Problem:


Score : 400 points

Problem Statement

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.

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

Any road square can be reached from any road square in zero or more moves.

Input

Input is given from Standard Input in the following format:

H W
S_{11}...S_{1W}
:
S_{H1}...S_{HW}

Output

Print the maximum possible number of moves Aoki has to make.

Sample Input 1

3 3
...
...
...

Sample Output 1

4

If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.

Sample Input 2

3 5
...#.
.#.#.
.#...

Sample Output 2

10

If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.



Sample input:
3 3
...
...
...


Sample output:
4

Submission status: Runtime Error

Solution code:
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy

glist = []


def makelist(num):
    if num == max:
        glist.append(list)
    else:
        list1 = copy.deepcopy(list)
        list1[num] = -1
        makelist(max, num + 1, list1)
        list2 = copy.deepcopy(list)
        list2[num] = 1
        makelist(max, num + 1, list2)


def checkcost(h, w):
    if h - 1 > -1:
        if glist[h - 1][w] == -1 or glist[h - 1][w] > glist[h][w] + 1:
            glist[h - 1][w] = glist[h][w] + 1
            checkcost(h - 1, w)

    if w - 1 > -1:
        if glist[h][w - 1] == -1 or glist[h][w - 1] > glist[h][w] + 1:
            glist[h][w - 1] = glist[h][w] + 1
            checkcost(h, w - 1)

    if h + 1 < maxh:
        if glist[h + 1][w] == -1 or glist[h + 1][w] > glist[h][w] + 1:
            glist[h + 1][w] = glist[h][w] + 1
            checkcost(h + 1, w)

    if w + 1 < maxw:
        if glist[h][w + 1] == -1 or glist[h][w + 1] > glist[h][w] + 1:
            glist[h][w + 1] = glist[h][w] + 1
            checkcost(h, w + 1)


maxh = 0
maxw = 0


def clacmaxxostaddress(maxh, maxw):
    max = -1
    maxh2 = -1
    maxj2 = -1
    for i in range(maxh):
        for j in range(maxw):
            if max < glist[i][j]:
                max = glist[i][j]
                maxh2 = i
                maxj2 = j
    return maxh2, maxj2


def clacmaxxost(maxh, maxw):
    max = -1
    maxh2 = -1
    maxj2 = -1
    for i in range(maxh):
        for j in range(maxw):
            if max < glist[i][j]:
                max = glist[i][j]
                maxh2 = i
                maxj2 = j
    return max


if __name__ == '__main__':
    a, b = map(int, input().split())
    maze = []
    maxh = a
    maxw = b
    for i in range(a):
        s = input()
        list = []
        for j in s:
            list.append(j)
        maze.append(list)
    address_h = -1
    address_w = -1
    for i in range(a):
        for j in range(b):
            if maze[i][j] == ".":
                address_h = i
                address_w = j
                break
        if maze[i][j] == ".":
            address_h = i
            address_w = j
            break

    glist = [[-1] * a for i in range(b)]
    glist[address_h][address_w] = 0
    checkcost(address_h, address_w)
    checkh, checkw = clacmaxxostaddress(a, b)
    glist = [[-1] * a for i in range(b)]
    glist[checkh][checkw] = 0

    checkcost(checkh, checkw)
    print(clacmaxxost(a, b))

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  while queue:
    y,x = queue.popleft()
    if [y, x] == [gy, gx]:
      return visited[y][x]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        visited[new_y][new_x] = visited[y][x] + 1
        queue.append([new_y, new_x])

h,w = map(int,input().split())
wall = ''
for i in range(w+2):
  wall += '#'
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('#'+m1+'#')
maze .append(wall)

ans = []
for i in range(1,h+1) :
  for j in range(1+w+1):
    for k in range(1,h+1) :
      for l in range(1,w+1) :
        sy = i ; sx = j
        gy = k ; gx = l
        if maze[sy][sx] == '#' or maze[gy][gx] == '#':
          break
        visited = [[-1]*(w+2) for _ in range(h+2)]
        ans.append(bfs(maze, visited, sy, sx, gy, gx))

