你有一张某海域 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)