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:
from collections import deque

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

def bfs(grid, start):
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[1]][start[0]] = 0#start地点を0に
    
    while queue:#queueにたまっている間は処理を続ける
        x, y = queue.popleft()#今いる地点をpop
        
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):#左右上下に進むパターンをそれぞれ考える
            next_x, next_y = x+i, y+j#次に行く地点
            
            if 0 <= next_x < W and 0 <= next_y < H:#次の地点が範囲内にある場合
                if grid[next_y][next_x] == '.' and distance[next_y][next_x] == -1:#次の地点が壁ではなくかつ訪れたことがない場合
                    distance[next_y][next_x] = distance[y][x] + 1#訪れた印として現在までの距離に1を足す
                    queue.append((next_x, next_y))#訪れる先をqueueに詰めとく
        
        if not queue:#最後にqueueをpopし終えてなくなったら最後に出力
            return distance[y][x]
        
answer = 0
for i in range(H):
    for j in range(W):
        #スタート地点を決める
        
        if S[i][j] == '#':#スタート地点が壁
            continue

        tmp = bfs(S, (i, j))#このスタート地点での一番遠い距離
        
        if tmp > answer:#最大の距離
            answer = tmp

print(answer)

Submission status: Runtime Error

Solution code:
from collections import deque

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

def bfs(grid, start):
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0#start地点を0に
    
    while queue:#queueにたまっている間は処理を続ける
        x, y = queue.popleft()#今いる地点をpop
        
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):#左右上下に進むパターンをそれぞれ考える
            next_x, next_y = x+i, y+j#次に行く地点
            
            if 0 <= next_x < W and 0 <= next_y < H:#次の地点が範囲内にある場合
                if grid[next_y][next_x] == '.' and distance[next_y][next_x] == -1:#次の地点が壁ではなくかつ訪れたことがない場合
                    distance[next_y][next_x] = distance[y][x] + 1#訪れた印として現在までの距離に1を足す
                    queue.append((next_x, next_y))#訪れる先をqueueに詰めとく
        
        if not queue:#最後にqueueをpopし終えてなくなったら最後に出力
            return distance[y][x]
        
answer = 0
for i in range(H):
    for j in range(W):
        #スタート地点を決める
        
        if S[i][j] == '#':#スタート地点が壁
            continue

        tmp = bfs(S, (i, j))#このスタート地点での一番遠い距離
        
        if tmp > answer:#最大の距離
            answer = tmp

print(answer)

Submission status: Runtime Error

Solution code:
from pprint import pprint

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

# 入力
h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(list(input()))

# ワーシャルフロイド用に枠を作る。
# 2次元マップしてもいいが面倒なので、１次元にする。[0 - x][0 - y]を[0- x * y]にflattenする
wsmap = lambda a, b: (a * h + b)
dp = []
# 辺がない時はINFを入れのでデフォルト値とする
for i in range(h * w):
    dp.append([INF] * (h * w))

# 迷路ををグラフにする。
for y in range(h):
    for x in range(w):
        if maze[y][x] == "#": # そのマスが壁なら何もしない(他のマストの連結はないので)
            continue
        # ワーシャルフロイドでは自分自身へのコストは0にしておく。
        dp[wsmap(y, x)][wsmap(y, x)] = 0
        # ４方向に移動できるかの判定
        for dir in range(len(dx)):
            nx, ny = x + dx[dir], y + dy[dir]
            if -1 < nx < w and -1 < ny < h: # 枠をはみ出ないかチェック
                if maze[ny][nx] != "#": # そのマスが壁でないなら
                    dp[wsmap(y, x)][wsmap(ny, nx)] = 1 # コストを1にする

# ワーシャルフロイドする
for kk in range(h * w):
    for ii in range(h * w):
        for jj in range(h * w):
            dp[ii][jj] = min(dp[ii][jj], dp[ii][kk] + dp[kk][jj])

# これで結果が出たので
res = -1
for i in range(h * w):
    for j in range(h * w):
        if dp[i][j] != INF:
            res = max(res, dp[i][j])
print(res)

Submission status: Runtime Error

Solution code:
from pprint import pprint

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

# 入力
h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(list(input()))

# ワーシャルフロイド用に枠を作る。
# 2次元マップしてもいいが面倒なので、１次元にする。[0 - x][0 - y]を[0- x * y]にflattenする
wsmap = lambda a, b: (a * h + b)
dp = []
# 辺がない時はINFを入れのでデフォルト値とする
for i in range(h * w):
    dp.append([INF] * (h * w))

