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 queue
H,W = map(int,input().split())
maze = list()
q = queue.Queue()
for i in range(H):
   maze.append( [x for x in input()])

maxim = 1
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." :
            maze_score = [[0]*W for k in range(W)]
            maze_score[i][j] = 1
            q.put([i,j])
            
        else :
            continue
        
        while(True):
            if q.empty() :
                break
            [x,y] = q.get()
            
            if maze_score[x][y] > maxim:
                maxim = maze_score[x][y]
            
            ##top
            if x != 0:
                if maze_score[x-1][y] ==0 and maze[x-1][y] == ".":
                    maze_score[x-1][y] = maze_score[x][y] +1
                    q.put([x-1,y])
            ##right
            if y != W-1:
                if maze_score[x][y+1] ==0 and maze[x][y+1] == ".":
                    maze_score[x][y+1] = maze_score[x][y] +1
                    q.put([x,y+1])
            ##bottom
            if x != H-1:
                if maze_score[x+1][y] ==0 and maze[x+1][y] == ".":
                    maze_score[x+1][y] = maze_score[x][y] +1
                    q.put([x+1,y])
            ##left
            if y != 0:
                if maze_score[x][y-1] ==0 and maze[x][y-1] == ".":
                    maze_score[x][y-1] = maze_score[x][y] +1
                    q.put([x,y-1])
        
print(maxim-1)

Submission status: Runtime Error

Solution code:
import queue
H,W = map(int,input().split())
maze = list()
q = queue.Queue()
for i in range(H):
   maze.append( [x for x in input()])

maxim = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." :
            maze_score = [[0]*W for k in range(W)]
            maze_score[i][j] = 1
            q.put([i,j])
            
        else :
            continue
        
        while(True):
            if q.empty() :
                break
            [x,y] = q.get()
            
            if maze_score[x][y] > maxim:
                maxim = maze_score[x][y]
            
            ##top
            if x != 0:
                if maze_score[x-1][y] ==0 and maze[x-1][y] == ".":
                    maze_score[x-1][y] = maze_score[x][y] +1
                    q.put([x-1,y])
            ##right
            if y != W-1:
                if maze_score[x][y+1] ==0 and maze[x][y+1] == ".":
                    maze_score[x][y+1] = maze_score[x][y] +1
                    q.put([x,y+1])
            ##bottom
            if x != H-1:
                if maze_score[x+1][y] ==0 and maze[x+1][y] == ".":
                    maze_score[x+1][y] = maze_score[x][y] +1
                    q.put([x+1,y])
            ##left
            if y != 0:
                if maze_score[x][y-1] ==0 and maze[x][y-1] == ".":
                    maze_score[x][y-1] = maze_score[x][y] +1
                    q.put([x,y-1])
        
print(maxim-1)

Submission status: Runtime Error

Solution code:
from collections import deque

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

G = []
for i in range(H):
    G.append(list(input()))


move = [[0, 1], [0, -1], [0, 1], [1, 0]]
saidai = 0
for sy in range(H):
    for sx in range(W):
        if G[sy][sx] == "#":
            break
        queue = deque([[sy, sx]])
        G[sy][sx] = 0
        visited = [[0]*W for i in range(H)]
        while queue:
            y, x = queue.popleft()
            for i in move:
                iy, ix = i[0], i[1]
                if 0<=iy+y<H and 0<=ix+x<W and G[iy+y][ix+x] =="." and visited[iy+y][ix+x] == 0:
                    visited[iy+y][ix+x] = 1
                    G[iy+y][ix+x] = G[y][x] + 1
                    queue.append([iy+y, ix+x])
 
        for i in range(H):
            for j in range(W):
                if G[i][j] == "#":
                    continue
                else:
                    saidai = max(saidai, G[i][j])

print(saidai)

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(map(str, input().split())) for _ in range(h)]


def bfs(i, j):  # 引数はスタートの位置(i, j)
    q = deque()
    q.append((i, j))
    log = [[-1] * w for _ in range(h)]
    log[i][j] = 0
    distance = 0
    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while q:
        p = q.popleft()
        for x, y in d:
            nx = p[0] + x
            ny = p[1] + y
            if not(0 <= nx < h and 0 <= ny < w):  # 迷路の外にはでれない
                continue
            elif s[nx][ny] == "#":  # 壁には進めない
                continue
            elif log[nx][ny] >= 0:  # 探索済みは探索しない
                continue
            else:
                log[nx][ny] = log[p[0]][p[1]] + 1
                q.append((nx, ny))
                if distance < log[nx][ny]:
                    distance = log[nx][ny]
    return distance


