你有一张某海域 N×N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：

…

.##…

.##…

…##.

…####.

…###.

…

其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。

具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

…

…

…

…

…#…

…

…

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入格式

第一行包含一个整数N。

以下 N 行 N 列，包含一个由字符”#”和”.”构成的 N×N 字符矩阵，代表一张海域照片，”#”表示陆地，”.”表示海洋。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。

输出格式

一个整数表示答案。

数据范围

1≤N≤1000

输入样例1：

7

1. … 2. .##… 3. .##… 4. …##. 5. …####. 6. …###. 7. …

输出样例1：

1

输入样例2：

1. 9 2. … 3. .##.##… 4. .#####… 5. .##.##… 6. … 7. .##.#… 8. .#.###… 9. .#…#… 10. …

输出样例2：

1

思路

对所给图片的每一个点进行宽度搜索。设置flag,如果flag==0,说明不被淹没，否则被淹没。

如果一块地周围都是土地，那么他最终不会被淹没。

标记搜算过的土地，避免重复搜索。

搜索当前土地相邻的未标记的土地，直到搜完这块岛屿为止

代码

1. def bfs(i,j): 2. d=[(0,1),(0,-1),(1,0),(-1,0)] 3. q=[(i,j)] 4. vis[i][j]=1 5. global flag 6. while q: 7. t=q.pop(0) 8. tx,ty=t[0],t[1] 9. if mp[tx][ty+1]=='#' and mp[tx][ty-1]=='#' and mp[tx-1][ty]=='#' and mp[tx+1][ty]=='#': 10. flag=1 11. for n in range(4): 12. nx=tx+d[n][0] 13. ny=ty+d[n][1] 14. if vis[nx][ny]==0 and mp[nx][ny]=="#": 15. q.append((nx,ny)) 16. vis[nx][ny]=1 17. 18. n=int(input()) 19. mp=[] 20. for i in range(n): 21. mp.append(list(input())) 22. 23. vis = [] 24. for i in range(n): 25. vis.append([0]*n) 26. 27. ans=0 28. for i in range(n): 29. for j in range(n): 30. if vis[i][j]==0 and mp[i][j]=='#': 31. flag=0 32. bfs(i,j) 33. if flag==0: 34. ans+=1 35. print(ans)