2276: 蓝桥杯2018年第九届真题-全球变暖（bfs）

解题思路:

做这道题看错了两个地方，一开始做成了求存活的#的数量，后来又看成了存活的岛屿的数量，其实题目问的是有多少岛屿被淹没。

可以上下左右联通的为同一岛屿，以样例数据为例：

有两岛屿，只有右下角的岛屿中有一个不和海洋接触的陆地#，所以左上角的岛屿会被淹没，右下角的岛屿会存留下来。

所以问题转变成了将这些岛屿找出来，并且查找岛屿内有没有不和海洋连接的陆地，如果没有的就看成被淹没，答案数量+1。

先遍历数组，如果找到了陆地#，而且没有被标记过（不是之前岛屿里的陆地），就从这个陆地开始向上下左右四个方向寻找，将找到陆地进行标记，在下一次寻找的时候不查找标记过的陆地#。

同时记录一个陆地上下左右是不是都是陆地，如果找遍联通的陆地都没有（说明这个岛屿会被淹没），就返回一个0，让答案数+1。

上面的情况用dfs bfs都可以做，不过bfs在做判断上更简单一些。

参考代码:

#include <bits/stdc++.h>
#include <queue>
using namespace std;

struct node{
	int x,y,l;//坐标xy，l记录走过的步数，不过在这道题里没有用
};

int dx[8]={1,-1,0,0,-1,1,1,-1};//上 下 左 右 右上 右下 左下 左上 
int dy[8]={0,0,-1,1,1,1,-1,-1};//四个方向寻找就可以了

bool vis[1001][1001];//记录是否访问过
char p[1001][1001];
queue<node>q;
int n,z=0;

bool dfs(int x1,int y1){
	bool b=0;
	q.push({x1,y1,1});//坐标入队，从x1 y1开始寻找
	while(!q.empty()){
		int k=0;//记录周围有多少个陆地
		node now=q.front();
		vis[now.x][now.y]=1;
		q.pop();
		for(int i=0;i<4;i++){//四个方向寻找
			int x=now.x+dx[i];
			int y=now.y+dy[i];
			if(x>0&&y>0&&x<=n&&y<=n){
				if(p[x][y]=='#'){//如果是陆地
					k++;
					if(!vis[x][y]){//如果没有访问过
						vis[x][y]=1;
						q.push({x,y,now.l+1});
					}
				}
			}	
		}
		if(k==4)b=1;//如果上下左右都是陆地
	}
	return b;//返回岛屿是否没有被淹没

}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>p[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(vis[i][j]==0&&p[i][j]=='#'){//如果没有访问过并且是陆地
				if(!dfs(i,j))z++;//如果这个岛屿会被淹没，答案+1
			}
		}
	}
	
	cout<<z;

 	return 0;
}