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: Wrong Answer

Solution code:
from collections import deque
c = input()
r = input()
l = [map(int, raw_input().split()) for i in range(r)]
ans = 0
d = [(-1,0),(0,-1),(1,0),(0,1)]
for i in range(c):
    for j in range(r):
        q = deque()
        a = [[0]*c for x in range(r)]
        if l[j][i] == 0: continue
        a[j][i] = 1
        q.append((j,i))
        while len(q) != 0:
            cy, cx = q.popleft()
            for x, y in d:
                dx = x + cx; dy = y + cy;
                if 0<=dx<c and 0<=dy<r and a[dy][dx] == 0 and l[dy][dx] == 1:
                    q.append((dy, dx))
                    a[dy][dx] = a[cy][cx] + 1
        for i in range(c):
            for j in range(r):
                ans = max(ans, a[j][i])
print ans

Submission status: Wrong Answer

Solution code:
from collections import deque
while 1:
    c = input()
    r = input()
    if c == 0: break
    l = [map(int, raw_input().split()) for i in range(r)]
    ans = 0
    d = [(-1,0),(0,-1),(1,0),(0,1)]
    for i in range(c):
        for j in range(r):
            q = deque()
            a = [[True]*c for x in range(r)]
            if l[j][i] == 0: continue
            q.append((j,i,1))
            a[j][i] = False
            while len(q) != 0:
                cy, cx, cn = q.popleft()
                for x, y in d:
                    dx = x + cx; dy = y + cy;
                    if 0<=dx<c and 0<=dy<r and a[dy][dx] and l[dy][dx] == 1:
                        q.append((dy, dx, cn+1))
                        a[dy][dx] = False
                ans = max(ans, cn)
    print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""

"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def bfs(H, W, maze, sx, sy):
    # 幅優先探索で切手の切り取りパタンをチェックする
    ans = 1
    max_ans = 0
    # 上下左右に移動する場合の座標の変化量
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    Q = deque()
    Q.append((ans, sx, sy, maze))
    while Q:
        ans, cx, cy, maze = Q.popleft()        #  現在地の座標と探索状況
        for i in range(len(dx)):
            nx = cx + dx[i]
            ny = cy + dy[i]
            #  移動先まで通行可能 かつ 既に探索済でなければ、その先でも探索を続ける
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == 1:
                ans += 1
                max_ans = max(max_ans, ans)
                t = maze[:]
                t[ny][nx] = 0
                Q.append((ans, nx, ny, t))
    return max_ans


def solve(H, W, maze):
    # 全てのマスを起点にして、条件を満たす切り取り方をチェックする
    ans = 0
    for y in range(H):
        for x in range(W):
            if maze[y][x] == 1:
                t = bfs(H, W, maze, x, y) #  座標x, yを起点にした解の一覧
                ans = max(ans, t)
    return ans


def main(args):
    while True:
        W = int(input())
        H = int(input())
        if W == 0 and H == 0:
            break
        maze = []
        for _ in range(H):
            maze.append([int(x) for x in input().split()])
        ans = solve(H, W, maze)
        print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

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):
        if ices[x][y]:
          score[x][y] += (ices[x - 1][y] + ices[x + 1][y] + ices[x][y - 1] + ices[x][y + 1])
    
    def bfs(x, y, imap, acc):
      imap[x][y] = 0
      acc += 1
      flag = 0
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = bfs(x - 1, y, imap, acc)
        flag = 1
      if imap[x + 1][y]:
        b = bfs(x + 1, y, imap, acc)
        flag = 1
      if imap[x][y - 1]:
        c = bfs(x, y - 1, imap, acc)
        flag = 1
      if imap[x][y + 1]:
        d = bfs(x, y + 1, imap, acc)
        flag = 1
      if not flag:
        return acc
      return max(a, b, c, d)
    
    ans = 0
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        if score[x][y] in [1, 2]:
          a = bfs(x, y, [[ices[i][j] for j in range(m + 2)] for i in range(n + 2)], 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()

Submission status: Wrong Answer

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(i, j)+1)
                used[i][j] = 0
    print(ans)