distance = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":  # start地点は壁でない
            continue
        else:
            temp = bfs(i, j)
            if temp >= distance:
                distance = temp
print(distance)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import collections

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw, 0))
    dist = [[float('inf') for _ in range(W)] for _ in range(W)]

    while len(que) > 0:
        h, w, d = que.popleft()
        if dist[h][w] != float('inf'):
            continue
        dist[h][w] = d
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#':
                continue
            que.append((h + dh, w + dw, d + 1))
    return dist


for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            tmp_dist = bfs(h, w, mp)
            break

sh, sw = (h, w)
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.' and tmp_dist[sh][sw] >= tmp_dist[h][w]:
            sh = h; sw = w
dist = bfs(sh, sw, mp)

ans = 0
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            ans = max(ans, dist[h][w])
print(ans)

Submission status: Runtime Error

Solution code:
from collections import*
from itertools import*
from copy import*
n,m=map(int,input().split())

grid=[tuple("#"*(m+2))]+[tuple("#"+input()+"#")for i in range(n)]+[tuple("#"*(m+2))]

#print(grid)

start=[]
for i in range(1,n+1):
    for j in range(1,m+1):
        start.append((i,j))

ans=0
for s,g in combinations(start,2):
    G=deepcopy(grid)
    if G[s[0]][s[1]]!="#":
        G[s[0]][s[1]]=0
    else:
        continue
    if G[g[0]][g[1]]=="#":
        continue
    Q=deque([s])
    while Q:
        y,x=Q.pop()
        for my,mx in (-1,0),(1,0),(0,-1),(0,1):
            if G[y+my][x+mx]==".":
                G[y+my][x+mx]=G[y][x]+1
                Q.appendleft((y+my,x+mx))
    
    if type(G[g[0]][g[1]])!=str:
        if ans<G[g[0]][g[1]]:
            ans=G[g[0]][g[1]]
print(ans)

Submission status: Runtime Error

Solution code:
import math
from queue import Queue
import copy

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

q = Queue()
ans = 0

for y in range(h):
    for x in range(w):
        li = copy.deepcopy(ili)
        if li[y][x] == "#": continue
        q.put([x, y])
        li[y][x] = 0
        while not q.empty():
            c = q.get()
            # 上(0, -1) 右(1, 0) 下(0, 1) 左(-1, 0)
            for dr in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
                nX = c[0] + dr[0]
                nY = c[1] + dr[1]

                if not (0 <= nX <= w - 1): continue
                if not (0 <= nY <= h - 1): continue

                if li[nY][nX] == ".":
                    li[nY][nX] = li[c[1]][c[0]] + 1
                    q.put([nX, nY])

        li = list(
            map(lambda item: 0 if item == "#" or item == "." else item,
                sum(li, [])))
        ans = max(*li, ans)

print(ans)

Submission status: Runtime Error

Solution code:
import math
from queue import Queue

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

q = Queue()
#     [x, y]
q.put([0, h - 1])
li[h - 1][0] = 0

while not q.empty():
    c = q.get()
    # 上(0, -1) 右(1, 0) 下(0, 1) 左(-1, 0)
    for dr in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
        if li[c[1]][c[0]] == "#": break

        nX = c[0] + dr[0]
        nY = c[1] + dr[1]

        if not (0 <= nX <= w - 1): continue
        if not (0 <= nY <= h - 1): continue

        if li[nY][nX] == ".":
            li[nY][nX] = li[c[1]][c[0]] + 1
            q.put([nX, nY])

li = list(map(lambda item: 0 if item == "#" else item, sum(li, [])))
print(max(li))

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
s = [['#' for _ in range(w+2)]]
for _ in range(h):
    s.append(list('#' + input() + '#'))
s.append(['#' for _ in range(w+2)])

# WFS
ans = []
d = [(1,0), (0,1), (-1,0), (0,-1)]
from collections import deque
for i in range(1, h+1):
    for j in (1, w+1):
        if s[i][j] == '#':
            continue
        seen = [[-1 for _ in range(w+2)] for __ in range(h+2)]
        seen[i][j] = 0
        todo = deque([(i, j)])
        num = 0
        while todo != deque([]):
            x, y = todo.popleft()
            for k in d:
                xk = x + k[0]
                yk = y + k[1]
                if seen[xk][yk] == -1 and s[xk][yk] == '.':
                    num = seen[x][y] + 1
                    seen[xk][yk] = num
                    todo.append((xk,yk))
        ans.append(num)
