TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
from collections import deque
 
H, W = map(int, input().split())
S = [input() for _ in range(H)]
INF = 10**15

answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      continue
    else:
      dist = [[INF for _ in range(W)] for _ in range(H)] 
      dist[i][j] = 0 
      stack = deque([(i, j)]) 
      
      while stack:
      # BFS
      
      si, sj = stack.popleft() 
        
        
        
        
        for ni, nj in [(si + 1, sj), (si - 1, sj), (si, sj + 1), (si, sj - 1)]:
        
        
        
        
        
        
        
        
          if 0 <= ni <= H - 1 and 0 <= nj <= W - 1 and S[ni][nj] != "#":
            if dist[ni][nj] > dist[si][sj] + 1:
              dist[ni][nj] = dist[si][sj] + 1
              stack.append((ni, nj))
          
          
              
              
      max_dist = 0
      for ii in range(H):
        for jj in range(W):
          if dist[ii][jj] != INF:
            max_dist = max(max_dist, dist[ii][jj])
      answer = max(max_dist, answer)
      
      
print(answer)

from collections import deque
 
H, W = map(int, input().split())
S = [input() for _ in range(H)]
INF = 10**15

answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      continue
    else:
      dist = [[INF for _ in range(W)] for _ in range(H)] 
      dist[i][j] = 0 
      stack = deque([(i, j)]) 
      
      while stack:
      # BFS
      
        si, sj = stack.popleft() 
        
        
        
        
        for ni, nj in [(si + 1, sj), (si - 1, sj), (si, sj + 1), (si, sj - 1)]:
        
        
        
        
        
        
        
        
          if 0 <= ni <= H - 1 and 0 <= nj <= W - 1 and S[ni][nj] != "#":
            if dist[ni][nj] > dist[si][sj] + 1:
              dist[ni][nj] = dist[si][sj] + 1
              stack.append((ni, nj))
          
          
              
              
      max_dist = 0
      for ii in range(H):
        for jj in range(W):
          if dist[ii][jj] != INF:
            max_dist = max(max_dist, dist[ii][jj])
      answer = max(max_dist, answer)
      
      
print(answer)

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
from collections import deque
import pprint
import numpy as np

h, w = map(int, input().split())
maze = [['*']*(w+2) for j in range(h+2)]
for i in range(1,h+1):
    maze[i][1:] = map(str,list(input()))
    maze[i].append('*')

score = []
def bfs(maze):
    for i in range(1,h+1):
        for l in range(1,w+1):
            if i == '#' or j == '#':
                continue
            visited = [[-1]*(w+1) for j in range(h+1)]
            queue = deque()
            queue.append([i, l])
            visited[i][l] = 0
            while(queue):
                y, x = queue.popleft()
                for j,k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                    new_x, new_y = x+j, y+k
                    if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
                        queue.append([new_y, new_x])
                        visited[new_y][new_x] = visited[y][x] + 1
            idx = np.unravel_index(np.argmax(np.array(visited)), np.array(visited).shape)
            score.append(np.array(visited)[idx])
    return (max(score))

print(bfs(maze))


from collections import deque
import pprint
import numpy as np

h, w = map(int, input().split())
maze = [['*']*(w+2) for j in range(h+2)]
for i in range(1,h+1):
    maze[i][1:] = map(str,list(input()))
    maze[i].append('*')

score = []
def bfs(maze):
    for i in range(1,h+1):
        for l in range(1,w+1):
            if maze[i][l] == '#':
                continue
            visited = [[-1]*(w+1) for j in range(h+1)]
            queue = deque()
            queue.append([i, l])
            visited[i][l] = 0
            while(queue):
                y, x = queue.popleft()
                for j,k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                    new_x, new_y = x+j, y+k
                    if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
                        queue.append([new_y, new_x])
                        visited[new_y][new_x] = visited[y][x] + 1
            idx = np.unravel_index(np.argmax(np.array(visited)), np.array(visited).shape)
            score.append(np.array(visited)[idx])
    return (max(score))