Submission status: Wrong Answer

Solution code:
while True:
    m = int(raw_input())
    n = int(raw_input())

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

    begin = [[False] * m for x in xrange(n)]

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

    # (stage, current position(x, y), current point)
    que = []
    for x in xrange(m):
        for y in xrange(n):
            if begin[y][x]:
                que.append((begin[:], (x, y), 1))

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

    ans = 0

    while que:
        stage = que.pop()
        for i in xrange(4):
            nx = dx[i] + stage[1][0]
            ny = dy[i] + stage[1][1]
            if 0 <= nx < m and 0 <= ny < n and stage[0][ny][nx]:
                field = stage[0][:]
                field[ny][nx] = False
                ans = max(ans, stage[2] + 1)
                que.append((field, (nx, ny), stage[2] + 1))

    print ans

Submission status: Wrong Answer

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]:
                search(x, y, 1)

    print ans

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
while 1:
    c = input()
    r = input()
    if c == 0: break
    l = [map(int, raw_input().split()) for i in range(r)]
    ans = 0
    d = [(-1,0),(0,-1),(1,0),(0,1)]
    for i in range(c):
        for j in range(r):
            q = deque()
            a = [[0]*c for x in range(r)]
            if l[j][i] == 0: continue
            a[j][i] = 1
            q.append((j,i))
            while len(q) != 0:
                cy, cx = q.popleft()
                for x, y in d:
                    dx = x + cx; dy = y + cy;
                    if 0<=dx<c and 0<=dy<r and a[dy][dx] == 0 and l[dy][dx] == 1:
                        q.append((dy, dx))
                        a[dy][dx] = a[cy][cx] + 1
            for i in range(c):
                for j in range(r):
                    ans = max(ans, a[j][i])
    print ans

Submission status: Time Limit Exceeded

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):
        if ices[x][y]:
          score[x][y] += (ices[x - 1][y] + ices[x + 1][y] + ices[x][y - 1] + ices[x][y + 1])
    
    def bfs(x, y, imap, acc):
#      print(x, y)
      imap[x][y] = 0
      acc += 1
      flag = 0
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = bfs(x - 1, y, [[imap[i][j] for j in range(m + 2)] for i in range(n + 2)], acc)
        flag = 1
      if imap[x + 1][y]:
        b = bfs(x + 1, y, [[imap[i][j] for j in range(m + 2)] for i in range(n + 2)], acc)
        flag = 1
      if imap[x][y - 1]:
        c = bfs(x, y - 1, [[imap[i][j] for j in range(m + 2)] for i in range(n + 2)], acc)
        flag = 1
      if imap[x][y + 1]:
        d = bfs(x, y + 1, [[imap[i][j] for j in range(m + 2)] for i in range(n + 2)], acc)
        flag = 1
      if not flag:
        return acc
      return max(a, b, c, d)
    
    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 = bfs(x, y, [[ices[i][j] for j in range(m + 2)] for i in range(n + 2)], 0)
          #a = bfs(x, y, ices, 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