print(max(ans))

Submission status: Runtime Error

Solution code:
import copy
from collections import deque

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


def check(tup):
    global H
    global W
    global S

    tup_x=tup[0]
    tup_y=tup[1]
    if 0<=tup_x<H and 0<=tup_y<W:
        if S[tup_x][tup_y]=='.':
            return True
    else:
        return False

def neighbor(tup):
    x=tup[0]
    y=tup[1]
    cand=[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
    List=[]
    for c in cand:
        if check(c):
            List.append(c)
    return List

def bfs(start):#startはtuple型
    global H
    global W

    deq=deque()#as queue
    Dict=[]
    component=[]
    for i in range(W):
        component.append(-1)
    for j in range(H):
        Dict.append(copy.copy(component))

    deq.append(start)
    Dict[start[0]][start[1]]=0
    while deq:
        now=deq.popleft()
        nexts=neighbor(now)
        for next in nexts:
            next_x=next[0]
            next_y=next[1]
            if Dict[next_x][next_y]>=0:
                continue
            if next in deq:
                continue
            deq.append(next)
            Dict[next_x][next_y]=Dict[now[0]][now[1]]+1

    M=[]
    for d in Dict:
        M.apeend(max(d))
    return max(M)

Ans=[]
for k in range(H):
    for l in range(W):
        Ans.append(bfs((k,l)))

print(max(Ans))

Submission status: Runtime Error

Solution code:
# coding: utf-8
 
def main():
	H, W = (int(x) for x in input().split())
	S = [[] for x in range(H)]
 
	for i in range(H):
		S[i] = [x for x in input()]
 
	# 隣接行列の作成
	inf = 1000000
 
	nodes = []
	for i in range(H):
		for j in range(W):
			if S[i][j] == ".":
				nodes.append([i, j])
	
	g = [[inf for j in range(len(nodes))] for i in range(len(nodes))]
	for i in range(len(nodes)):
		for j in range(len(nodes)):
			if   nodes[i][0] == nodes[j][0] and nodes[i][1] == nodes[j][1]:
				g[i][j] = 0
			elif abs(nodes[i][0]-nodes[j][0]) + abs(nodes[i][1]-nodes[j][1]) == 1:
				g[i][j] = 1
 
	max = 0
	for k in range(len(g[0])):
		for i in range(len(g[0])):
			for j in range(len(g[0])):
				g[i][j] = min(g[i][j], g[i][k] + g[k][j])
                if max < g[i][j]:
					max = g[i][j]

	print(max)
 
if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def dfs(h, w): # startからの距離の最大値をreturnする
    res = -1
    dist = [[-1] * W for _ in range(H)]
    stack = []
    dist[h][w] = 0
    stack.append([h, w])
    while stack:
        h, w = stack.pop()
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if nh >= H or nh < 0 or nw >= W or nw < 0:
                continue
            if s[nh][nw] == "#":
                continue
            if dist[nh][nw] == -1:
                dist[nh][nw] = dist[h][w] + 1
                stack.append([nh, nw])
            if dist[nh][nw] != -1:
                if dist[nh][nw] > (dist[h][w]+1):
                    dist[nh][nw] = dist[h][w] + 1
                    stack.append([nh, nw])
    for i in range(H):
        if res <= max(visited[i]):
            res = max(visited[i])
    return res

H, W = map(int, input().split())
s = [input() for _ in range(H)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
m = -1
dist = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            dist = dfs(i, j)
            if m <= dist:
                m = dist
print(m)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
from collections import deque


h,w=map(int,input().split())
s = [list(input()) for i in range(h)]

def bfs(sx,sy,gx,gy):
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    d = [[float('inf')]*w for i in range(h)]
    q = deque()
    q.append((sx,sy))
    d[sx][sy] = 0
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if  0<= nx < h and 0 <= ny < w and d[nx][ny]==float('inf') and s[nx][ny]=='.':
                q.append((nx,ny))
                d[nx][ny] = d[x][y]+1
    return max([max(i) for i in d])

count = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            count  = max(count, bfs(i,j,k,l))
print(count)

Submission status: Runtime Error

Solution code:
from collections import deque
import math

H,W = list(map(int,input().split()))
r = []
ans = []
for i in range(H):
    S = str(input())
    S = [S[i] for i in range(len(S))]
    r.append(S)

def mazesol(H,W,r,sx,sy,ans):
    count = 0
    bfs = [[-1 for i in range(W+2)] for j in range(H+2)]
    for i in range(H):
        for j in range(W):
            if r[i][j] == '.':
                bfs[i+1][j+1] = math.inf
    if bfs[sy-1][sx-1] != -1:
        bfs[sy-1][sx-1] = 0
        que = deque([[sy-1,sx-1]])
        while que:
            y,x = que.popleft()
            for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
                ny,nx = y+i,x+j
                nex = bfs[ny][nx]
                if nex != '#':
                    if nex > bfs[y][x]+1:
                        bfs[ny][nx]=bfs[y][x]+1
                        que.append([ny,nx])
        for i in range(H+2):
            ans.append(max(bfs[i]))
for i in range(H+2):
    for j in range(W+2):
        mazesol(H,W,r,j,i,ans)
print(max(ans))

Submission status: Runtime Error

Solution code:
from collections import deque
import math

H,W = list(map(int,input().split()))
r = []
ans = []
for i in range(H):
    S = str(input())
    S = [S[i] for i in range(len(S))]
    r.append(S)

def mazesol(H,W,r,sx,sy,ans):
    count = 0
    bfs = [[-1 for i in range(W+2)] for j in range(H+2)]
    for i in range(H):
        for j in range(W):
            if r[i][j] == '.':
                bfs[i+1][j+1] = math.inf
    if bfs[sy-1][sx-1] != -1:
        bfs[sy-1][sx-1] = 0
        que = deque([[sy-1,sx-1]])
        while que:
            y,x = que.popleft()
            for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
                ny,nx = y+i,x+j
                nex = bfs[ny][nx]
                if nex != '#':
                    if nex > bfs[y][x]+1:
                        bfs[ny][nx]=bfs[y][x]+1
                        que.append([ny,nx])
        for i in range(W+2):
            ans.append(max(bfs[i]))
for i in range(H+2):
    for j in range(W+2):
        mazesol(H,W,r,j,i,ans)
print(max(ans))

Submission status: Runtime Error

Solution code:
from collections import deque
import math

H,W = list(map(int,input().split()))
r = []
ans = []
for i in range(H):
    S = str(input())
    S = [S[i] for i in range(len(S))]
    r.append(S)

def mazesol(H,W,r,sx,sy,ans):
    count = 0
    bfs = [[-1 for i in range(W+2)] for j in range(H+2)]
    for i in range(H):
        for j in range(W):
            if r[i][j] == '.':
                bfs[i+1][j+1] = math.inf
    if bfs[sy-1][sx-1] != -1:
        bfs[sy-1][sx-1] = 0
        que = deque([[sy-1,sx-1]])
        while que:
            y,x = que.popleft()
            for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
                ny,nx = y+i,x+j
                nex = bfs[ny][nx]
                if nex != '#':
                    if nex > bfs[y][x]+1:
                        bfs[ny][nx]=bfs[y][x]+1
                        que.append([ny,nx])
        for i in range(5):
            ans.append(max(bfs[i]))
for i in range(H+2):
    for j in range(W+2):
        mazesol(H,W,r,j,i,ans)
print(max(ans))

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int,input().split())
S = [list(input()) for _ in range(H)]
dhw = [[0,1],[0,-1],[1,0],[-1,0]]

ans = 0
for h in range(H):
  for w in range(W):
    d = deque([h,w])
    maze = [[-1] * W for _ in range(H)]
    if S[h][w] == '#':
      continue
    maze[h][w] = 0
    while d:
      ht , wt = d.popleft()
      for dh, dw in dhw:
        nh = ht + dh
        nw = wt + dw
        if not(0 <= nh < H and 0 <= nw < W):
          continue
        S[nh][nw] == '#':
          continue
        if maze[nh][nw] == -1:
          d.append([nh,nw])
          maze[nh][nw] = maze[ht][wt] + 1
    ans = max(ans,max[max(l) for l in maze])

print(ans)

Submission status: Runtime Error

Solution code:
from intertools import chain
from collections import deque
H, W = map(int,input().split())
S = [list(input()) for _ in range(H)]
dhw = [[0,1],[0,-1],[1,0],[-1,0]]

ans = 0
for h in range(H):
  for w in range(W):
    d = deque([h,w])
    maze = [[-1] * W for _ in range(H)]
    if S[h][w] == '#':
      continue
    maze[h][w] = 0
    while d:
      ht , wt = d.popleft()
      for dh, dw in dhw:
        nh = ht + dh
        nw = wt + dw
        if not(0 <= nh < H and 0 <= nw < W):
          continue
        S[nh][nw] == '#':
          continue
        if maze[nh][nw] == -1:
          d.append([nh,nw])
          maze[nh][nw] = maze[ht][wt] + 1
    ans = max(ans,max[max(l) for l in maze])

print(ans)

Submission status: Runtime Error

Solution code:
from intertools import chain
from collections import deque
H, W = map(int,input().split())
S = [list(input()) for _ in range(H)]
dhw = [[0,1],[0,-1],[1,0],[-1,0]]

ans = 0
for h in range(H):
  for w in range(W):
    d = deque([h,w])
    maze = [[-1] * W for _ in range(H)]
    if S[h][w] == '#':
      continue
    maze[h][w] = 0
    while d:
      ht , wt = d.popleft()
      for dh, dw in dhw:
        nh = ht + dh
        nw = wt + dw
        if 0 <= nh < H and 0 <= nw < W:
          if maze[nh][nw] == -1 and S[nh][nw] == '.':
            d.append([nh,nw])
            maze[nh][nw] = maze[ht][wt] + 1
    ans = max(ans,max(chain(*maze))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int,input().split())
S = [list(map(str,input().split())) for _ in range(H)]
dhw = [[0,1],[0,-1],[1,0],[-1,0]]

ans = 0
for h in range(H):
  for w in range(W):
    d = deque([h,w])
    maze = [[-1] * W for _ in range(H)]
    if S[h][w] == '#':
      continue
    maze[h][w] = 0
    while d:
      ht , hw = d.popleft()
      for dh, dw in dhw:
        nh = ht + dh
        nw = wt + dw
        if 0 <= nh < H and 0 <= nw < W:
          if maze[nh][nw] == -1 and S[nh][nw] == '.':
            d.append([nh,nw])
            maze[nh][nw] = maze[ht][wt] + 1
    ans = max(ans,max(maze))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int,input().split())
