站长论坛 激活网站展厅设计要考虑哪些方面

图论的经典题型，深度优先搜索和广度优先搜索都可以，但是本题推荐使用广度优先搜索（类似的题最好都用广度优先搜索），因为使用深度优先搜索会爆栈（栈溢出）。本篇博客两种方法都进行讲解，也会讲解栈溢出的解决方案。

题目：

题目链接：全球变暖
你有一张某海域 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)

总结：

本题看着很简单，但是统计问题解决实现起来还是有点绕的。