# 迷路ををグラフにする。
for y in range(h):
    for x in range(w):
        if maze[y][x] == "#": # そのマスが壁なら何もしない(他のマストの連結はないので)
            continue
        # ワーシャルフロイドでは自分自身へのコストは0にしておく。
        dp[wsmap(y, x)][wsmap(y, x)] = 0
        # ４方向に移動できるかの判定
        for dir in range(len(dx)):
            nx, ny = x + dx[dir], y + dy[dir]
            if -1 < nx < w and -1 < ny < h: # 枠をはみ出ないかチェック
                if maze[ny][nx] != "#": # そのマスが壁でないなら
                    dp[wsmap(y, x)][wsmap(ny, nx)] = 1 # コストを1にする

# ワーシャルフロイドする
for kk in range(h * w):
    for ii in range(h * w):
        for jj in range(h * w):
            dp[ii][jj] = min(dp[ii][jj], dp[ii][kk] + dp[kk][jj])

# これで結果が出たので
import itertools
res = itertools.chain(*dp) # 二次元配列を一次元にして
res = filter(lambda x: x != INF, res) # INFを取り除き
res = max(res) # 最大値を得る
print(res)

Submission status: Runtime Error

Solution code:
'''input
1 1
#
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	return str(arr[0]) + ' ' + str(arr[1])

def bfs(source, target):
	myq = deque()
	myq.append(mp(source))
	visited = dict()
	visited[mp(source)] = True
	dist = 0
	while len(myq) > 0:
		temp = deque()
		while len(myq) > 0:
			x, y  = list(map(int, myq.popleft().split()))
			if mp([x,y]) == mp(target):
				return dist
			if x - 1 >= 0 and maze[x - 1][y] != '#' and mp([x - 1, y]) not in visited:
				visited[mp([x -1, y])] = True
				temp.append(mp([x - 1, y]))
			if x  + 1 < n and maze[x + 1][y] != '#' and mp([x + 1, y]) not in visited:
				visited[mp([x + 1, y])] = True
				temp.append(mp([x + 1, y]))
			if y - 1 >= 0 and maze[x][y - 1] != '#' and mp([x, y - 1]) not in visited:
				visited[mp([x, y - 1])] = True
				temp.append(mp([x, y - 1]))
			if y + 1 < m and maze[x][y + 1] != '#' and mp([x, y + 1]) not in visited:
				visited[mp([x, y + 1])] = True
				temp.append(mp([x, y + 1]))
		dist += 1
		myq = temp
	return -float('inf')			


# main starts
n, m = list(map(int, input().split()))
maze = []
for _ in range(m):
	state = list(stdin.readline().strip())
	maze.append(state)

ans = -float('inf')
for i in range(n):
	for j in range(m):
		for x in range(n):
			for y in range(m):
				first = [i, j]
				second = [x, y]
				ans = max(ans, bfs(first, second))
print(ans)

Submission status: Runtime Error

Solution code:
'''input
3 3
...
...
...
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	return str(arr[0]) + ' ' + str(arr[1])

def bfs(source, target):
	myq = deque()
	myq.append(mp(source))
	visited = dict()
	visited[mp(source)] = True
	dist = 0
	while len(myq) > 0:
		temp = deque()
		while len(myq) > 0:
			x, y  = list(map(int, myq.popleft().split()))
			if mp([x,y]) == mp(target):
				return dist
			if x - 1 >= 0 and maze[x - 1][y] != '#' and mp([x - 1, y]) not in visited:
				visited[mp([x -1, y])] = True
				temp.append(mp([x - 1, y]))
			if x  + 1 < n and maze[x + 1][y] != '#' and mp([x + 1, y]) not in visited:
				visited[mp([x + 1, y])] = True
				temp.append(mp([x + 1, y]))
			if y - 1 >= 0 and maze[x][y - 1] != '#' and mp([x, y - 1]) not in visited:
				visited[mp([x, y - 1])] = True
				temp.append(mp([x, y - 1]))
			if y + 1 < m and maze[x][y + 1] != '#' and mp([x, y + 1]) not in visited:
				visited[mp([x, y + 1])] = True
				temp.append(mp([x, y + 1]))
		dist += 1
		myq = temp
	return -float('inf')			


# main starts
n, m = list(map(int, input().split()))
maze = []
for _ in range(m):
	state = list(stdin.readline().strip())
	maze.append(state)

