题目描述
你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：
....... .##.... .##.... ....##. ..####. ...###. .......其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
....... ....... ....... ....... ....#.. ....... .......请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
输出
一个整数表示答案。
样例输入
7 ....... .##.... .##.... ....##. ..####. ...###. .......
样例输出
1
算法分析：dfs求连通块
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 constexpr size_t maxn = 1e3 + 5; 6 char mp[maxn][maxn]; 7 int n, ans; 8 bool flag = 0; 9 bool vis[maxn][maxn]; 10 int dx[4] = {0,0,1,-1}; 11 int dy[4] = {1,-1,0,0}; 12 void dfs(int x, int y){ 13 14 vis[x][y] = 1; 15 int t = 0;//用来记录当前的的点四周陆地的数量 16 for(int i = 0; i < 4; ++ i){ 17 int nx = x + dx[i]; 18 int ny = y + dy[i]; 19 if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue; 20 if(vis[nx][ny]){ 21 t++;//如果搜过说明它这个方向也是陆地 22 continue; 23 } 24 if(mp[nx][ny] != '#') continue; 25 dfs(nx, ny); 26 t++; 27 } 28 if(t == 4 && !flag)//flage用来特判，因为一个连通块加上一次就行了,ans是不会被淹没的岛屿 29 flag = true; 30 ans++; 31 } 32 33 int main(){ 34 cin >> n; 35 int cnt = 0; 36 for(int i = 0; i < n; ++ i) 37 scanf("%s", mp[i]); 38 for(int i = 0; i < n; ++ i) 39 for(int j = 0; j < n; ++ j) 40 if(mp[i][j] == '#' && !vis[i][j]) flag = 0,dfs(i, j), cnt ++; 41 cout << cnt - ans << endl; 42 return 0; 43 } 44