while True:
    m = int(raw_input())
    n = int(raw_input())

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

    begin = [[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:
                begin[y][x] = True

    # (stage, current position(x, y), current point)
    que = []
    for x in xrange(m):
        for y in xrange(n):
            if begin[y][x]:
                stage = deepcopy(begin)
                stage[y][x] = False
                que.append((stage, (x, y), 1))


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

    ans = 0

    while que:
        stage = que.pop()
        for i in xrange(4):
            nx = dx[i] + stage[1][0]
            ny = dy[i] + stage[1][1]
            if 0 <= nx < m and 0 <= ny < n and stage[0][ny][nx]:
                field = deepcopy(stage[0])
                field[ny][nx] = False
                ans = max(ans, stage[2] + 1)
                que.append((field, (nx, ny), stage[2] + 1))

    print ans

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from array import array

while True:
    m = int(raw_input())
    n = int(raw_input())

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

    begin = [array('b', [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:
                begin[y][x] = True

    # (stage, current position(x, y), current point)
    que = []
    for x in xrange(m):
        for y in xrange(n):
            if begin[y][x]:
                stage = deepcopy(begin)
                stage[y][x] = False
                que.append((stage, (x, y), 1))


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

    ans = 0

    while que:
        stage = que.pop()
        for i in xrange(4):
            nx = dx[i] + stage[1][0]
            ny = dy[i] + stage[1][1]
            if 0 <= nx < m and 0 <= ny < n and stage[0][ny][nx]:
                field = deepcopy(stage[0])
                field[ny][nx] = False
                ans = max(ans, stage[2] + 1)
                que.append((field, (nx, ny), stage[2] + 1))

    print ans

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
dx=[0,0,1,-1]
dy=[1,-1,0,0]

def dfs(y,x):
    global cnt
    Ice_cp[y][x]=0
    cnt+=1
    for i in range(4):
        mx=x+dx[i]
        my=y+dy[i]
        if 0<=mx<m and 0<=my<n and Ice_cp[my][mx]==1:
            dfs(my,mx)
            if Ice_cp[y][x]==0:
                return cnt
    return cnt

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 i in range(n):
        for j in range(m):
            cnt=0
            Ice_cp=deepcopy(Ice)
            if Ice_cp[i][j]==1:
                maxInt=max(maxInt,dfs(i,j))
    print maxInt

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
dx=[0,0,1,-1]
dy=[1,-1,0,0]

def dfs(y,x,cnt):
    Ice_cp[y][x]=0
    cnt+=1
    for i in range(4):
        mx=x+dx[i]
        my=y+dy[i]
        if 0<=mx<m and 0<=my<n and Ice_cp[my][mx]==1:
            return dfs(my,mx,cnt)
    return cnt

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 i in range(n):
        for j in range(m):
            cnt=0
            Ice_cp=deepcopy(Ice)
            if Ice_cp[i][j]==1:
                maxInt=max(maxInt,dfs(i,j,cnt))
    print maxInt

Submission status: Accepted

Solution code:
while 1:
    c = input()
    r = input()
    if c == 0: break        
    l = [map(int, raw_input().split()) for i in range(r)]
    ans = 0
    d = [(-1,0),(0,-1),(1,0),(0,1)]
    def dfs(j, i, cnt):
        global ans
        ans = max(ans, cnt)
        for x, y in d:
            dx = x + i; dy = y + j
            if 0<=dx<c and 0<=dy<r and l[dy][dx]:
                l[dy][dx] = False
                dfs(dy, dx, cnt+1)
                l[dy][dx] = True
    for i in range(c):
        for j in range(r):
            if l[j][i]:
                l[j][i] = False
                dfs(j,i,1)
                l[j][i] = True
    print ans

Submission status: Accepted

Solution code:
def breaking(a,x,y,n):
    a[x][y] = 0;
    answer = n
    if a[x-1][y]:
        answer = max(breaking(a,x-1,y,n+1),answer)
    if a[x][y-1]:
        answer = max(breaking(a,x,y-1,n+1),answer)
    if a[x+1][y]:
        answer = max(breaking(a,x+1,y,n+1),answer)
    if a[x][y+1]:
        answer = max(breaking(a,x,y+1,n+1),answer)
    a[x][y] = 1
    return answer

while True:
    n = int(input())
    if n==0: break
    m = int(input())

    mapp = [[0]*(n+2) for i in range(m+2)]
    for i in range(m):
        ainarray = list(map(int,input().split()))
        for j in range(n):
            mapp[i+1][j+1] = ainarray[j]

    res = 0
    for i in range(m):
        for j in range(n):
            if mapp[i+1][j+1]:
                res = max(res,breaking(mapp,i+1,j+1,1))

    print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""

"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def bfs(H, W, maze, sx, sy):
    max_ans = 1
    # 上下左右に移動する場合の座標の変化量
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    path = [(sx, sy)]           #  切り取りに含める切手の座標 (まずは探索開始地点のみからスタート)
    Q = deque()
    Q.append((sx, sy, path))
    while Q:
        cx, cy, path = Q.popleft()        #  現在地の座標と探索状況
        for i in range(len(dx)):
            nx = cx + dx[i]
            ny = cy + dy[i]
            #  移動先まで通行可能 かつ 既に探索済でなければ、その先でも探索を続ける
            if 0 <= nx < W and 0 <= ny < H and not (nx, ny) in path and maze[ny][nx] == 1:
                t = path[:]
                t.append((nx, ny))
                ans = len(t)
                if ans > max_ans:
                    max_ans = ans
                Q.append((nx, ny, t[:]))
    return max_ans


def solve(H, W, maze):
    # 全てのマスを起点にして、条件を満たす切り取り方をチェックする
    ans = 0
    for y in range(H):
        for x in range(W):
            if maze[y][x] == 1:
                t = bfs(H, W, maze, x, y) #  座標x, yを起点にした解の一覧
                ans = max(ans, t)
    return ans


def main(args):
    while True:
        W = int(input())
        H = int(input())
        if W == 0 and H == 0:
            break
        maze = []
        for _ in range(H):
            maze.append([int(x) for x in input().split()])
        ans = solve(H, W, maze)
        print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def b(M,x,y,n=1):
 M[x][y]='0';t=[]
 if'1'==M[x-1][y]:t+=[b(M,x-1,y,n+1)]
 if'1'==M[x][y-1]:t+=[b(M,x,y-1,n+1)]
 if'1'==M[x+1][y]:t+=[b(M,x+1,y,n+1)]
 if'1'==M[x][y+1]:t+=[b(M,x,y+1,n+1)]
 M[x][y]='1'
 return max([n]+t)
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]=input().split()
 print(max(b(P,i,j)for i in range(1,m+1)for j in range(1,n+1)if'1'==P[i][j]))

Submission status: Accepted

Solution code:
def b(M,x,y,n=1):
 M[x][y]=0;t=[]
 if M[x-1][y]:t+=[b(M,x-1,y,n+1)]
 if M[x][y-1]:t+=[b(M,x,y-1,n+1)]
 if M[x+1][y]:t+=[b(M,x+1,y,n+1)]
 if M[x][y+1]:t+=[b(M,x,y+1,n+1)]
 M[x][y]=1
 return max([n]+t)
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]))

Submission status: Accepted

Solution code:
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(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]))

