【2018 蓝桥杯】全球变暖【BFS】【Python解法】

思路很清晰。

1. 遍历图中所有的点，遇到 “#”， 代表是岛屿的区块。
2. 用 bfs 向外扩展岛屿，遇到海就停住。 （使用一个 vis 记录遍历过的点）
3. 在遍历一个岛屿的过程中，同时记录不会被淹没区块的数量：实现一个 flood 函数判断区块的上下左右是否是海洋。
4. bfs 返回剩余区块的数量。 返回若为零代表完全被淹没。

几个注意的点：

1. 题目问的是被完全淹没的点的数量。我看成了剩余的岛屿的数量，结果因为给的样例两种情况都是一就弄错了。
2. 注意需要单独判断一下起始点是否会被淹没来决定区块数量的初始化值。（也可以不标记在后续的点中被搜索到。）

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
sea = [list(input().strip()) for _ in range(n)]
direct = [(0, 1), (1, 0), (-1, 0), (0, -1)]
vis = [[False]*n for _ in range(n)]
def check(x, y):
    if (x<0 or y<0 or x>=n or y>=n): return False
    if (vis[x][y]): return False
    if (sea[x][y]=="."): return False
    return True
def flood(x, y):
    for dx, dy in direct:
        nx, ny = x + dx, y + dy
        if (nx<0 or ny<0 or nx>=n or ny>=n): continue
        if(sea[nx][ny]=="."): return True
    return False
def bfs(x ,y):
    q = deque()
    q.append((x, y))
    blocks = 0 if flood(x, y) else 1
    while q:
        tx, ty = q.popleft()
        for dx, dy in direct:
            nx, ny = tx + dx, ty + dy
            if(check(nx, ny)):
                vis[nx][ny] = True
                q.append((nx, ny))
                if(not flood(nx, ny)): blocks+=1
    return blocks
res = 0
for x in range(n):
    for y in range(n):
        if(sea[x][y]=="#" and not vis[x][y]):
            vis[x][y] = True
            rest = bfs(x, y)
            if(rest==0): res+=1
print(res)