S = [list(map(str,input().split())) for _ in range(H)]
dhw = [[0,1],[0,-1],[1,0],[-1,0]]

ans = 0
for h in range(H):
  for w in range(W):
    d = deque([h,w])
    maze = [[-1] * W for _ in range(H)]
    if S[h][w] == '#':
      continue
    maze[h][w] = 0
    while d:
      ht , hw = d.popleft()
      for dh, dw in dhw:
        nh = ht + dh
        nw = wt + dw
        if 0 <= nh < H and 0 <= nw < W:
          if maze[nh][nw] == -1 and S[nh][nw] == '.':
            d.append([nh,nw])
            maze[nh][nw] = maze[ht][wt] + 1
    ans = max(ans,max(maze))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

for h in range(H):
  for w in range(W): #スタートが(h,w)
    if S[h][w] == '#':
      continue
    d = [[-1]*W for i in range(H)]
    d[h][w] = 0
    
    q = deque([[h,w]])
    
    while q:
      nh,nw = q.pop()
      
      if nw+1<W and S[nh][nw+1]=='.' and d[nh][nw+1]==-1:
        d[nh][nw+1] = d[nh][nw]+1
        q.append([nh,nw+1])
      if 0<=nw-1 and S[nh][nw-1]=='.' and d[nh][nw-1]==-1:
        d[nh][nw-1] = d[nh][nw]+1
        q.append([nh,nw-1])
      if nh+1<H and S[nh+1][nw]=='.' and d[nh+1][nw]==-1:
        d[nh+1][nw] = d[nh][nw]+1
        q.append([nh+1,nw])
      if 0<=nh-1 and S[nh-1][nw]=='.' and d[nh-1][nw]==-1:
        d[nh-1][nw] = d[nh][nw]+1
        q.append([nh-1,nw])
    a = max(a,max([max(i) for i in d]))
    
