全球变暖|蓝桥杯

2024-02-10 19:30

文章标签 蓝桥全球变暖

本文主要是介绍全球变暖|蓝桥杯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

全球变暖|蓝桥杯

https://www.lanqiao.cn/problems/178/learning/
在这里插入图片描述

题目分析
dfs先查找有多少岛屿和这一题相似，再减去没有淹没的岛屿
洛谷 P1596 [USACO10OCT]Lake Counting S
https://www.luogu.com.cn/problem/P1596

Lake Counting代码

#include<iostream>
using namespace std ;
char squ[10001][10001];
int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
int res=0;
int n,m;
void dfs(int x,int y)
{squ[x][y]='.';for(int i=0;i<8;i++){int nx=x+dir[i][0];int ny=y+dir[i][1];if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&squ[nx][ny]=='W')dfs(nx,ny);}
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>squ[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(squ[i][j]=='W'){res++;dfs(i,j);}cout<<res;return 0;
}

代码

#include <iostream>
using namespace std;
int n;
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
char map[10001][10001];
int flag = 1;
int yanmo = 0;
int daoyu = 0;
int k;
void dfs(int x, int y)
{k = 0;map[x][y] = '@';for (int i = 0; i < 4; i++){int tx = x + dir[i][0];int ty = y + dir[i][1];if (map[tx][ty] == '#'||map[tx][ty]=='@')k++;}if (k == 4&&flag) {yanmo++;flag = 0;}for (int i = 0; i < 4; i++){int nx = x + dir[i][0];int ny = y + dir[i][1];if(nx>=1&&ny>=1&&nx<=n&&ny<=n&&map[nx][ny]=='#')dfs(nx, ny);}return;
}
int main()
{cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> map[i][j];for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){if (map[i][j] == '#'){flag = 1;dfs(i, j);daoyu++;}}cout<< daoyu-yanmo;return 0;
}