print(max(ans))

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  while queue:
    y,x = queue.popleft()
    if [y, x] == [gy, gx]:
      return visited[y][x]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        visited[new_y][new_x] = visited[y][x] + 1
        queue.append([new_y, new_x])

h,w = map(int,input().split())
wall = ''
for i in range(w+2):
  wall += '#'
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('#'+m1+'#')
maze .append(wall)

s = [[1,1],[1,h],[w,1],[w,h]]
g = [[w,h],[w,1],[1,h],[1,1]]

ans = []
for i in range(4) :
  sy = s[i][1] ; sx = s[i][0]
  for j in range(1,h+1) :
    for k in range(1,w+1) :
      gy = j ; gx = k
      if maze[gy][gx] == '#' :
        break
      visited = [[-1]*(w+2) for _ in range(h+2)]
      ans.append(bfs(maze, visited, sy, sx, gy, gx))

print(max(ans))

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  while queue:
    y,x = queue.popleft()
    if [y, x] == [gy, gx]:
      return visited[y][x]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        visited[new_y][new_x] = visited[y][x] + 1
        queue.append([new_y, new_x])

h,w = map(int,input().split())
wall = ''
for i in range(w+2):
  wall += '#'
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('#'+m1+'#')
maze .append(wall)

s = [[1,1],[1,h],[w,1],[w,h]]
g = [[w,h],[w,1],[1,h],[1,1]]

ans = []
for i in range(4) :
  sy = s[i][1] ; sx = s[i][0]
  gy = g[i][1] ; gx = g[i][0]
  visited = [[-1]*(w+2) for j in range(h+2)]
  ans.append(bfs(maze, visited, sy, sx, gy, gx))

print(max(ans))

Submission status: Runtime Error

Solution code:
# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w = na()
m = nsn(h)

dist = [[inf] * (h * w) for _ in range(h * w)]
dx, dy = [0, 1, -1, 0], [1, 0, 0, -1]
for i in range(h):
    for j in range(w):
        for k in range(4):
            ni, nj = i + dy[k], j + dx[k]
            if ni >= 0 and ni < h and nj >= 0 and nj < w and m[ni][nj] != '#' and m[i][j] != '#':
                dist[i * h + j][ni * h + nj] = 1
        dist[i * h + j][i * h + j] = 0