print(bfs(maze))


Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
H, W = map(int,input().split())
grid = [list(input().split()) for _ in H]
res = 0
def bfs(tup,visited):
  def helper(tup, total):
    if tup in visited():
      res = max(res, total)
    elif tup[0]>=H or tup[0] < 0 or tup[1]>=W or tup[1]<0 or grid[tup[0]][tup[1]]:
      res = max(res, total)
    else:
      visited.add(tup)
      h, w = tup
      helper((h+1, w),total+1)
      helper((h-1, w),total+1)
      helper((h, w-1),total+1)
      helper((h, w+1),total+1)
  helper(tup,0)
  return res
      
ans = 0
for h in H:
  for w in W:
    if grid[h][w] == '#':
      continue
    ans = max(ans,bfs((h,w),set()))
print(ans)

from collections import deque
import numpy as np

H,W = map(int,input().split())
maze = [input() for _ in range(H)]

ans = 0
for x in range(H):
    for y in range(W):
        
        if maze[x][y] == "#":
            continue

        distance = [[-1]*W for _ in range(H)]
        distance[x][y] = 0
        
        stack = deque([[x,y]])

        while stack:
            h,w = stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h, new_w = h+i, w+j
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue
                elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == -1:
                    distance[new_h][new_w] = distance[h][w]+1
                    stack.append([new_h, new_w])

        ans = max(ans, np.max(distance))

print(ans)

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
from collections import deque

H, W = map(int, input().split())

S = [['#'] * (W+2)]
for _ in range(H):
  tmp = ['#'] + list(input()) + ['#']
  S.append(tmp)
S.append(['#'] * (W+2))

move = [[1,0], [-1,0], [0,1], [0,-1]]

ans = 0
for X in range(1, H+1):
  for Y in range(1, W+1):
    if S[x][Y] == '#':
      continue
    check = [[-1] * (W+2) for _ in range(H+2)]
    check[X][Y] = 0
    que = deque()
    que.append([X, Y])
    while que:
      tmp = que.popleft()
      x = tmp[0]
      y = tmp[1]
      flag = True
      for dx, dy in move:
        nx = x + dx
        ny = y + dy
        if S[nx][ny] == '.' and check[nx][ny] == -1:
          que.append([nx, ny])
          check[nx][ny] = check[x][y] + 1
          flag =False
      if flag:
        ans = max(ans, check[x][y])
print(ans)

from collections import deque

H, W = map(int, input().split())

S = [['#'] * (W + 2)]
for _ in range(H):
    tmp = ['#'] + list(input()) + ['#']
    S.append(tmp)
S.append(['#'] * (W + 2))


move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

ans = 0

for X in range(1, H + 1):
    for Y in range(1, W + 1):
        if S[X][Y] == '#':
            continue

        check = [[-1] * (W + 2) for _ in range(H + 2)]
        check[X][Y] = 0

        que = deque()
        que.append([X, Y])
        while que:
            tmp = que.popleft()
            x = tmp[0]
            y = tmp[1]
            flag = True
            for dx, dy in move:
                nx = x + dx
                ny = y + dy
                if S[nx][ny] == '.' and check[nx][ny] == -1:
                    que.append([nx, ny])
                    check[nx][ny] = check[x][y] + 1 
                    flag = False

            if flag:
                ans = max(ans, check[x][y])


print (ans)


Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
from collections import deque

h, w = map(int, input().split())

maze = [input() for i in range(h)]

ans = 0
INF = 20 * 20 + 1
for j in range(h):
    for i in range(w):
        if maze[j][i] == ".":
            cnt = [[INF] * w for _ in range(h)] 
            cnt[j][i] = 0
            q = deque([(j,i)])
            while q:
                y,x = q.popleft()
                for by,bx in ((0,1),(0,-1),(1,0),(-1,0)):
                    by += y
                    bx += x 
                    if 0 <= by < h and 0 <= bx < w:
                        ct = cnt[y][x] + 1
                        if maze[ny][nx] == "." and ct < cnt[ny][nx]:
                            q += [(by,bx)] 
                            cnt[by][bx] = ct
                            ans = max(ans, cnt[by][bx])

print(ans)

from collections import deque

h, w = map(int, input().split())

maze = [input() for i in range(h)]

