Problem:


薄氷渡り

問題

冬の寒いある日，JOI太郎君は広場にはった薄氷を割って遊ぶことにした．広場は長方形で，東西方向に m 個，南北方向に n 個，つまり， m &times; n の区画に区切られている．また，薄氷が有る区画と無い区画がある． JOI太郎君は，次のルールにしたがって，薄氷を割りながら区画を移動することにした．

    
 薄氷があるどの区画からも薄氷を割り始めることができる．

    
 東西南北のいずれかの方向に隣接し， まだ割られていない薄氷のある区画に移動できる．

    
 移動した先の区画の薄氷をかならず割る．

JOI太郎君が薄氷を割りながら移動できる区画数の最大値を求めるプログラムを作成せよ．ただし， 1 ≤ m ≤ 90，1 ≤ n ≤ 90 である．与えられる入力データでは，移動方法は20万通りを超えない．

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

入力はn+2行ある． 1 行目には整数 m が書かれている． 2 行目には整数 n が書かれている． 3 行目から n+2 行目までの各行には、0 もしくは 1 が， 空白で区切られて m 個書かれており，各区画に薄氷があるか否かを表している．北から i 番目，西からj番目の区画を (i,j) と記述することにすると (1 ≤ i ≤ n, 1 ≤ j ≤ m)，第 i+2 行目の j 番目の値は，区画 (i,j) に薄氷が存在する場合は 1 となり，区画 (i,j) に薄氷が存在しない場合は 0 となる． 

m, n がともに 0 のとき入力の終了を示す. データセットの数は 5 を超えない．

出力

データセットごとに, 移動できる区画数の最大値を１行に出力せよ．

入出力例

入力例

3
3
1 1 0
1 0 1
1 1 0
5
3
1 1 1 0 1
1 1 0 0 0
1 0 0 0 1
0
0

出力例

5
5

1つ目の入力例に対して，最大値を与える移動方法の例　　

   
   

2つ目の入力例に対して，最大値を与える移動方法の例 

   

2つ目の入力例に対して，最大値を与えない移動方法の例

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
3
3
1 1 0
1 0 1
1 1 0
5
3
1 1 1 0 1
1 1 0 0 0
1 0 0 0 1
0
0


Sample output:
5
5

Submission status: Accepted