def floyd_warshall(n, dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

floyd_warshall(h * w, dist)

ans = 0
for i in range(h * w):
    for j in range(h * w):
        if dist[i][j] != inf:
            ans = max(ans, dist[i][j])

print(ans)

Submission status: Runtime Error

Solution code:
# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w = na()
m = nsn(h)

dist = [[inf] * (h * w) for _ in range(h * w)]
dx, dy = [0, 1, -1, 0], [1, 0, 0, -1]
for i in range(h):
    for j in range(w):
        for k in range(4):
            ni, nj = i + dx[k], j + dy[k]
            if ni >= 0 and ni < h and nj >= 0 and nj < w and m[ni][nj] != '#' and m[i][j] != '#':
                dist[i * h + j][ni * h + nj] = 1
        dist[i * h + j][i * h + j] = 0

def floyd_warshall(n, dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

floyd_warshall(h * w, dist)

ans = 0
for i in range(h * w):
    for j in range(h * w):
        if dist[i][j] != inf:
            ans = max(ans, dist[i][j])

print(ans)

Submission status: Runtime Error

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

# 方針
# まずはスタート地点を固定し、移動回数を最小にして歩いたときの最大移動回数をbfs関数で求める
# ついでスタート地点を動かして、当の最大移動回数の最大値をとる
def bfs(maze, visited, sy, sx):

    visited[sy][sx] = 0
    # queueの要素について、そこから周囲4方向を模索する
    # queueには、これから周囲4方向を模索すべき地点が格納されている
    queue = deque([[sy, sx]])

    while queue:
        y, x = queue.popleft()
        for dy, dx in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            ny, nx = y + dy, x + dx
            if 0 <= ny < H and 0 <= nx < W and \
                    maze[ny][nx] == "." and visited[ny][nx] == -1:
                visited[ny][nx] = visited[y][x] + 1
                queue.append([ny, nx])

    return np.amax(visited)

ans = -1
for i in range(H):
    for j in range(W):
        sy, sx = i, j
        # (i,j)地点に到達するのにかかった歩数を(i,j)成分に記録する用のリストvisited
        visited = [[-1] * W for _ in range(H)]
        if maze[sy][sx] == '.':
            ans = max(ans, bfs(maze, visited, sy, sx))

print(ans)

Submission status: Runtime Error

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

# 方針
# まずはスタート地点を固定し、移動回数を最小にして歩いたときの最大移動回数をbfs関数で求める
# ついでスタート地点を動かして、当の最大移動回数の最大値をとる
def bfs(maze, visited, sy, sx):

    visited[sy][sx] = 0
    # queueの要素について、そこから周囲4方向を模索する
    # queueには、これから周囲4方向を模索すべき地点が格納されている
    queue = deque([[sy, sx]])

    while queue:
        y, x = queue.popleft()
        for dy, dx in ([1, 0], [1, 1], [0, 1], [0, -1]):
            ny, nx = y + dy, x + dx
            if 0 <= ny < H and 0 <= nx < W and \
                    maze[ny][nx] == "." and visited[ny][nx] == -1:
                visited[ny][nx] = visited[y][x] + 1
                queue.append([ny, nx])

    return np.amax(visited)

ans = -1
for i in range(H):
    for j in range(W):
        sy, sx = i, j
        # (i,j)地点に到達するのにかかった歩数を(i,j)成分に記録する用のリストvisited
        visited = [[-1] * W for _ in range(H)]
        if maze[sy][sx] == '.':
            ans = max(ans, bfs(maze, visited, sy, sx))

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())

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

ans = 0
for ii in range(1,H+1):
    for jj in range(1,W+1):
        if maze[ii][jj]=='#':continue
        temp = deque()
        temp.append([ii,jj])
        mazenum = [[0]*(W+2) for _ in range(H+2)]
        mazenum[ii][jj] = 0
        visited = [[False]*(W+2) for _ in range(H+2)]
        visited[ii][jj] = True

        while temp:
            p = temp.popleft()
            m = mazenum[p[0]][p[1]]
            for i, j in [[p[0]-1,p[1]], [p[0]+1, p[1]], [p[0],p[1]-1],[p[0],p[1]+1]]:
                if maze[i][j]=='.':
                    if not visited[i][j]:
                        temp.append([i, j])
                        mazenum[i][j] = m + 1
                        visited[i][j]=True        
        ans = max(ans, max(max(mazenum)))     

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

h,w = map(int,input().split())
maze = [[False for _ in range(w)] for _ in range(h)]


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

#print(maze)

def bfs(x,y):
    seen = [[False for _ in range(w)] for _ in range(h)]
    dist = [[False for _ in range(w)] for _ in range(h)]
    
    if(maze[y][x] == "#"):
        return [[0]]
    
    dist[y][x] = 0
    d = deque()
    d.append(x + w*y)
    #print(d)
    while d:
        #print(d)
        base = d.popleft()
        #print(base)
        xx = base%w
        yy = base//w
        #print(*seen,sep='\n')
        #print("-------")
        if(seen[yy][xx] == True):
            continue
        else:
            seen[yy][xx] = True
        
        for px,py in [(-1,0),(1,0),(0,-1),(0,1)]:
            #print(xx+px,yy+py)
            if (0<= xx+px < w and 0<= yy+py < h):
                if(maze[yy+py][xx+px] == "." and seen[yy+py][xx+px] == False):
                    d.append(xx+px+(yy+py)*w)
                    dist[yy+py][xx+px] = dist[yy][xx] + 1
    
    return dist

result = bfs(0,2)  

#print(*result,sep ="\n")
ans = 0
for j in range(h):
    for k in range(w):
        res = 0
        result = bfs(k,j)
        for i in result:
            res = max(max(i),res)
        ans = max(ans,res)
        


print(ans)

Submission status: Runtime Error

Solution code:
import math 
import bisect
import heapq
from collections import deque

h,w = map(int,input().split())
s = [map(int,input().split()) for _ in range(h)]
v = [ [0] * w ] * h

def bfs(i,j,s,v,count):

    if s[i][j] == '#': return 0
    else:
        v[i][j] = 1
        if i+1 < h and j+1 < w :
            if v[i+1][j+1] != 1 and s[i+1][j+1] == '.':
                count += 1
                bfs(i+1,j+1,s,v,count)

        elif i+1 < h and j-1 > 0 :
            if v[i+1][j-1] != 1 and s[i+1][j-1] == '.':
                count += 1
     
                bfs(i+1,j-1,s,v,count)

        elif i-1 < h and j+1 > 0 :
            if v[i-1][j+1] != 1 and s[i-1][j+1] == '.':
                count += 1
       
                bfs(i-1,j+1,s,v,count)

        elif i-1 < h and j-1 > 0 :
            if v[i+1][j-1] != 1 and s[i-1][j-1] == '.':
                count += 1
               
                bfs(i-1,j-1,s,v,count)

        else :return count

ans = 0
for i in range(h):
    for j in range(w):
        x,y = i,j
        ans = max(ans,bfs(i,j,s,v,0))

print(ans)

Submission status: Runtime Error

Solution code:
import math 
import bisect
import heapq
from collections import deque

h,w = map(int,input().split())
s = [map(int,input().split()) for _ in range(h)]
v = [ [0] * w ] * h

def bfs(i,j,s,v,count):

    if s[i][j] == '#': return 0
    else:
        v[i][j] = 1
        if i+1 < h and j+1 < w :
            if v[i+1][j+1] != 1 and s[i+1][j+1] == '.':
                count += 1
                bfs(i+1,j+1,s,v,count)

        elif i+1 < h and j-1 > 0 :
            if v[i+1][j-1] != 1 and s[i+1][j-1] == '.':
                count += 1
     
                bfs(i+1,j-1,s,v,count)

        elif i-1 < h and j+1 > 0 :
            if v[i-1][j+1] != 1 and s[i-1][j+1] == '.':
                count += 1
       
                bfs(i-1,j+1,s,v,count)

        elif i-1 < h and j-1 > 0 :
            if v[i+1][j-1] != 1 and s[i-1][j-1] == '.':
                count += 1
               
                bfs(i-1,j-1,s,v,count)

        else :return count

ans = 1000000
for i in range(h):
    for j in range(w):
        x,y = i,j
        ans = min(ans,bfs(i,j,s,v,0))

Submission status: Runtime Error

Solution code:
import math 
import bisect
import heapq
from collections import deque

h,w = map(int,input().split())
s = [map(int,input().split()) for _ in range(h)]
v = [ [0] * w ] * h

def bfs(i,j,s,v,count):

    if s[i][j] == '#': return 0
    else:
        v[i][j] = 1
        if i+1 < h and j+1 < w :
            if v[i+1][j+1] != 1 and s[i+1][j+1] == '.':
                count += 1
                bfs(i+1,j+1,s,v,count)

        elif i+1 < h and j-1 > 0 :
            if v[i+1][j-1] != 1 and s[i+1][j-1] == '.':
                count += 1
     
                bfs(i+1,j-1,s,v,count)

        elif i-1 < h and j+1 > 0 :
            if v[i-1][j+1] != 1 and s[i-1][j+1] == '.':
                count += 1
       
                bfs(i-1,j+1,s,v,count)

        elif i-1 < h and j-1 > 0 :
            if v[i+1][j-1] != 1 and s[i-1][j-1] == '.':
                count += 1
               
                bfs(i-1,j-1,s,v,count)

        else :return count

ans = 1000000
for i in range(h):
    for j in range(w):
        x,y = i,j
        ans = min(ans,bfs(i,j,s,v))

Submission status: Runtime Error

Solution code:
import math 
import bisect
import heapq
from collections import deque

h,w = map(int,input().split())
s = [map(int,input().split()) for _ in range(h)]
v = [ [0] * w ] * h

def bfs(i,j,s,v):
    count = 0
    mx = 0
    if s[i][j] == '#': return 0
    else:
        v[i][j] = 1
        if i+1 < h and j+1 < w :
            if v[i+1][j+1] != 1 and s[i+1][j+1] == '.':
                count += 1
                mx = max(count,mx)
                bfs(i+1,j+1,s,v)

        elif i+1 < h and j-1 > 0 :
            if v[i+1][j-1] != 1 and s[i+1][j-1] == '.':
                count += 1
                mx = max(count,mx)
                bfs(i+1,j-1,s,v)

        elif i-1 < h and j+1 > 0 :
            if v[i-1][j+1] != 1 and s[i-1][j+1] == '.':
                count += 1
                mx = max(count,mx)
                bfs(i-1,j+1,s,v)

        elif i-1 < h and j-1 > 0 :
            if v[i+1][j-1] != 1 and s[i-1][j-1] == '.':
                count += 1
                mx = max(count,mx)
                bfs(i-1,j-1,s,v)


    return mx

ans = 1000000
for i in range(h):
    for j in range(w):
        x,y = i,j
        ans = min(ans,bfs(i,j,s,v))

Submission status: Runtime Error

Solution code:
import math 
import bisect
import heapq
from collections import deque

h,w = map(int,input().split())
s = [map(int,input().split()) for _ in range(h)]
v = [ [0] * w ] * h

bfs(i,j,s,v):
    count = 0
    mx = 0
    if s[i][j] == '#': return 0
    elif:
        v[i][j] = 1
        if i+1 < h and j+1 < w 
            if v[i+1][j+1] != 1 and s[i+1][j+1] == '.'
                count += 1
                mx = max(count,mx)
                bfs(i+1,j+1,s,v)

        elif i+1 < h and j-1 > 0 
            if v[i+1][j-1] != 1 and s[i+1][j-1] == '.'
                count += 1
                mx = max(count,mx)
                bfs(i+1,j-1,s,v)

        elif i-1 < h and j+1 > 0 
            if v[i-1][j+1] != 1 and s[i-1][j+1] == '.'
                count += 1
                mx = max(count,mx)
                bfs(i-1,j+1,s,v)

        elif i-1 < h and j-1 > 0 
            if v[i+1][j-1] != 1 and s[i-1][j-1] == '.'
                count += 1
                mx = max(count,mx)
                bfs(i-1,j-1,s,v)


    return mx

ans = 1000000
for i in range(h):
    for j in range(w):
        x,y = i,j
        ans = min(ans,bfs(i,j,s,v))

Submission status: Runtime Error

Solution code:
from collections import deque
import math
import copy
import sys
sys.setrecursionlimit(2147483647)

h,w = map(int, input().split())
maze = [list(map(str,input())) for _ in range(h)]


ans = 0

for i in range(w):
     for j in range(h):
          for k in range(w):
               for l in range(h):

                    maze2 = copy.deepcopy(maze)

                    if maze[j][i] == '#' or maze[l][k] == '#':
                         pass
                    else:
                         sx,sy,gx,gy = i,j,k,l
                         for y in range(h):
                              for x in range(w):
                                   if maze[y][x] == '.':
                                        maze2[y][x] = math.inf


                         maze2[sy][sx]=0
                         que=deque([[sy,sx]])
                         while que:
                              y,x=que.popleft()
                              for m,n in [(1,0),(0,1),(-1,0),(0,-1)]:
                                   nexty,nextx=y+m,x+n
                                   if  nexty in range(h) and nextx in range(w):
                                        dist=maze2[nexty][nextx]
                                        if dist!='#':
                                             if dist>maze2[y][x]+1:
                                                  maze2[nexty][nextx]=maze2[y][x]+1
                                                  que.append([nexty,nextx])
                         if ans < maze2[gy][gx]:
                              ans = maze2[gy][gx]

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import math
import copy

h,w = map(int, input().split())
maze = [list(map(str,input())) for _ in range(h)]


ans = 0

for i in range(w):
     for j in range(h):
          for k in range(w):
               for l in range(h):

                    maze2 = copy.deepcopy(maze)

                    if maze[j][i] == '#' or maze[l][k] == '#':
                         pass
                    else:
                         sx,sy,gx,gy = i,j,k,l
                         for y in range(h):
                              for x in range(w):
                                   if maze[y][x] == '.':
                                        maze2[y][x] = math.inf


                         maze2[sy][sx]=0
                         que=deque([[sy,sx]])
                         while que:
                              y,x=que.popleft()
                              for m,n in [(1,0),(0,1),(-1,0),(0,-1)]:
                                   nexty,nextx=y+m,x+n
                                   if  nexty in range(h) and nextx in range(w):
                                        dist=maze2[nexty][nextx]
                                        if dist!='#':
                                             if dist>maze2[y][x]+1:
                                                  maze2[nexty][nextx]=maze2[y][x]+1
                                                  que.append([nexty,nextx])
                         if ans < maze2[gy][gx]:
                              ans = maze2[gy][gx]

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import math
import copy

h,w = map(int, input().split())
maze = [list(map(str,input())) for _ in range(h)]


ans = 0

for i in range(w):
     for j in range(h):
          for k in range(w):
               for l in range(h):

                    maze2 = copy.deepcopy(maze)

                    if maze[j][i] == '#' or maze[l][k] == '#':
                         pass
                    else:
                         sx,sy,gx,gy = i,j,k,l
                         for y in range(h):
                              for x in range(w):
                                   if maze[y][x] == '.':
                                        maze2[y][x] = math.inf


                         maze2[sy][sx]=0
                         que=deque([[sy,sx]])
                         while que:
                              y,x=que.popleft()
                              for m,n in [(1,0),(0,1),(-1,0),(0,-1)]:
                                   nexty,nextx=y+m,x+n
                                   if  nexty in range(h) and nextx in range(w):
                                        dist=maze2[nexty][nextx]
                                        if dist!='#':
                                             if dist>maze2[y][x]+1:
                                                  maze2[nexty][nextx]=maze2[y][x]+1
                                                  que.append([nexty,nextx])
                         if ans < maze2[gy][gx]:
                              ans = maze2[gy][gx]
                              
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
mass = [[ord(i) for i in input().split()]for _ in range(h)]
wall = ord("#")
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = [[0] * w for _ in range(h)]
    depth = [[0] * w for _ in range(h)]
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1
        r = depth[x][y] + 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == wall:
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = r

    u = 0
    for row in depth:
        u = max(u, max(row))
    return u


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Runtime Error

Solution code:
from collections import deque
import math
import copy

h,w = map(int, input().split())
maze = [list(map(str,input())) for _ in range(h)]


ans = 0

for i in range(w):
     for j in range(h):
          for k in range(w):
               for l in range(h):

                    maze2 = copy.deepcopy(maze)

                    if maze[j][i] == '#' or maze[l][k] == '#':
                         pass
                    else:
                         sx,sy,gx,gy = i,j,k,l
                         for y in range(h):
                              for x in range(w):
                                   if maze[y][x] == '.':
                                        maze2[y][x] = math.inf


                         maze2[sy][sx]=0
                         que=deque([[sy,sx]])
                         while que:
                              y,x=que.popleft()
                              for m,n in [(1,0),(0,1),(-1,0),(0,-1)]:
                                   nexty,nextx=y+m,x+n
                                   if  nexty in range(h) and nextx in range(w):
                                        dist=maze2[nexty][nextx]
                                        if dist!='#':
                                             if dist>maze2[y][x]+1:
                                                  maze2[nexty][nextx]=maze2[y][x]+1
                                                  que.append([nexty,nextx])
                         if ans < maze2[gy][gx]:
                              ans = maze2[gy][gx]
                              print(ans,sx,sy,gx,gy)
print(ans)

Submission status: Runtime Error

Solution code:
#D
from collections import deque
h,w=map(int,input().split())
s=[]

for i in range(h):
    s.append(list(input()))
dx=[1,0,-1,0]#東南西北
dy=[0,-1,0,1]
ans=0
def search(i,j):
    if s[i][j]=="#":
        return 0
    max_step=0
    que=deque()
    que.append([i,j])#1現在地
    dist=[[-1 for _ in range(w)] for _ in range (h)]
    #(h,w)
    dist[i][j]=0#現在地は0
    while que:#行き先が無くなるまで
        y,x=que.popleft()#現在地を取り出す(y,x)
        for dir in range(4):
            nx=x+dx[dir]#行き先(nx,xy)
            ny=y+dy[dir]
            if ny<0 or ny>=h or nx<0 or nx>=w or s[ny][nx]=="#":#壁の中
            elif dist[ny][nx]!=-1:#捜索済み
            #未捜索地点"."
            else:
                dist[ny][nx]=dist[y][x]+1#1進む
                que.append([ny,nx])
    out=0
    for i in range(h):
        for j in range(w):
            if dist[i][j]==-1:
                break
            out=max(out,dist[i][j])
    return out

for i in range(h):
    for j in range(w):
        step=search(i,j)#(j,i)の時の最大移動数を求める
        if ans<step:
            ans=step
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np

h, w = map(int, input().split())
S = [input() for _ in range(h)] # #.のグリッドの場合

starts = []
for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            starts.append((i,j))

step = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ans = 0
for si in starts:
    maxlen = 0
    seen = [[0] * w for _ in range(h)]
    que = deque()
    que.append(si)
    while len(que) > 0:
        x, y = que.popleft()
        for xs, ys in step:
            xi, yi = x + xs, y + ys
            if xi < 0 or yi < 0 or xi >= h or yi >= w:
                continue
            if S[xi][yi] == '#':
                continue
            if seen[xi][yi] != 0:
                continue
            else:
                seen[xi][yi] = seen[x][y] + 1
                que.append((xi, yi))
                maxlen = max(maxlen, seen[xi][yi])
    #print(np.array(seen))
    ans = max(ans, maxlen)
print(ans)

Submission status: Runtime Error

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


from collections import deque
def bfs(maze, dist, sy, sx):
    d = deque()
    d.append([sy, sx])
    while d:
        y, x = d.popleft()
        for dy, dx in [1, 0], [-1, 0], [0, 1], [0, -1]:
            ny = y + dy
            nx = x + dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            if maze[ny][nx] == '#':
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                d.append([ny, nx])

ans = -1
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '#':
            continue
        dist = [[-1] * W for _ in range(W)]
        for gy in range(H):
            for gx in range(W):
                if maze[gy][gx] == '#':
                    continue
                dist[sy][sx] = 0
                bfs(maze, dist, sy, sx)
                ans = max(ans, dist[gy][gx])
print(ans)