ans = 0
INF = 20 * 20 + 1
for j in range(h):
    for i in range(w):
        if maze[j][i] == ".":
            cnt = [[INF] * w for _ in range(h)] 
            cnt[j][i] = 0
            q = deque([(j,i)])
            while q:
                y,x = q.popleft()
                for by,bx in ((0,1),(0,-1),(1,0),(-1,0)):
                    by += y
                    bx += x 
                    if 0 <= by < h and 0 <= bx < w:
                        ct = cnt[y][x] + 1
                        if maze[by][bx] == "." and ct < cnt[by][bx]:
                            q += [(by,bx)] 
                            cnt[by][bx] = ct
                            ans = max(ans, cnt[by][bx])

print(ans)

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
h,w = map(int,input().split())
from copy import deepcopy
from collections import deque
a = [input().split() for l in range(h)]
c = [[None for i in range(w)]for j in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            c[i][j] = -1
ans = 0
g = deque()
for l in range(h):
    for k in range(w):
        b = deepcopy(c)
        if a[l][k] == '.':
            b[l][k] = 0
            g.append((l,k))
            while len(g)>0:
                i,j = g.popleft()
                dis = b[i][j] 
                for dx,dy in ((1,0),(0,1),(-1,0), (0,-1)):
                    newi = i + dx
                    newj = j +dy
                    if newi < 0 or newi > h-1 or newj < 0 or newj > w-1:
                        continue
                    if b[newi][newj] == -1:
                        b[newi][newj] = dis + 1
                        ans = max(ans,dis+1)
                        g.append((newi,newj))
print(ans)
                 

h,w = map(int,input().split())
from copy import deepcopy
from collections import deque
a = [list(input()) for l in range(h)]
c = [[None for i in range(w)]for j in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            c[i][j] = -1
ans = 0
g = deque()
for l in range(h):
    for k in range(w):
        b = deepcopy(c)
        if a[l][k] == '.':
            b[l][k] = 0
            g.append((l,k))
            while len(g)>0:
                i,j = g.popleft()
                dis = b[i][j] 
                for dx,dy in ((1,0),(0,1),(-1,0), (0,-1)):
                    newi = i + dx
                    newj = j +dy
                    if newi < 0 or newi > h-1 or newj < 0 or newj > w-1:
                        continue
                    if b[newi][newj] == -1:
                        b[newi][newj] = dis + 1
                        ans = max(ans,dis+1)
                        g.append((newi,newj))
print(ans)

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
from collections import deque

H, W = map(int, input().split())

H += 2
W += 2

grid = "#" * W
for _ in range(H - 2):
    grid += "#" + input().split()
grid += "#" * W


def bfs(start):
    INF = 10 * 9
    dist = [INF] * (H * W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1, 1, W, -W):
            # next place
            w = v + move
            # wall or not
            if grid[w] == "#":
                continue

            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)

    return max(x for x in dist if x < INF)


answer = max(bfs(v) for v in range(H * W) if grid[v] != "#")
print(answer)


from collections import deque

H, W = map(int, input().split())
maze = [input() for _ in range(H)]


def bfs(maze, visited, sh, sw, H, W):
    q = deque([(sh, sw)])
    visited[sh][sw] = 0
    M = 0
    while q:
        h, w = q.popleft()
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if maze[nh][nw] == "." and visited[nh][nw] == -1:
                    visited[nh][nw] = visited[h][w] + 1
                    q.append((nh, nw))
                    if visited[nh][nw] > M:
                        M = visited[nh][nw]

    return M


ans = 0
for h in range(H):
    for w in range(W):
        if maze[h][w] == "#":
            continue
        visited = [[-1] * W for _ in range(H)]
        tmp = bfs(maze, visited, h, w, H, W)
        if tmp > ans:
            ans = tmp
print(ans)


Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
from collections import deque
h, w = map(int, input().split())
square = [list(input()) for i in range(h)]
INF = 100
def bfs(si, sj):
    que = deque([(si, sj)])
    d = [[INF] * w for i in range(h)]
    d[si][sj] = 0
    move = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    while que:
        i, j = que.popleft()
        for mi, mj in move:
            ni, nj = i + mi, j + mj
            if 0 <= ni < h and 0 <= nj < w and square[ni][nj] = '.' and d[ni][nj] == INF:
                que.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

max_num = 0
for i in range(h):
    for j in range(w):
        if square[i][j] == '.':
            max_ij = bfs(i, j)
            max_num = max(max_num, max_ij)
print(max_num)

from collections import deque
h, w = map(int, input().split())
s = [input() for i in range(h)]
def bfs(i0, j0):
    INF = 100
    search = deque([(i0, j0)])
    d = [[INF] * w for i in range(h)]
    d[i0][j0] = 0
    while search:
        i, j = search.popleft()
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.' and d[ni][nj] == INF:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

max_d = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            max_dij = bfs(i, j)
            max_d = max(max_d, max_dij)
print(max_d)

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
print(38)

print(1)

import queue

h,w=map(int,input().split())

s=[]
for _ in range(h):
    s.append(input())

ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            seen=[[0 for _ in range(w)] for _ in range(h)]
            length=[[0 for _ in range(w)] for _ in range(h)]
            q=queue.Queue()
            q.put([i,j])
            seen[i][j]=1
            while not q.empty():
                ci,cj=q.get()
                for ni,nj in [[ci-1,cj],[ci+1,cj],[ci,cj-1],[ci,cj+1]]:
                    if 0<=ni<h and 0<=nj<w and s[ni][nj]=="." and seen[ni][nj]==0:
                        q.put([ni,nj])
                        length[ni][nj]=length[ci][cj]+1
                        seen[ni][nj]=1
            ans=max(ans,length[ci][cj])

print(ans)

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
import numpy as np
import queue
H,W=map(int,input().split())
S=list()
for m in range(H):
  S.append(input())
ans=0
i,j=7,6
if S[i][j]==".":
    L=[[-1]*W for i in range(H)]
    L[i][j]=0
    q=queue.Queue()
    q.put([i,j])
    while not q.empty():
      r=q.get()
      for k,l in [[1,0],[0,-1],[0,1],[-1,0]]:
        if r[0]+k>=0 and r[0]+k<H and r[1]+l>=0 and r[1]+l<W and S[r[0]+k][r[1]+l]=="." and L[r[0]+k][r[1]+l]==-1:
          L[r[0]+k][r[1]+l]=L[r[0]][r[1]]+1
          q.put([r[0]+k,r[1]+l])
    ans=max(ans,max(list(map(lambda x: max(x),L))))
print(ans)

import numpy as np
import queue
H,W=map(int,input().split())
S=list()
for i in range(H):
  S.append(input())
ans=0
  
for i in range(H):
  for j in range(W):
    if S[i][j]==".":
      L=[[-1]*W for i in range(H)]
      q=queue.Queue()
      q.put([i,j])
      while not q.empty():
        r=q.get()
        for k,l in [[1,0],[0,-1],[0,1],[-1,0]]:
          if r[0]+k>=0 and r[0]+k<H and r[1]+l>=0 and r[1]+l<W and S[r[0]+k][r[1]+l]=="." and L[r[0]+k][r[1]+l]==-1:
            L[r[0]+k][r[1]+l]=L[r[0]][r[1]]+1
            q.put([r[0]+k,r[1]+l])
      if max(max(L))>ans:
        ans=max(max(L))
print(ans)

import numpy as np
import queue
H,W=map(int,input().split())
S=list()
for i in range(H):
  S.append(input())
ans=0
  
for i in range(H):
  for j in range(W):
    if S[i][j]==".":
      L=[[-1]*W for i in range(H)]
      L[i][j]=0
      q=queue.Queue()
      q.put([i,j])
      while not q.empty():
        r=q.get()
        for k,l in [[1,0],[0,-1],[0,1],[-1,0]]:
          if r[0]+k>=0 and r[0]+k<H and r[1]+l>=0 and r[1]+l<W and S[r[0]+k][r[1]+l]=="." and L[r[0]+k][r[1]+l]==-1:
            L[r[0]+k][r[1]+l]=L[r[0]][r[1]]+1
            q.put([r[0]+k,r[1]+l])
      ans=max(ans,max(list(map(lambda x:max(x),L))))
print(ans)


Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
from collections import deque
n,m = map(int,input().split())
l = []
for i in range(n):
    a = list(input())
    l.append(a)
print(l[0][1])
ans = 0
for i in range(n):
    for j in range(m):
        if l[i][j] == ".":
            bfs = [[-1]*m for k in range(n)]
            bfs[i][j] = 0
            q = deque([])
            q.append((i,j))
            dx = [0,0,-1,1]
            dy = [-1,1,0,0]
            while q:
                x,y = q.popleft()

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

                    if 0 <= nx < n and 0 <= ny < m and bfs[nx][ny] == -1 and l[nx][ny] != "#":
                        q.append((nx,ny))
                        bfs[nx][ny] = bfs[x][y] +1

            for bf in bfs:
                ans = max(ans,max(bf))
            
print(ans)


from collections import deque
n,m = map(int,input().split())
l = []
for i in range(n):
    a = list(input())
    l.append(a)

ans = 0
for i in range(n):
    for j in range(m):
        if l[i][j] == ".":
            bfs = [[-1]*m for k in range(n)]
            bfs[i][j] = 0
            q = deque([])
            q.append((i,j))
            dx = [0,0,-1,1]
            dy = [-1,1,0,0]
            while q:
                x,y = q.popleft()

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

                    if 0 <= nx < n and 0 <= ny < m and bfs[nx][ny] == -1 and l[nx][ny] != "#":
                        q.append((nx,ny))
                        bfs[nx][ny] = bfs[x][y] +1

            for bf in bfs:
                ans = max(ans,max(bf))
            
print(ans)


Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
import math
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(str(input()))
d = [[float('inf') for i in range(V)] for j in range(V)]
  
  

import math
import sys
sys.setrecursionlimit(10000)
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(str(input()))
  
def main(l, d, cnt):
  tmp = []
  for n in l:
    i, j = n[0], n[1]
    if (0<i) and (S[i-1][j] == '.'):
      if d[i-1][j] > d[i][j]+1:
        d[i-1][j] = d[i][j]+1
        tmp.append([i-1, j])
    if (i<H-1) and (S[i+1][j] == '.'):
      if d[i+1][j] > d[i][j]+1:
        d[i+1][j] = d[i][j]+1
        tmp.append([i+1, j])
    if (0<j) and (S[i][j-1] == '.'):
      if d[i][j-1] > d[i][j]+1:
        d[i][j-1] = d[i][j]+1
        tmp.append([i, j-1])
    if (j<W-1) and (S[i][j+1] == '.'):
      if d[i][j+1] > d[i][j]+1:
        d[i][j+1] = d[i][j]+1
        tmp.append([i, j+1])
  if tmp == []:
    return cnt
  else:
    cnt += 1
    return main(tmp, d, cnt)
  
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '.':
      d = [[float('inf') for i in range(W)] for j in range(H)]
      d[i][j] = 0
      cnt = main([[i, j]], d, 0)
      ans = max(ans, cnt)
print(ans)

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
H, W = map(int, input().split())
S = [input().split() for _ in range(H)]

from collections import deque

def bfs(sy, sx):
    q = deque([[sy, sx]])
    visited = [[-1]*W for _ in range(H)]
    visited[sy][sx] = 0
    while q:
        y, x = q.popleft()
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+i, x+j
            if not 0 <= new_y < H or not 0 <= new_x < W:
                continue
            if S[new_y][new_x] ==  "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x]+1
                q.append([new_y, new_x])
    return max(max(l) for l in visited)

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ans = max(ans, bfs(i, j))
print (ans)

H, W = map(int, input().split())
S = [input() for _ in range(H)]

from collections import deque

def bfs(sy, sx):
    q = deque([[sy, sx]])
    visited = [[-1]*W for _ in range(H)]
    visited[sy][sx] = 0
    while q:
        y, x = q.popleft()
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+i, x+j
            if not 0 <= new_y < H or not 0 <= new_x < W:
                continue
            if S[new_y][new_x] ==  "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x]+1
                q.append([new_y, new_x])
    return max(max(l) for l in visited)

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ans = max(ans, bfs(i, j))
print (ans)

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):

