返回题解分享
讨论 / 题解分享/ 帖子详情

全球变暖(编程题) - 题解

n = int(input())    # 输入地图的大小
a = [input() for _ in range(n)] # 存储地图的数组
# print(*a, sep='\n')   # 打印地图
flag = 0    # 用于标记岛屿是否被完全淹没
vis = [[0] * n for _ in range(n)]   # 标记是否搜过的二维数组
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]   # 四个方向(上、右、下、左)的偏移量


def dfs(x, y):
    global flag
    vis[x][y] = 1   # 标记当前位置已经被搜索过
    if (x - 1 < 0 or a[x - 1][y] == '#') and (y + 1 > n - 1 or a[x][y + 1] == '#') and (x + 1 > n - 1 or a[x + 1][y] == '#') and (y - 1 < 0 or a[x][y - 1] == '#'):
        flag = 1    # 若周围都是陆地不会被淹没
    for dx, dy in dirs:  # 搜索当前位置的四个相邻位置
        nx, ny = x + dx, y + dy
        if nx < 0 or nx > n - 1 or ny < 0 or ny > n - 1:    # 地图边界
            continue
        if a[nx][ny] == '#' and vis[nx][ny] == 0:   # 如果相邻位置是未搜索过的陆地
            dfs(nx, ny) # 继续搜索其相邻位置


cnt = 0
# DFS所有像素点
for i in range(n):
    for j in range(n):
        # 如果当前位置是陆地且未被搜索过
        if a[i][j] == '#' and vis[i][j] == 0:
            flag = 0
            dfs(i, j)
            if flag == 0:
                cnt += 1
print(cnt)
0 回复 0 转发 0 喜欢 3 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!