图论的经典题型，深度优先搜索和广度优先搜索都可以，但是本题推荐使用广度优先搜索（类似的题最好都用广度优先搜索），因为使用深度优先搜索会爆栈（栈溢出）。本篇博客两种方法都进行讲解，也会讲解栈溢出的解决方案。
题目：
题目链接：全球变暖
你有一张某海域 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, bound
q = deque()
vis[x][y] = True
q.append([x, y])
while q:
curx, cury = q.popleft()
total += 1
is_bound = False
for 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 = True
continue
vis[next_x][next_y] = True
q.append([next_x, next_y])
if is_bound:
bound += 1
cnt = 0
# 遍历整个迷宫
for i in range(n):
for j in range(n):
# 未访问过的岛屿开始进行搜索
if vis[i][j] == False and a[i][j] == '#':
total = 0
bound = 0
bfs(i, j)
# 如果所有土地都紧靠水，计数加一
if total == bound:
cnt += 1
print(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 flag
vis[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:
continue
if vis[next_x][next_y] == True:
continue
if a[next_x][next_y] == '.':
continue
dfs(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 = 0
dfs(i, j)
if flag == 0:
cnt += 1
# 输出结果
print(cnt)
总结：
本题看着很简单，但是统计问题解决实现起来还是有点绕的。
