PythonでJOI難易度5を埋める #25

D - 薄氷渡り

一つの経路を調べた後に氷を経路を調べる前の状態に戻す必要があるので，再帰関数で実装します．

m = int(input())
n = int(input())
ice = [[0] * (m + 2)]
for _ in range(n):
    tmp  = list(map(int, input().split()))
    ice.append([0] + tmp + [0])
ice.append([0] * (m + 2))


ans = 0
def dfs(n, m, d):
    global ans
    if ice[n][m] == 0:
        return
    ans = max(ans, d)

    ice[n][m] = 0
    for i, j in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
        go_x = n + i
        go_y = m + j
        dfs(go_x, go_y, d + 1)
    ice[n][m] = 1

for i in range(1, n + 1):
    for j in range(1, m + 1):
        dfs(i, j, 1)

print(ans)

参考にした記事