dfs72分求助

P8662 [蓝桥杯 2018 省 AB] 全球变暖

SvanurA @ 2023-01-16 22:58:27

def dfs(y, x, map):
    if map[y][x] != '#':
        return
    map[y][x] = '.'
    dfs(y - 1, x, map)
    dfs(y + 1, x, map)
    dfs(y, x - 1, map)
    dfs(y, x + 1, map)

n = int(input())

map = []
for i in range(n):
    map.append(list(input()))

for i in range(1, n - 1):
    for j in range(1, n - 1):
        if map[i - 1][j] == '#' and map[i + 1][j] == '#' and map[i][j + 1] == '#' and map[i][j - 1] == '#':
            dfs(i, j, map)

ans = 0
for i in range(n):
    for j in range(n):
        if map[i][j] == '#':
            dfs(i, j, map)
            ans += 1
print(ans)

我的思路是先把不会完全沉没的岛屿清掉,然后剩下的岛屿就一定是能够完全沉没的,用dfs统计。但是最后两个测试点RE了


by SvanurA @ 2023-01-17 16:05:16

此贴终结,因为python的递归最大深度问题,改了递归最大深度就好了


|