ans = -float('inf')
for i in range(n):
	for j in range(m):
		for x in range(n):
			for y in range(m):
				first = [i, j]
				second = [x, y]
				ans = max(ans, bfs(first, second))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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


def bfs(initial):
    # goal判定はなく、一番遠いところで返す
    distance = [[-1] * W for _ in range(H)]
    frontier = deque()
    frontier.append(initial) 
    while len(frontier):
        locations = []
        current_node = frontier.popleft()
        current_state = current_node[0]
        x, y = current_state
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_x, new_y = x + i, y + j
            if 0 <= new_x < H and 0 <= new_y < H:
                if maze[new_x][new_y] == '.' and maze[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    frontier.append((new_x, new_y))
    return distance[x][y]


ans = 0
for x in range(H):
    for y in range(W):
        if maze[x][y] == '#':
            continue
        solution = bfs((x, y))
        if ans < solution:
            ans = solution

print(ans)

Submission status: Runtime Error

Solution code:
def Warshall_floyd(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

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

d = [[float("inf") for i in range(N)] for i in range(N)] 

M = [[1 for i in range(W+1)] for i in range(H+1)]
for i in range(H):
    m = input().strip()
    for j in range(W):
        if m[j] == '.':
            M[i][j] = 0

for i in range(H):
    for j in range(W):
        if M[i][j] == 0:
            d[W*i+j][W*i+j] = 0
            if M[i][j+1] == 0:
                d[W*i+j][W*i+j+1] = 1
                d[W*i+j+1][W*i+j] = 1
            if M[i+1][j] == 0:
                d[W*i+j][W*(i+1)+j] = 1
                d[W*(i+1)+j][W*i+j] = 1

o = warshall_floyd(d, N)
ans = 0
for i in range(N):
    for j in range(N):
        if o[i][j] != float('inf'):
            ans = max(ans, o[i][j])
print(ans)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(input()))
s=[]
for i in range(h):
    for j in range(w):
        if l[i][j]=='.':
            s.append([i,j])
def solve(s):
    v=[[0 for i in range(w)] for j in range(h)]       
    v[s[0]][s[1]]=1
    mc=0
    q=[[s,0]]
    while len(q):
        p=q.pop(0)
        x=p[0][0]
        y=p[0][1]
        c=p[1]
        k=[[0,1],[0,-1],[1,0],[-1,0]]
        for j in k:
            nx=x+j[0]
            ny=y+j[1]
            if 0<=nx<h and 0<=ny<w and l[nx][ny]=='.' and v[nx][ny]==0:
                v[nx][ny]=1
                q.append([[nx,ny],c+1])
                if mc<=c+1:
                    mc=c+1
                    # ms=[nx,ny]
    return mc
ans=
exit()

v=[[0 for i in range(w)] for j in range(h)]       
v[ms[0]][ms[1]]=1
ans=0
q=[[ms,0]]
while len(q):
    p=q.pop(0)
    x=p[0][0]
    y=p[0][1]
    c=p[1]
    k=[[0,1],[0,-1],[1,0],[-1,0]]
    for j in k:
        nx=x+j[0]
        ny=y+j[1]
        if 0<=nx<h and 0<=ny<w and l[nx][ny]=='.' and v[nx][ny]==0:
            v[nx][ny]=1
            q.append([[nx,ny],c+1])
            ans=max(ans,c+1)
                #ms=[nx,ny]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(grid, start):
    H, W = len(grid), len(grid[0])
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()
 
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return max(map(max, distance))

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


res = -1
for i in range(h):
    for j in range(w):
        if(maze[i][j] == '#'): continue
        tmpmaze = copy.deepcopy(maze)
        steps = bfs(tmpmaze, [i, j])
        if(steps > res):
            res = steps
print(res)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(grid, start):
    H, W = len(maze), len(maze[0])
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()
 
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return max(map(max, distance))

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


res = -1
for i in range(h):
    for j in range(w):
        if(maze[i][j] == '#'): continue
        tmpmaze = copy.deepcopy(maze)
        steps = bfs(tmpmaze, [i, j])
        if(steps > res):
            res = steps
print(res)

Submission status: Runtime Error

Solution code:
# BFS queue
import queue
import copy

import time
sss = time.time()
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**2 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
# start把握
for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start, bb):
    dist = [[10**2 for _ in range(W)] for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    # BFS
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        olddist = dist[x][y]
        bb[x][y] = '#'
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            x+dx = xx
            y+dy = yy
            if xx>=0 and xx<= H-1 and yy>=0 and yy<=W-1:
                if bb[xx][yy] != '#':
                    if dist[xx][yy] > olddist:
                        dist[xx][yy] = olddist + 1
                        far = max([far,olddist+1])
                        q.put((xx,yy))
        if q.empty():
            break
    return far
res = 0
while 1:
    ttt = time.time()
    if sss-ttt >= 1.8:
        break
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)

