2276: 蓝桥杯2018年第九届真题-全球变暖（Python3） DFS+BFS

解题思路:
    1.深搜所有地图;

    2.遇到岛屿对周围同样是岛屿的部分广搜，同时判断该岛屿是否会完全沉没；

注意事项:
    1.此处的深搜不带回溯；

    2.广搜时的判断沉没部分很重要；

    3.除了注意判断边界，每次找一个陆地周围的情况时，要找4个方向才行；

    4.广搜时同样要记录被访问的点，避免一个连在一起的岛屿的陆地被割裂开判断；

    5.如果一个陆地确定会“存活”，再找该陆地的其他部分时就跳过“存活”判断部分。

参考代码:

def bfs(a, b):
    global visited, around
    stack, flag = [(a, b)], 0
    while stack:
        temp = stack.pop(0)
        visited[temp[0]][temp[1]] = True
        if not flag:
            flag = bool(sum(1 for u in around if 0 <= temp[0] + u[0] < n and 0 <= temp[1] + u[1] < n
                            and map_[temp[0] + u[0]][temp[1] + u[1]] == '#') == 4)
        for u in around:
            if 0 <= temp[0] + u[0] < n and 0 <= temp[1] + u[1] < n and \
                    map_[temp[0] + u[0]][temp[1] + u[1]] == '#' and \
                    not visited[temp[0] + u[0]][temp[1] + u[1]] and (temp[0] + u[0], temp[1] + u[1]) not in stack:
                stack.append((temp[0] + u[0], temp[1] + u[1]))
    return flag


n, islands, total = int(input()), 0, 0
map_ = [list(input()) for _ in range(n)]
visited = [[False for _ in range(n)] for _ in range(n)]
around = [(1, 0), (0, 1), (-1, 0), (0, -1)]

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            if map_[i][j] == '#':
                total += 1
                islands += 1 if bfs(i, j) else 0
            visited[i][j] = True
print(total - islands)