【题目来源】
蓝桥云课：1.全球变暖 - 蓝桥云课 (lanqiao.cn)
【题目描述】
你有一张某海域 \(N\times N\) 像素的照片， "."表示海洋、"#"表示陆地， 如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 \(2\) 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入】
第一行包含一个整数 \(N(1≤N≤1000)\).
以下 \(N\) 行 \(N\) 列代表一张海域照片。
照片保证第 \(1\) 行、第 \(1\) 列、第 \(N\) 行、第 \(N\) 列的像素都是海洋。
【输出】
输出一个整数表示答案。
【输入样例】
7
.......
.##....
.##....
....##.
..####.
...###.
.......
【输出样例】
1
【算法标签】
《蓝桥云课 178 全球变暖》 #2018# #省赛# #DFS#
【代码详解】
import sys
#扩栈：递归层数过大，需要设置最大栈空间
sys.setrecursionlimit(100000)#从左往右，从上到下，对于每一个未标记的陆地，做一遍DFS
#DFS目的：扩展能够到达的所有店，并打上标记
#可以统计出有多少个连通块
def dfs(x, y):#当前处于(x,y)，标记当前点vis[x][y]=1#判断当前点是否为高地if Map[x][y+1]=='#' and Map[x+1][y]=='#' and Map[x-1][y]=='#' and Map[x][y-1]=='#':global flagflag = True#往四周扩展，把所有相邻的点打上标记for (delta_x, delta_y) in [(1,0), (0,1), (-1,0), (0,-1)]:xx, yy = x+delta_x, y+delta_y # 因为题目中说第1行、第1列、第N行、第N列都是海洋，所以无需做边界判断if Map[xx][yy]=='#' and vis[xx][yy]==0: dfs(xx, yy)N = int(input())
Map = []
vis = [] #vis[i][j]表示每个点是否打标记
for i in range(N):Map.append(list(input()))vis.append([0]*N)
#ans表示淹没岛屿的数量
ans = 0
for i in range(N):for j in range(N):if Map[i][j] == '#' and vis[i][j] == 0:#flag表示当前岛屿是否存在高地flag = 0dfs(i, j)if flag==False:ans += 1
print(ans)
【运行结果】
7
.......
.##....
.##....
....##.
..####.
...###.
.......
1