seo网站推广目的,中文在线中文资源,音乐自助建站,东营公共资源交易信息网图论的经典题型#xff0c;深度优先搜索和广度优先搜索都可以#xff0c;但是本题推荐使用广度优先搜索#xff08;类似的题最好都用广度优先搜索#xff09;#xff0c;因为使用深度优先搜索会爆栈#xff08;栈溢出#xff09;。本篇博客两种方法都进行讲解#xff0…图论的经典题型深度优先搜索和广度优先搜索都可以但是本题推荐使用广度优先搜索类似的题最好都用广度优先搜索因为使用深度优先搜索会爆栈栈溢出。本篇博客两种方法都进行讲解也会讲解栈溢出的解决方案。
题目
题目链接全球变暖 你有一张某海域 N×N 像素的照片”.”表示海洋、”#”表示陆地如下所示
.......
.##....
.##....
....##.
..####.
...###.
.......其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿例如上图就有 2 座岛屿。 由于全球变暖导致了海面上升科学家预测未来几十年岛屿边缘一个像素的范围会被海水淹没。 具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)它就会被淹没。 例如上图中的海域未来会变成如下样子
.......
.......
.......
.......
....#..
.......
.......请你计算依照科学家的预测照片中有多少岛屿会被完全淹没。
输入格式 第一行包含一个整数N。 以下 N 行 N 列包含一个由字符”#”和”.”构成的 N×N 字符矩阵代表一张海域照片”#”表示陆地”.”表示海洋。照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。
输出格式 一个整数表示答案。
数据范围 1≤N≤1000
输入样例1
7
.......
.##....
.##....
....##.
..####.
...###.
.......输出样例1 1
输入样例2
9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........输出样例2 1
思路
接触过图论的同学都知道 连通块问题是基础搜索。用DFS或BFS都行遍历一个连通块找到这个连通块中所有的’#‘并标记已经搜过不用再搜再遍历下一个连通块…遍历完所有连通块统计有多少个连通块。
本题是在寻找连通块的基础上进行了进阶问题1还要找寻被淹没的连通块问题2。这里分步讨论
问题1很好解决那么问题2该如何计数呢
方法一BFS
在统计连通块的基础上我们可以定义两个变量 total 和 bound
total 用来统计每个连通块上有多少块土地
bound 用来统计在每个连通块上有多少土地是紧挨着水的上下左右任意一边挨水都算
如果 total bound 则表明该连通块会完全淹没因为所有土地都紧靠水。
这个思路想出来了问题就很好解决了下面直接套用模板就行
代码及详细注释
from collections import deque# 输入迷宫大小
n int(input())
a []
# 读取迷宫
for i in range(n):path list(input())a.append(path)# 记录访问情况
vis [[False] * n for _ in range(n)]
# 定义四个方向
dirs [[0,1],[0,-1],[1,0],[-1,0]]def bfs(x, y):global total, boundq deque()vis[x][y] Trueq.append([x, y])while q:curx, cury q.popleft()total 1is_bound Falsefor dir in dirs:next_x curx dir[0]next_y cury dir[1]# 边界检查if next_x 0 or next_y 0 or next_x n or next_y n:continue# 已访问过的点跳过if vis[next_x][next_y] True:continue# 如果是水域标记为边界点并跳过if a[next_x][next_y] .:is_bound Truecontinuevis[next_x][next_y] Trueq.append([next_x, next_y])if is_bound:bound 1cnt 0
# 遍历整个迷宫
for i in range(n):for j in range(n):# 未访问过的岛屿开始进行搜索if vis[i][j] False and a[i][j] #:total 0bound 0bfs(i, j)# 如果所有土地都紧靠水计数加一if total bound:cnt 1print(cnt)
方法二DFS
dfs解决问题二的时候有个很巧妙的方法就是在统计连通块的时候多加一个判断语句判断当前岛屿是否被完全淹没就是判断上下左右是否为陆地如果是陆地的话最后计数不算该连通块。
但是dfs很大的问题就是栈溢出问题也就是爆栈虽然 dfs 比 bfs 写起来简单但不太推荐大家在打比赛的时候用爆栈几率小但也不敢赌啊
解决爆栈问题也比较简单对递归深度进行限制即可使用sys.setrecursionlimit()函数
在Python中sys.setrecursionlimit()函数用于设置递归深度限制。递归深度指的是递归函数嵌套调用的层数。通过调用sys.setrecursionlimit()函数可以设置Python解释器允许的最大递归深度从而避免递归调用导致的栈溢出错误。
代码及详细注释
import sys
# 设置递归深度限制
sys.setrecursionlimit(60000)# 读取输入的迷宫大小
n int(input())# 读取迷宫地图
a []
for i in range(n):path list(input())a.append(path)# 记录访问状态
vis [[False] * n for _ in range(n)]# 定义四个方向
dirs [[0, 1], [0, -1], [1, 0], [-1, 0]]# 深度优先搜索函数
def dfs(x, y):global flagvis[x][y] True# 判断当前岛屿是否被完全淹没if a[x][y 1] # and a[x][y - 1] # and a[x 1][y] # and a[x - 1][y] #:flag 1# 遍历四个方向for dir in dirs:next_x x dir[0]next_y y dir[1]if next_x 0 or next_y 0 or next_x n or next_y n:continueif vis[next_x][next_y] True:continueif a[next_x][next_y] .:continuedfs(next_x, next_y)# 统计未被淹没的岛屿数量
cnt 0
for i in range(n):for j in range(n):if vis[i][j] False and a[i][j] #:flag 0dfs(i, j)if flag 0:cnt 1
# 输出结果
print(cnt)
总结
本题看着很简单但是统计问题解决实现起来还是有点绕的。
