Python：每日一题之全球变暖（BFS连通性判断）

题目描述

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

.......

.##....

.##....

....##.

..####.

...###.

.......

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

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

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

.......

.......

.......

.......

....#..

.......

.......

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

输入描述

第一行包含一个整数 N (1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

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

输出一个整数表示答案。

输入输出样例

示例

输入

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出

1

思路：

连通性判断：
图论的一个简单问题，给定一张图，图由点和连接点的边组成，要求找到图中互相连通的部分。
BFS判断连通性的步骤：
        ·从图上任意一个点u开始遍历，把它放进队列中。
        ·弹出队首u，标记u已搜过，然后搜索u的邻居点，即与u连通的点，放到队列中。
        ·继续弹出队首，标记搜过，然后搜索与它连通的邻居点，放进队列。
继续以上步骤，直到队列为空，此时一个连通块已经找到。
其他没有访问到的点，属于另外的连通块，按以上步骤再次处理这些点。
最后所有点都搜到，所有连通块也都找到。
连通性判断
什么岛屿不会被完全淹没？
        >若岛中有个陆地（称为高地），它周围都是陆地，那么这个岛不会被完全淹没。
        >用BFS搜出有多少个岛（连通块），检查这个岛有没有高地，统计那些没有高地的岛（连通块）的数量，就是答案。
        >计算复杂度：每个像素点只用搜一次且必须至少搜一次，共N2个点，BFS的复杂度是O(N2)，不可能更好了。

参考代码：

from queue import *  #导入模块
def bfs(x,y):global flag    q=Queue()     #创建队列vis[x][y]=1   #标记使用q.put((x,y))  #放入while not q.empty():  #是否为空x,y=q.get((x,y))   #弹出队头if mp[x][y+1]=="#" and mp[x][y-1]=='#' and mp[x+1][y]=='#' and mp[x-1][y]=='#':flag=1   #判断是否为高地，高地不被淹没for i in range(4):xt=x+l[i][0]yt=y+l[i][1]if vis[xt][yt]==0 and mp[xt][yt]=='#':q.put((xt,yt))vis[xt][yt]=1n=int(input())
mp=[]
l=[(1,0),(-1,0),(0,-1),(0,1)]
for i in range(n):mp.append(list(input()))
vis=[]
for i in range(n):vis.append([0]*n)
ans=0
for i in range(n):for j in range(n):if vis[i][j]==0 and mp[i][j]=='#': #没被标记且为陆地flag=0bfs(i,j)if flag==0:ans+=1
print(ans)

用list实现队列 ：

def bfs(x,y):global flag    vis[x][y]=1   #标记使用q=[(x,y)]  #放入while q:  #是否为空x,y=q.pop(0)   #弹出队头if mp[x][y+1]=="#" and mp[x][y-1]=='#' and mp[x+1][y]=='#' and mp[x-1][y]=='#':flag=1   #判断是否为高地，高地不被淹没for i in range(4):xt=x+l[i][0]yt=y+l[i][1]if vis[xt][yt]==0 and mp[xt][yt]=='#':q.append((xt,yt))vis[xt][yt]=1

用deque实现队列：

from collections import *  #导入模块
def bfs(x,y):global flag    vis[x][y]=1   #标记使用q=deque()  q.append((x,y))while q:  #是否为空x,y=q.popleft()   if mp[x][y+1]=="#" and mp[x][y-1]=='#' and mp[x+1][y]=='#' and mp[x-1][y]=='#':flag=1   #判断是否为高地，高地不被淹没for i in range(4):xt=x+l[i][0]yt=y+l[i][1]if vis[xt][yt]==0 and mp[xt][yt]=='#':q.append((xt,yt))vis[xt][yt]=1

---

建议用队列操作时，使用deque