AcWing 1233. 全球变暖
你有一张某海域 N×NN×N 像素的照片,”.”表示海洋、”#”表示陆地,如下所示:
.......
.##....
.##....
....##.
..####.
...###.
.......
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿,例如上图就有 22 座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
.......
.......
.......
.......
....#..
.......
.......
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
输入格式
第一行包含一个整数N。
以下 NN 行 NN 列,包含一个由字符”#”和”.”构成的 N×NN×N 字符矩阵,代表一张海域照片,”#”表示陆地,”.”表示海洋。
照片保证第 11 行、第 11 列、第 NN 行、第 NN 列的像素都是海洋。
输出格式
一个整数表示答案。
数据范围
1≤N≤10001≤N≤1000
输入样例1:
7
.......
.##....
.##....
....##.
..####.
...###.
.......
输出样例1:
1
输入样例2:
9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........
输出样例2:
1
难度:简单 |
---|
时/空限制:1s / 64MB |
总通过数:2088 |
总尝试数:4458 |
来源:第九届蓝桥杯省赛C++A/B组,第九届蓝桥杯省赛JAVAA/B组 |
算法标签 |
Code
from collections import deque
N = 1010
graph = [[0] * N for _ in range(N)]
state = [[0] * N for _ in range(N)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def BFS():
res = 0 # 不会淹没的岛屿
island = 0 # 总岛屿数
queue = deque()
for i in range(1,n+1):
for j in range(1,n+1):
if state[i][j]:
continue
state[i][j] = 1
if graph[i][j] == "#":
# 发现新大陆
island += 1
queue.append((i,j))
# 登上新的岛屿
is_live = False
while queue:
x,y = queue.popleft()
sur = 0 # 周围的陆地数量
for k in range(4):
a = x + dx[k]
b = y + dy[k]
if 1<=a<=n and 1<=b<=n and graph[a][b] == "#":
if not state[a][b]:
queue.append((a,b))
state[a][b] = 1
sur += 1
if sur == 4:
is_live = True
if is_live:
res += 1
return island - res
if __name__ == "__main__":
n = int(input())
for i in range(1,n+1):
line = [x for x in input()]
graph[i][1:n+1] = line
print(BFS())