郑州交通建设投资有限公司网站,建设网站时间推进表,网站的总规划书,wordpress编辑器支持代码题目描述
你有一张某海域 NxN 像素的照片#xff0c;.表示海洋、#表示陆地#xff0c;如下所示#xff1a;
.......
.##....
.##....
....##.
..####.
...###.
.......
其中上下左右四个方向上连在一起的一片陆地组成一座岛屿…题目描述
你有一张某海域 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 qQueue() #创建队列vis[x][y]1 #标记使用q.put((x,y)) #放入while not q.empty(): #是否为空x,yq.get((x,y)) #弹出队头if mp[x][y1]# and mp[x][y-1]# and mp[x1][y]# and mp[x-1][y]#:flag1 #判断是否为高地高地不被淹没for i in range(4):xtxl[i][0]ytyl[i][1]if vis[xt][yt]0 and mp[xt][yt]#:q.put((xt,yt))vis[xt][yt]1nint(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)
ans0
for i in range(n):for j in range(n):if vis[i][j]0 and mp[i][j]#: #没被标记且为陆地flag0bfs(i,j)if flag0:ans1
print(ans)
用list实现队列
def bfs(x,y):global flag vis[x][y]1 #标记使用q[(x,y)] #放入while q: #是否为空x,yq.pop(0) #弹出队头if mp[x][y1]# and mp[x][y-1]# and mp[x1][y]# and mp[x-1][y]#:flag1 #判断是否为高地高地不被淹没for i in range(4):xtxl[i][0]ytyl[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 #标记使用qdeque() q.append((x,y))while q: #是否为空x,yq.popleft() if mp[x][y1]# and mp[x][y-1]# and mp[x1][y]# and mp[x-1][y]#:flag1 #判断是否为高地高地不被淹没for i in range(4):xtxl[i][0]ytyl[i][1]if vis[xt][yt]0 and mp[xt][yt]#:q.append((xt,yt))vis[xt][yt]1 建议用队列操作时使用deque
