JOI2009予選d

atcoder.jp

与えられた’１’のマスを移動できる最大値を求める問題。
普通の bfs だと例えば

1 1 0
1 1 0
1 0 0

が与えられたときに a[1][1]をスタートとしても

3 2 0
2 1 0
3 0 0

のような移動距離を返してくる（本当は a[2][0] = 5となってほしい）
そこで通常の bfs(i, j) に加えて距離を表す d を追加した、bfs(i, j, d) にして、今までの最大距離を保存する、
ある点 a から次に行くところがなくなったら、その手前の地点 b に戻って次に行けるところを探すが、そのときに a に’まだ行ってないことにして’新しいルートを探すようにする
(b の直ぐ次に a に行くルートの探索は終わっているので無限ループすることはない）

m = int(input())
n = int(input())
s = []
for i in range(n):
  array = [int(i) for i in input().split()]
  s.append(array)

import sys
sys.setrecursionlimit(1000000)

def dfs(x,y,d):
    s[x][y] = 0
    nd = d + 1
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and s[nx][ny] != 0:
                d = max(dfs(nx,ny,nd),d)
    s[x][y] = 1
    return d
  
chk = set()
for i in range(n):
      for j in range(m):
          if s[i][j] == 1:
              chk.add(dfs(i,j,1))
              
print(max(chk))