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