print(a)

Submission status: Runtime Error

Solution code:
from collections import deque

h,w=map(int,input().split())
S=[]
pos=[]
for i in range(h):
  l=input()
  L=[]
  for j in range(w):
    if l[j]=='.':
      L.append('.')
      pos.append((i,j))
    else:
      L.append('#')
  S.append(L)
Maze=[[float('inf')]*w for i in range(h)]
def bfs(h,w,S,maze,sy,sx,gy,gx):
    maze=Maze
    maze=[[float('inf')]*w for i in range(h)]
    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que: #キューの中に入っているということはまだ調べる余地有り
        y,x=que.popleft()
        for (i,j) in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<=h-1 and 0<=nextx<=w-1:
              dist=maze[nexty][nextx]
              if S[nexty][nextx]!='#':
                if dist>maze[y][x]+1: #今の経路から(nexty,nextx)に進む方が距離が短くなるなら
                    maze[nexty][nextx]=maze[y][x]+1
                    que.append([nexty,nextx])

    return maze[gy][gx]
M=0
for (sy,sx) in pos:
  for (gy,gx) in pos:
    if bfs(h,w,S,maze,sy,sx,gy,gx)>M:
      M=bfs(h,w,S,maze,sy,sx,gy,gx)

print(M)

Submission status: Runtime Error