from collections import deque
def check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False

count=0
def bfs():
    while (q):
        x,y,count=q.popleft()
        
        if check(x,y)==False or (x,y) in finished or c[x][y]=='#':
            continue

        else:
            q.append([x,y-1,count+1])
            q.append([x,y+1,count+1])
            q.append([x+1,y,count+1])
            q.append([x-1,y,count+1])
            finished.add((x,y))
            bfscount.append(count)

    return max(bfscount)

q = deque()
h,w=map(int,input().split())
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))
ans=[]
bfscount=[]
for i in range(h):
    for j in range(w):
        if c[i][j]==".":
            q.append([i,j,0])
            ans.append(bfs())
            finished = set()
            bfscount=[]
print(ans)
print(max(ans))



from collections import deque
def check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False

count=0
def bfs():
    while (q):
        x,y,count=q.popleft()
        
        if check(x,y)==False or (x,y) in finished or c[x][y]=='#':
            continue

        else:
            q.append([x,y-1,count+1])
            q.append([x,y+1,count+1])
            q.append([x+1,y,count+1])
            q.append([x-1,y,count+1])
            finished.add((x,y))
            bfscount.append(count)

    return max(bfscount)

q = deque()
h,w=map(int,input().split())
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))
ans=[]
bfscount=[]
for i in range(h):
    for j in range(w):
        if c[i][j]==".":
            q.append([i,j,0])
            ans.append(bfs())
            finished = set()
            bfscount=[]
