【题目描述】 你有一张某海域NxN像素的照片，".“表示海洋、”#"表示陆地，如下所示：
… .##… .##… …##. …####. …###. …
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
… … … … …#… … …
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】 第一行包含一个整数N。 (1 <= N <= 1000) 以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】 一个整数表示答案。
【样例输入】 7 … .##… .##… …##. …####. …###. …
【样例输出】 1
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms
思路：求连通块个数 岛屿为陆地相而成，求岛屿数目即求图连通块个数。 求得岛屿数目后还要注意一个问题，不是所有岛屿都会被水完全淹没，只有构成当前岛屿的每一块陆地都与海洋相连，此岛屿才会被完全淹没。即在连通块中，如果连通块(岛屿)内存在一点陆地，其上下左右全是陆地(即此点不挨着海，无法被淹没)，那么此连通块(岛屿)就不能被完全淹没。 想明白此点此题便可顺利求解。
求连通块可用bfs也可用dfs。 dfs求连通块的本质是一旦能连通就dfs把此连通块全部标记，再遇到新连通块时再dfs把其全部标记，通过相同的id确定为一块连通块。 代码如下，注释很清楚
#include <iostream> using namespace std; char mp[1005][1005]; int idx[1005][1005]; int n; int cnt； int flag=0;//此标记用来看当前连通块中是否有点的上下左右全为陆地 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; void dfs(int x,int y,int id)//求连通块 { if(x<0 || y<0 || x>n || y>n) return;//越界 if(mp[x][y]!='#' || idx[x][y]!=0)return; //此点不连通或者是连通的但是已经记录过 idx[x][y] = id;//连通块的编号，有几个id就有几个连通块 if(flag==0)//如果此连通块还没找到四个方向都是陆地的点就继续找，一旦找到了至少一点，flag会变为4，就进不去此判断 { for(int i=0;i<4;i++)//寻找当前点的上下左右四个方向是否全为陆地 { //如果全为陆地，则说明此连通块构成的岛屿不会被全部淹没 int dx = x+dir[i][0]; int dy = y+dir[i][1]; //不用考虑越界问题，只有当x,y是边界上点时，dxdy才会越界 //此题已告知地图四周全为海洋，即地图四周上的点在dfs第二行判断是否是陆地时就返回了，无法进入此循环 if(mp[dx][dy]=='#')flag++; else //只要此点有一个方向与海洋相邻便标记为0，继续寻找此连通块内有没有四个方向都是陆地的点 { flag = 0; break; } } } for(int i=0;i<4;i++) { int dx = x+dir[i][0]; int dy = y+dir[i][1]; dfs(dx,dy,id); } } int main() { cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>mp[i][j]; } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(mp[i][j]=='#' && idx[i][j]==0) { dfs(i,j,++cnt);//查找连通块 if(flag == 4) { --cnt; flag = 0;//一定不要忘记当前连通块找完后flag要变回0，否则下个连通块无法正确判断 } } } } cout<<cnt<<endl; }