Submission status: Runtime Error

Solution code:
from copy import deepcopy as dcopy
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
def mostfar(sx,sy,s):
  if s[sy][sx]=='#':
    return -1
  mx=len(s)*len(s[0])-1
  l=[[mx if s[j][i]=='.' else -1 for i in range(w)] for j in range(h)]
  step=0
  l[sy][sx]=0
  tmp=dcopy(l)
  while 1:
    step+=1
    print(step)
    for x in range(w):
      for y in range(h):
        if l[y][x]==step-1:
          if x!=0:
            l[y][x-1]=min(l[y][x-1],step)
          if x!=w-1:
            l[y][x+1]=min(l[y][x+1],step)
          if y!=0:
            l[y-1][x]=min(l[y-1][x],step)
          if y!=h-1:
            l[y+1][x]=min(l[y+1][x],step)
    if tmp==l:
      break
    tmp=dcopy(l)
  return max([max(r) for r in l])

ans=max(max([mostfar(x,y,s)] for x in range(w)) for y in range(h))
print(mostfar(3,0,s))

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())

maze = [list(input()) for _ in range(h)]
#print(maze)
ans = 0
def solve(sx, sy):
    reached = [[0 for _ in range(w)] for _ in range(h)]
    d = deque()
    d.append([sx, sy])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]    
    while d:
        x, y = d.popleft()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if next_x < 0 or next_x > h - 1 or next_y < 0 or next_y > w - 1:
                continue
            if maze[next_x][next_y] == "#":
                continue
            if reached[next_x][next_y] != 0:
                continue
            d.append([next_x, next_y])
            reached[next_x][next_y] = reached[x][y] + 1
    return max(reached)

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            res = solve(i, j)
            ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
)

// -----------------------------------------------------------------------------

// IO helper functions

// Returns next token from input.  It must be initialized by SetInput()
// before the first call.
var nextToken func() ([]byte, error)
var nextLine func() ([]byte, error)

// Holds a buffer for output.  It must be initialized by SetOutput().
// All IO fucntions (read*() and [e]print*()) should write to OutputWriter
// instead of this.
var OutputBuffer *bufio.Writer

// Holds an io.Writer.  It must be initialized by SetOutput()
var OutputWriter io.Writer

// Set IO functions for interactive input/output.
func SetInteractive(w io.Writer, r io.Reader) {
	SetUnbefferedInput(r)
	OutputBuffer = nil
	OutputWriter = w
}

// Setup OutputBuffer and OutputWriter.
func SetOutput(w io.Writer) {
	OutputBuffer = bufio.NewWriter(w)
	OutputWriter = OutputBuffer
}

// Flushes OutputBuffer
func Flush() {
	if OutputBuffer != nil {
		OutputBuffer.Flush()
	}
}

// Returns true if c is a white space
func IsSpace(c byte) bool {
	switch c {
	case '\t', '\n', '\v', '\f', '\r', ' ':
		return true
	}
	return false
}

func IsNewLine(c byte) bool {
	switch c {
	case '\n', '\r':
		return true
	}
	return false
}

// Setup nextToken with input buffer.
func SetInput(r io.Reader) {
	buf := new(bytes.Buffer)
	var b []byte

	var i int
	rest := func() ([]byte, error) {
		for i < len(b) && IsSpace(b[i]) {
			i++
		}
		if i == len(b) {
			return nil, io.ErrUnexpectedEOF
		}
		j := i
		for i < len(b) && !IsSpace(b[i]) {
			i++
		}
		return b[j:i], nil
	}
	initial := func() ([]byte, error) {
		io.Copy(buf, r)
		b = buf.Bytes()
		nextToken = rest
		return rest()
	}
	nextToken = initial

	restLn := func() ([]byte, error) {
		for i < len(b) && IsNewLine(b[i]) {
			i++
		}
		if i == len(b) {
			return nil, io.ErrUnexpectedEOF
		}
		j := i
		for i < len(b) && !IsNewLine(b[i]) {
			i++
		}
		return b[j:i], nil
	}

	initialLn := func() ([]byte, error) {
		io.Copy(buf, r)
		b = buf.Bytes()
		nextLine = restLn
		return restLn()
	}
	nextLine = initialLn
}