print(max(ans))


Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                    map[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    map[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    map[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    map[y][x - 1] = "a"
print(MAX)


import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            maps[i][l] = "a"
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                    maps[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    maps[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    maps[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    maps[y][x - 1] = "a"
print(MAX)


Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
from collections import deque

H,W=map(int,input().split())
S=[]
for i in range(H):
  S.append(input())
  
def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  total = [[0 for i in range(W)] for j in range(H)]
  todo = deque([])
  if s <= H-1:now = (s,0)
  else:now = (H-1,s-H+1)
  if S[now[0]][now[1]]=='#':return 0
  seen[now[0]][now[1]],total[now[0]][now[1]] = 1,0
  todo.append(now)
  while 1:
    if len(todo)==0:break
    now = todo.popleft()
    for d in [(1,0),(-1,0),(0,1),(0,-1)]:
      new = (now[0]+d[0], now[1]+d[1])
      if new[0]<0 or new[0]>=H:continue
      if new[1]<0 or new[1]>=W:continue
      if seen[new[0]][new[1]]==1:continue
      if S[new[0]][new[1]]=='#':continue
      seen[new[0]][new[1]] = 1
      todo.append(new)
      total[new[0]][new[1]] = total[now[0]][now[1]] + 1
  return max(map(max, total))

MAX=0
for s in range(H+W-1):
  max_ = bfs(s)
  print(s,max_)
  if MAX < max_:MAX=max_

print(MAX)

from collections import deque

H,W=map(int,input().split())
S=[]
for i in range(H):
  S.append(input())
  
def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  total = [[0 for i in range(W)] for j in range(H)]
  todo = deque([])
  now = s
  if S[now[0]][now[1]]=='#':return 0
  seen[now[0]][now[1]],total[now[0]][now[1]] = 1,0
  todo.append(now)
  while 1:
    if len(todo)==0:break
    now = todo.popleft()
    for d in [(1,0),(-1,0),(0,1),(0,-1)]:
      new = (now[0]+d[0], now[1]+d[1])
      if new[0]<0 or new[0]>=H:continue
      if new[1]<0 or new[1]>=W:continue
      if seen[new[0]][new[1]]==1:continue
      if S[new[0]][new[1]]=='#':continue
      seen[new[0]][new[1]] = 1
      todo.append(new)
      total[new[0]][new[1]] = total[now[0]][now[1]] + 1
  return max(map(max, total))

MAX=0
for i in range(H):
  for j in range(W):
    s = (i,j)
    max_ = bfs(s)
    if MAX < max_:MAX=max_

print(MAX)

Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
ab.append(list('#'*w))
mx = 0

for i in range(h):
    for j in range(w):
        dp = [[0 for i in range(w)] for j in range(h)]
        step = [[i, j]]

        while len(step) > 0:
            y, x = step.pop(0)
            if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
                step.append([y+1, x])
                dp[y+1][x] = dp[y][x] + 1
            if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
                step.append([y, x+1])
                dp[y][x+1] = dp[y][x] + 1
            if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
                step.append([y-1, x])
                dp[y-1][x] = dp[y][x] + 1
            if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
                step.append([y, x-1])
                dp[y][x-1] = dp[y][x] + 1
        mx = max([mx, max(list(itertools.chain.from_iterable(dp)))])

print(mx)

import itertools

import copy
    
h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
ab.append(list('#'*w))
mx = 0

for i in range(h):
    for j in range(w):
        if ab[i][j] == '.':
            dp = [[0 for a in range(w)] for b in range(h)]
            step = [[i, j]]

            while len(step) > 0:
                y, x = step.pop(0)
                if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
                    step.append([y+1, x])
                    dp[y+1][x] = dp[y][x] + 1
                if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
                    step.append([y, x+1])
                    dp[y][x+1] = dp[y][x] + 1
                if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
                    step.append([y-1, x])
                    dp[y-1][x] = dp[y][x] + 1
                if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
                    step.append([y, x-1])
                    dp[y][x-1] = dp[y][x] + 1
            dp[i][j] = 0
            mx = max([mx, max(list(itertools.chain.from_iterable(dp)))])

print(mx)

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
from collections import deque
import numpy as np
h, w = map(int,input().split())
s = [input() for _ in range(h)]
result = []
for xx in range(h):
    for yy in range(w):
        if s[xx][yy]==".":
            visit = np.array([np.array([-1 for _ in range(w)]) for __ in range(h)])
            visit[xx][yy] = 0

            q = deque([[xx,yy]])
            while q:
                x, y = q.pop()
                for i in [-1, 1]:
                    if 0 <= x+i and x+i < h:
                        if s[x+i][y] != "#" and visit[x+i][y] < 0:
                            visit[x+i][y] = visit[x][y]+1
                            q.append([x+i, y])
                    if 0 <= y+i and y+i < w:
                        if s[x][y+i] != "#" and visit[x][y+i] < 0:
                            visit[x][y+i] = visit[x][y]+1
                            q.append([x, y+i])
            result.append(max(visit.flatten()))
print(max(result))

from collections import deque
h, w = map(int,input().split())
s = [input() for _ in range(h)]
result = []
for xx in range(h):
    for yy in range(w):
        if s[xx][yy]==".":
            visit = [[-1 for _ in range(w)] for __ in range(h)]
            visit[xx][yy] = 0

            q = deque([[xx,yy]])
            while q:
                x, y = q.popleft()
                for i in [-1, 1]:
                    if 0 <= x+i and x+i < h:
                        if s[x+i][y] != "#" and visit[x+i][y] < 0:
                            visit[x+i][y] = visit[x][y]+1
                            q.append([x+i, y])
                    if 0 <= y+i and y+i < w:
                        if s[x][y+i] != "#" and visit[x][y+i] < 0:
                            visit[x][y+i] = visit[x][y]+1
                            q.append([x, y+i])
            result.append(max([max(i) for i in visit]))
print(max(result))

Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
n, m = map(int, input().split())
ar = []
for i in range(n):
    ar.append(list(input()))

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


def recursion(x, y, vis):
    ans = 0
    for k in range(4):
        x1 = x + dx[k]
        y1 = y + dy[k]

        if 0 <= x1 < n and 0 <= y1 < m and ar[x1][y1] == '.' and vis[x1][y1] == 0:
            vis[x1][y1] = 1
            ans = max(ans, 1 + recursion(x1, y1, vis))
    return ans


res = 0
for i in range(n):
    for j in range(m):
        if ar[i][j] == '.':
            vis = [[0] * m for k in range(n)]
            res = max(res, recursion(i, j, vis))

print(res)

n, m = map(int, input().split())
ar = []
for i in range(n):
    ar.append(list(input()))

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


for i in range(n):
    for j in range(m):
        if ar[i][j] == '.':
            vis = [[-1] * m for k in range(n)]
            queue = [i, j]
            vis[i][j] = 0
            while len(queue):
                x = queue.pop(0)
                y = queue.pop(0)
                for k in range(4):
                    x1 = x + dx[k]
                    y1 = y + dy[k]
                    if 0 <= x1 < n and 0 <= y1 < m and ar[x1][y1] == '.' and vis[x1][y1] == -1:
                        vis[x1][y1] = vis[x][y] + 1
                        res = max(res, vis[x1][y1])
                        queue.append(x1)
                        queue.append(y1)

print(res)


Verdicts: Wrong Answer

Accepted