Solution code:
def solve():
  while True:
    m, n  = int(input()), int(input())
    if not m:
      break
    ices = [[0] + list(map(int,input().split())) + [0] for _ in range(n)]
    ices.insert(0, [0] * (m + 2),)
    ices.append([0] * (m + 2))
    score = [[0] * (m + 2) for _ in range(n + 2)]
    
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        score[x][y] = ices[x - 1][y] + ices[x + 1][y] + ices[x][y - 1] + ices[x][y + 1] 

    def search(x, y, imap, acc):
      imap[x][y] = 0
      acc += 1
      ret = acc
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = search(x - 1, y, imap, acc)
        if ret < a:
          ret = a
      if imap[x + 1][y]:
        b = search(x + 1, y, imap, acc)
        if ret < b:
          ret = b
      if imap[x][y - 1]:
        c = search(x, y - 1, imap, acc)
        if ret < c:
          ret = c
      if imap[x][y + 1]:
        d = search(x, y + 1, imap, acc)
        if ret < d:
          ret = d
      imap[x][y] = 1
      return ret
    
    ans = 0
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        if score[x][y] in [1, 2] and ices[x][y]:
          a = search(x, y, ices, 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()

Submission status: Accepted

Solution code:
def search(x, y, imap, acc):
  imap[x][y] = 0
  acc += 1
  ret = acc
  a = b = c = d = 0
  if imap[x - 1][y]:
    a = search(x - 1, y, imap, acc)
    if ret < a:
      ret = a
  if imap[x + 1][y]:
    b = search(x + 1, y, imap, acc)
    if ret < b:
      ret = b
  if imap[x][y - 1]:
    c = search(x, y - 1, imap, acc)
    if ret < c:
      ret = c
  if imap[x][y + 1]:
    d = search(x, y + 1, imap, acc)
    if ret < d:
      ret = d
  imap[x][y] = 1
  return ret
 

def solve():
  while True:
    m, n  = int(input()), int(input())
    if not m:
      break
    ices = [[0] + list(map(int,input().split())) + [0] for _ in range(n)]
    ices.insert(0, [0] * (m + 2),)
    ices.append([0] * (m + 2))
    score = [[0] * (m + 2) for _ in range(n + 2)]
    
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        score[x][y] = ices[x - 1][y] + ices[x + 1][y] + ices[x][y - 1] + ices[x][y + 1] 
   
    ans = 0
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        if score[x][y] in [1, 2] and ices[x][y]:
          a = search(x, y, ices, 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()

Submission status: Accepted

Solution code:
def search(x, y, imap, acc):
  imap[x][y] = 0
  acc += 1
  ret = acc
  a = b = c = d = 0
  if imap[x - 1][y]:
    a = search(x - 1, y, imap, acc)
    if ret < a:
      ret = a
  if imap[x + 1][y]:
    b = search(x + 1, y, imap, acc)
    if ret < b:
      ret = b
  if imap[x][y - 1]:
    c = search(x, y - 1, imap, acc)
    if ret < c:
      ret = c
  if imap[x][y + 1]:
    d = search(x, y + 1, imap, acc)
    if ret < d:
      ret = d
  imap[x][y] = 1
  return ret
 

def solve():
  while True:
    m, n  = int(input()), int(input())
    if not m:
      break
    ices = [[0] + list(map(int,input().split())) + [0] for _ in range(n)]
    ices.insert(0, [0] * (m + 2),)
    ices.append([0] * (m + 2))
    score = [[0] * (m + 2) for _ in range(n + 2)]
    
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        if ices[x][y]:
          score[x - 1][y] += 1
          score[x + 1][y] += 1
          score[x][y - 1] += 1
          score[x][y + 1] += 1
   
    ans = 0
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        if score[x][y] in [1, 2] and ices[x][y]:
          a = search(x, y, ices, 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()

Submission status: Accepted

Solution code:
while 1:
    M = int(input())
    N = int(input())
    if M == N == 0:
        break
    S = [list(map(int, input().split())) for i in range(N)]
    used=[[0]*M for i in range(N)]
    def dfs(x, y, dd=((-1,0),(0,-1),(1,0),(0,1))):
        r = 0
        for dx, dy in dd:
            nx = x + dx; ny = y + dy
            if 0 <= nx < M and 0 <= ny < N and S[ny][nx] and not used[ny][nx]:
                used[ny][nx] = 1
                r = max(r, dfs(nx, ny)+1)
                used[ny][nx] = 0
        return r
    ans = 0
    for i in range(N):
        for j in range(M):
            if S[i][j]:
                used[i][j] = 1
                ans = max(ans, dfs(j, i)+1)
                used[i][j] = 0
    print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

while True:

    m = int(raw_input())
    n = int(raw_input())

    if m == 0 and n == 0:
        break

    field = [[False] * m for y in xrange(n)]

    for y in xrange(n):
        line = map(int, raw_input().split(' '))
        for x in xrange(m):
            if line[x] == 1:
                field[y][x] = True

    ans = 0

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    def search(x, y, d):
        global ans

        if d > ans:
            ans = d

        for i in xrange(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < m and 0 <= ny < n and field[ny][nx]:
                field[ny][nx] = False
                search(nx, ny, d + 1)
                field[ny][nx] = True

    for x in xrange(m):
        for y in xrange(n):
            if field[y][x]:
                field[y][x] = False
                search(x, y, 1)
                field[y][x] = True

    print ans

Submission status: Accepted

Solution code:
def dfs(x, y):
  if x >= M or y >= N or x < 0 or y < 0 or field[y][x] == 0:
    return 0
  field[y][x] = 0
  res = max(dfs(x + 1, y), dfs(x - 1, y), dfs(x, y - 1), dfs(x, y + 1))
  field[y][x] = 1
  return res + 1

while True:
  M = input()
  N = input()
  field = []
  if not M and not N:
    break
  for i in range(N):
    field.append(map(int, raw_input().split()))

  ans = 0
  for x in range(M):
    for y in range(N):
      ans = max(dfs(x, y), ans)
  print ans

Submission status: Accepted

Solution code:
dx=[0,0,1,-1]
dy=[1,-1,0,0]

def dfs(y,x,cnt):
    global maxInt
    maxInt=max(maxInt,cnt)
    Ice[y][x]=0
    for i in range(4):
        mx=x+dx[i]
        my=y+dy[i]
        if mx<0 or m<=mx or my<0 or n<=my:
            continue
        if Ice[my][mx]==1:
            dfs(my,mx,cnt+1)
            Ice[my][mx]=1

while True:
    m=input()
    n=input()
    if n==m==0:break
    maxInt=0
    Ice=[map(int,raw_input().split()) for i in range(n)]
    for y in range(n):
        for x in range(m):
            if Ice[y][x]==1:
                dfs(y,x,1)
                Ice[y][x]=1
    print maxInt

Submission status: Accepted

Solution code:
while True:

  m = int(input())
  n = int(input())
  if m==n==0: exit()
  graph = []
  for _ in range(n):
    graph.append(list(map(int,input().split())))

  res = 0
  def dfs(r,c,ice):
    global res
    ice += 1
    graph[r][c] = 0

    for x,y in [(0,1), (1,0), (0,-1), (-1,0)]:
      nr,nc = r+x,c+y
      if nr<0 or nc<0 or nr>=n or nc>=m: continue
      if graph[nr][nc] == 1:
        dfs(nr,nc,ice)
    else:
      graph[r][c] = 1
      res = max(res, ice)

  for i in range(n):
    for j in range(m):
      if graph[i][j] == 1:
        dfs(i,j,0)

  print(res)

Submission status: Accepted

Solution code:
m, n, mat, tmp = 0, 0, 0, 0
ans = 0
printer = []
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
def main():
    while True:
        global m, n, mat, tmp, printer,ans
        ans = 0
        m, n = [int(input()) for _ in range(2)]
        if m == n == 0:
            break
        mat = [list(map(int, input().split())) for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if mat[i][j] == 1:
                    dfs(i, j, mat, 0)
        printer.append(ans)
    for i in range(len(printer)):
        print(printer[i])

def dfs(i, j, mat, c):
    global dx,dy,ans
    mat[i][j] = 0
    c += 1
    for k in range(4):
        if (0 <= i + dy[k] <= n - 1) and (0 <= j + dx[k] <= m - 1):
            if mat[i + dy[k]][j + dx[k]] == 1:
                dfs(i + dy[k], j + dx[k], mat, c)
    mat[i][j] = 1
    ans = max(ans,c)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
r=sys.stdin.readline
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:a=max(a,b(M,x-1,y,n+1))
  if M[x][y-1]:a=max(a,b(M,x,y-1,n+1))
  if M[x+1][y]:a=max(a,b(M,x+1,y,n+1))
  if M[x][y+1]:a=max(a,b(M,x,y+1,n+1))
  M[x][y]=1
  return a
 for e in iter(r,'0'):
  n,m=int(e),int(r())
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=map(int,r().split())
  print(max(b(P,i,j)for i in range(1,m+1)for j in range(1,n+1)if P[i][j]))
if'__main__'==__name__:s()

Submission status: Runtime Error

Solution code:
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:
   t=b(M,x-1,y,n+1)
   if a<t:a=t
  if M[x][y-1]:
   t=b(M,x,y-1,n+1)
   if a<t:a=t
  if M[x+1][y]:
   t=b(M,x+1,y1,n+1)
   if a<t:a=t
  if M[x][y+1]:
   t=b(M,x,y+1,n+1)
   if a<t:a=t
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(input())
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=map(int,input().split())
  print(max(b(P,i,j)for i in range(1,m+1)for j in range(1,n+1)if P[i][j]))
if'__main__'==__name__:s()

Submission status: Runtime Error

Solution code:
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:
   t=b(M,x-1,y,n+1)
   if a<t:a=t
  if M[x][y-1]:
   t=b(M,x,y-1,n+1)
   if a<t:a=t
  if M[x+1][y]:
   t=b(M,x+1,y+1,n+1)
   if a<t:a=t
  if M[x][y+1]:
   t=b(M,x,y+1,n+1)
   if a<t:a=t
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(input())
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=map(int,input().split())
  print(max(b(P,i,j)for i in range(1,m+1)for j in range(1,n+1)if P[i][j]))
if'__main__'==__name__:s()