// Setup nextToken without input buffer.
func SetUnbefferedInput(r io.Reader) {
	buf := bufio.NewReader(r)
	var b []byte

	var i int
	nextToken = func() ([]byte, error) {
		var err error
		if i == len(b) {
			b, err = buf.ReadBytes('\n')
			if err != nil {
				return nil, err
			}
			i = 0
			j := len(b) - 1
			for 0 <= j && IsSpace(b[j]) {
				j--
			}
			b = b[0 : j+1]
		}
		for i < len(b) && IsSpace(b[i]) {
			i++
		}
		j := i
		for i < len(b) && !IsSpace(b[i]) {
			i++
		}
		if i == j {
			return nil, io.ErrUnexpectedEOF
		}
		return b[j:i], nil
	}
}

// -----------------------------------------------------------------------------

// IO functions

// Reads next token and return it as []byte
func readb() []byte {
	b, err := nextToken()
	if err != nil {
		panic(err)
	}
	return b
}

// Reads next token and return it as string
func reads() string {
	return string(readb())
}

// Read next line as []byte
func readbln() []byte {
	b, err := nextLine()
	if err != nil {
		panic(err)
	}
	return b
}

// Read next line as string
func readsln() string {
	return string(readbln())
}

// Reads next token and return it as int64
func readll() int64 {
	i, err := strconv.ParseInt(reads(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

// Reads next token and return it as int
func readi() int {
	return int(readll())
}

// Reads next token and return it as float64
func readf() float64 {
	f, err := strconv.ParseFloat(reads(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

// Write args to OutputWriter with the format f
func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(OutputWriter, f, args...)
}

// Write args to OutputWriter without format
func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(OutputWriter, args...)
}

// Write args to stderr with the format f
func eprintf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(os.Stderr, f, args...)
}

// Write args to stderr without format
func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

// -----------------------------------------------------------------------------

// Simple math functions

const (
	// big prime
	INF  = 1000000007
	INF2 = 1000000009
	INF3 = 998244353
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func minll(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxll(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absll(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

// egcd(a, b) returns d, x, y:
//   d is gcd(a,b)
//   x, y are  integers that satisfy ax + by = d
func egcd(a, b int) (int, int, int) {
	if b == 0 {
		return a, 1, 0
	}
	d, x, y := egcd(b, a%b)
	return d, y, x - a/b*y
}

func egcdll(a, b int64) (int64, int64, int64) {
	if b == 0 {
		return a, 1, 0
	}
	d, x, y := egcdll(b, a%b)
	return d, y, x - a/b*y
}

func gcd(a, b int) int {
	d, _, _ := egcd(a, b)
	return d
}

func gcdll(a, b int64) int64 {
	d, _, _ := egcdll(a, b)
	return d
}

// set up IO functions
func init() {
	// for non-interactive
	SetInput(os.Stdin)
	SetOutput(os.Stdout)

	// Enable below when interactive.  Its ok to leave above intact.
	// SetInteractive(os.Stdout, os.Stdin)
}

func main() {
	defer Flush()

	H := readi()
	W := readi()
	S := make([][]byte, H)
	for i := range S {
		S[i] = readb()
	}

	var ans int
	for i := range S {
		for j := range S[i] {
			ans = max(ans, calc(S, H, W, i, j))
		}
	}
	println(ans)
}

func calc(S [][]byte, H, W, i, j int) int {
	f := make([][]int, H)
	if S[i][j] == '#' {
		return 0
	}
	for i := range f {
		f[i] = make([]int, W)
		for j := range f[i] {
			f[i][j] = INF
		}
	}

	q := make([][2]int, 0)
	push := func(y, x int) {
		q = append(q, [2]int{y, x})
	}
	pop := func() (int, int) {
		res := q[0]
		q = q[1:]
		return res[0], res[1]
	}

	f[i][j] = 0
	push(i, j)
	dy := []int{-1, 0, 1, 0}
	dx := []int{0, -1, 0, 1}
	var res int
	for len(q) != 0 {
		y, x := pop()
		res = max(res, f[y][x])
		for i := range dy {
			ny := y + dy[i]
			nx := x + dx[i]
			if ny < 0 || H <= ny || nx < 0 || W <= nx || S[ny][nx] == '#' {
				continue
			}
			nd := f[y][x] + 1
			if f[ny][nx] <= nd {
				continue
			}
			f[ny][nx] = nd
			push(ny, nx)
		}
	}
	return res
}

Submission status: Runtime Error

Solution code:
from collections import deque    
H,W = map(int, input().split())
maze = []
ans = 0
dist =[]
q = deque([])

for i in range(H):
    maze.append(input())

for i in range(H):
    for j in range(W):
        dist = [[-1]*W for i in range(H)] # 配列の初期化
        q.append([i,j]) #初期値挿入
        dist[i][j] = 0
        while(q):
            a,b = q.popleft()
            if a + 1 < H:
                if maze[a+1][b] == '.' and dist[a+1][b] == -1:
                    q.append([a+1, b])
                    dist[a+1][b] = dist[a][b] + 1
                    tmp = dist[a+1][b] 
            if a > 0:
                if maze[a-1][b] == '.' and dist[a-1][b] == -1:
                    q.append([a-1, b])
                    dist[a-1][b] = dist[a][b] + 1
                    tmp = dist[a-1][b]
            if b + 1 < W:
                if maze[a][b+1] == '.' and dist[a][b+1] == -1:
                    q.append([a, b+1])
                    dist[a][b+1] = dist[a][b] + 1
                    tmp = dist[a][b+1]
            if b > 0:
                if maze[a][b-1] == '.' and dist[a][b-1] == -1:
                    q.append([a, b-1])
                    dist[a][b-1] = dist[a][b] + 1
                    tmp = dist[a][b-1]
        ans = max(ans,tmp)


print(ans)

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='#':
          A[h][w]=0
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
        
    A = [a for a in b for b in A if a!=inf]
    ans = max(ans,max(max(A)))
    
print(ans)

Submission status: Runtime Error

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

def bfs(h,w):
  checked = [[False for i in range(W)] for j in range(H)]
  q = [(h,w,0)] if maze[h][w]=="." else []
  g_n = 0
  while q:
    h_,w_,n = q.pop(0)
    g_n = max(n, g_n)
    for i,j in zip([0,0,-1,1],[-1,1,0,0]):
      if (0<=h_+i<H) and (0<=w_+j<W):
        if checked[h_+i][w_+j]: continue
        checked[h_+i][w_+j] = True
        if maze[pt[0]][pt[1]]==".": q.append((h_+i,w_+j,n+1))
  return g_n

n = 0
for i in range(H):
  for j in range(W):
    n = max(n, bfs(i,j))
print(n)

Submission status: Runtime Error

Solution code:
import sys
from copy import deepcopy
from collections import deque

h, w = map(int, inputs[0].split())
S = deque(deque(map(lambda x: int(x=='.'), x)) for x in inputs[1:])
S.appendleft(deque([0]*w))
S.append(deque([0]*w))
for row in S:
    row.appendleft(0)
    row.append(0)

max_dist = 0
for y in range(1, h+1):
    for x in range(1, w+1):
        if S[y][x]:
            maze = deepcopy(S)
            queue = deque([(x, y, 0)])
            while queue:
                x, y, d = queue.popleft()
                d += 1
                maze[y][x] = 0
                for dx, dy in zip([0, 1, 0, -1], [-1, 0, 1, 0]):
                    if maze[y+dy][x+dx]:
                        queue.append((x+dx, y+dy, d))
                        maze[y+dy][x+dx] = 0
                        max_dist = max(max_dist, d)
print(max_dist)

Submission status: Runtime Error

Solution code:
from collections import deque

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

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue

        q = deque()
        q.append([i, j, 0])
        visited = [[False for _ in range(h + 5)] for _ in range(w + 5)]
        dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        while len(q) != 0:
            x, y, z = q[0]
            ans = max(ans, z)
            visited[x][y] = True
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
            q.popleft()
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque

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

visited = np.zeros((h + 5, w + 5), dtype = bool)
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue

        q = deque()
        q.append([i, j, 0])
        dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        while len(q) != 0:
            x, y, z = q[0]
            ans = max(ans, z)
            visited[x][y] = True
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
            q.popleft()
        for a in range(h): for b in range(w): visited[a][b] = False
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque

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

visited = np.zeros((h + 5, w + 5), dtype = bool)
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue

        q = deque()
        q.append([i, j, 0])
        dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        while len(q) != 0:
            x, y, z = q[0]
            ans = max(ans, z)
            visited[x][y] = True
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
            q.popleft()
        for a in range(h): for b in range(b): visited[a][b] = False
print(ans)