Submission status: Accepted

Solution code:
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(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: Accepted

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'):
  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: Accepted

Solution code:
def s():
 def b(M,x,y,n=0):
  if M[x][y]==0:return n
  M[x][y]=0
  a=max(b(M,x-1,y,n+1),b(M,x,y-1,n+1),b(M,x+1,y,n+1),b(M,x,y+1,n+1))
  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'__main__'==__name__:s()

Submission status: Accepted

Solution code:
def s():
 def b(M,x,y,n=0):
  if M[x][y]==0:return n
  M[x][y]=0
  a=max(b(M,x+s,y+t,n+1)for s,t in[(-1,0),(0,-1),(1,0),(0,1)])
  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'__main__'==__name__:s()

Submission status: Accepted

Solution code:
def s():
 def b(M,x,y,n):
  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(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,1)for i in range(1,m+1)for j in range(1,n+1)if P[i][j]))
if'__main__'==__name__:s()

Submission status: Accepted

Solution code:
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(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: Accepted

Solution code:
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(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: Accepted

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,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: Accepted

Solution code:
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  for p,q in[(-1,0),(0,-1),(1,0),(0,1)]:
   if M[x+p][y+q]:
    t=b(M,x+p,y+q,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: Accepted

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,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())
  a=0
  for i in range(1,m+1):
   for j in range(1,n+1):
    if P[i][j]:
     t=b(P,i,j)
     if a<t:a=t
  print(a)
if'__main__'==__name__:s()

Submission status: Accepted

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,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())
  a=0
  for i in range(1,m+1):
   for j in range(1,n+1):
    if P[i][j]:
     t=b(P,i,j)
     if a<t:a=t
  print(a)
if'__main__'==__name__:s()

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):
        if ices[x][y]:
          score[x][y] += (ices[x - 1][y] + ices[x + 1][y] + ices[x][y - 1] + ices[x][y + 1])
    
    def bfs(x, y, imap, acc):
      imap[x][y] = 0
      acc += 1
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = bfs(x - 1, y, imap, acc)
      if imap[x + 1][y]:
        b = bfs(x + 1, y, imap, acc)
      if imap[x][y - 1]:
        c = bfs(x, y - 1, imap, acc)
      if imap[x][y + 1]:
        d = bfs(x, y + 1, imap, acc)
      imap[x][y] = 1
      return max(acc, a, b, c, d)
    
    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 = bfs(x, y, ices, 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()

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):
#        if ices[x][y]:
#          score[x][y] += (ices[x - 1][y] + ices[x + 1][y] + ices[x][y - 1] + ices[x][y + 1])
    
    def bfs(x, y, imap, acc):
      imap[x][y] = 0
      acc += 1
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = bfs(x - 1, y, imap, acc)
      if imap[x + 1][y]:
        b = bfs(x + 1, y, imap, acc)
      if imap[x][y - 1]:
        c = bfs(x, y - 1, imap, acc)
      if imap[x][y + 1]:
        d = bfs(x, y + 1, imap, acc)
      imap[x][y] = 1
      return max(acc, a, b, c, d)
    
    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]:
        if ices[x][y]:
          a = bfs(x, y, ices, 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()

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):
        if ices[x][y]:
          score[x][y] += (ices[x - 1][y] + ices[x + 1][y] + ices[x][y - 1] + ices[x][y + 1])
    
    def bfs(x, y, imap, acc):
      imap[x][y] = 0
      acc += 1
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = bfs(x - 1, y, imap, acc)
      if imap[x + 1][y]:
        b = bfs(x + 1, y, imap, acc)
      if imap[x][y - 1]:
        c = bfs(x, y - 1, imap, acc)
      if imap[x][y + 1]:
        d = bfs(x, y + 1, imap, acc)
      imap[x][y] = 1
      return max(acc, a, b, c, d)
    
    ans = 0
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        if score[x][y] in [1, 2]:
          a = bfs(x, y, ices, 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()

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):
        if ices[x][y]:
          score[x - 1][y] += 1
          score[x + 1][y] += 1
          score[x][y - 1] += 1
          score[x][y + 1] += 1
    
    def bfs(x, y, imap, acc):
      imap[x][y] = 0
      acc += 1
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = bfs(x - 1, y, imap, acc)
      if imap[x + 1][y]:
        b = bfs(x + 1, y, imap, acc)
      if imap[x][y - 1]:
        c = bfs(x, y - 1, imap, acc)
      if imap[x][y + 1]:
        d = bfs(x, y + 1, imap, acc)
      imap[x][y] = 1
      return max(acc, a, b, c, d)
    
    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 = bfs(x, y, ices, 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()

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):
        if ices[x][y]:
          score[x - 1][y] += 1
          score[x + 1][y] += 1
          score[x][y - 1] += 1
          score[x][y + 1] += 1
    
    def search(x, y, imap, acc):
      imap[x][y] = 0
      acc += 1
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = search(x - 1, y, imap, acc)
      if imap[x + 1][y]:
        b = search(x + 1, y, imap, acc)
      if imap[x][y - 1]:
        c = search(x, y - 1, imap, acc)
      if imap[x][y + 1]:
        d = search(x, y + 1, imap, acc)
      imap[x][y] = 1
      return max(acc, a, b, c, d)
    
    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 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
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = search(x - 1, y, imap, acc)
      if imap[x + 1][y]:
        b = search(x + 1, y, imap, acc)
      if imap[x][y - 1]:
        c = search(x, y - 1, imap, acc)
      if imap[x][y + 1]:
        d = search(x, y + 1, imap, acc)
      imap[x][y] = 1
      return max(acc, a, b, c, d)
    
    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()