Solution code:
work = [[[] for j in range(w)] for i in range(h)]
result = 0
for i in range(h):
    for j in range(w):
        append = work[i][j].append
        if i<h-1 and s[i+1][j] == ".":
            append([i+1,j])
        if i>0 and s[i-1][j] == ".":
            append([i-1,j])
        if j<w-1 and s[i][j+1] == ".":
            append([i,j+1])
        if j>0 and s[i][j-1] == ".":
            append([i,j-1])
for i in range(h):
    for j in range(w):
        if s[i][j] != ".":
            continue
        q = deque([[i, j]])
        temp = [[i, j]]
        popleft = q.popleft
        append = q.append
        d = -1
        count = 1
        counter = 0
        for k in range(h*w):
            x, y = popleft()
            count -= 1
            for el in work[x][y]:
                if el not in temp:
                    counter += 1
                    append(el)
                    temp.append(el)
            if count == 0:
                d += 1
                count = counter
                counter = 0
            if len(q) == 0:
                break
        result = result if result>d else d
print(result)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**8)
INF = float('inf')



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

def bfs(sy, sx):
  dist = [[0 for x in range(w)] for y in range(h)]
  dy = [0, 1, 0, -1]
  dx = [1, 0, -1, 0]
  Q = deque()
  Q.append((sy, sx))
  while Q:
    q = Q.popleft()
    y = q[0]
    x = q[1]
    d = dist[y][x]
    for i in range(4):
      ny = y + dy[i]
      nx = x + dx[i]
      if ny < 0 or h <= ny or nx < 0 or w <= nx:
        continue
      #迷路における道が'.'、壁が'#'で表されている場合
      if ny = sy and nx = sx:
        continue
      if maze[ny][nx] == '#':
        continue
      nd = d + 1
      if dist[ny][nx] != 0 and nd >= dist[ny][nx]:
        continue
      dist[ny][nx] = nd
      Q.append((ny, nx))
  return max(max(x) for x in dist)

ans = 0
for y in range(h):
  for x in range(w):
    if maze[y][x] == '.':
      ans = max(ans, bfs(y,x))
print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
from collections import deque
from itertools import product
import numpy as np
inputs = open(0).readlines()
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val
        
h, w = map(int, inputs[0].split())
grid_origin = Grid(inputs[1:], function=lambda x: int(x == '.'))

def bfs(root):
    x, y, _ = root
    grid[y, x] = 0
    queue = deque([root])
    while queue:
        x, y, d = queue.popleft()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            if grid.is_valid_xy(x+dx, y+dy) and grid[y+dy, x+dx]:
                queue.append((x+dx, y+dy, d+1))
                grid[y+dy, x+dx] = 0
    return d-1
    
ans = 0
for i, j in product(range(h), range(w)):
    if grid_origin[i, j]:
        grid = deepcopy(grid_origin)
        ans = max(ans, bfs((j, i)))
print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
from collections import deque
from itertools import product
import numpy as np
inputs = open(0).readlines()
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

h, w = map(int, inputs[0].split())
grid_origin = Grid(inputs[1:], function=lambda x: int(x == '.'))

def bfs(root):
    d = 0
    queue = deque([root])
    grid[root] = 0
    while queue:
        x, y = queue.popleft()
        d += 1
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            if grid.is_valid_xy(x+dx, y+dy) and grid[y+dy, x+dx]:
                queue.append((x+dx, y+dy))
                grid[y+dy, x+dx] = 0
    return d-1
    
ans = 0
for i, j in product(range(h), range(w)):
    if grid_origin[i, j]:
        grid = deepcopy(grid_origin)
        ans = max(ans, bfs((j, i)))
print(ans)