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.

Solution (Python):
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    st = [(h, w) for h in range(H) for w in range(W)]  

    def bfs(sy, sx):
        que = deque()
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))

    ans = 0
    for s in st:
        dist = [[-1]*W for h in range(H)]
        if c[s[0]][s[1]] == "
            continue
        bfs(s[0], s[1])
        for t in st:
            if s == t or c[t[0]][t[1]] == "
                continue
            ans = max(ans, dist[t[0]][t[1]])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


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

S = [["


ans = 0


for r in range(1, H-1):
    for c in range(1, W-1):
        if S[r][c] == "
            continue

        
        dist = [[-1]*W for _ in range(H)]
        dist[r][c] = 0

        dq = deque([(r, c)])

        while dq:
            cr, cc = dq.popleft()
            
            if dist[cr][cc] > ans:
                
                ans = dist[cr][cc]
            
            for nr, nc in ((cr+1, cc), (cr-1, cc), (cr, cc+1), (cr, cc-1)):
                if S[nr][nc] == "." and dist[nr][nc] == -1:
                    dist[nr][nc] = dist[cr][cc]+1
                    dq.append((nr, nc)) 


print(ans)

Solution (Python):

def get_next_str():
    return input().rstrip("\n")
def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])
def solve(maze, start_r, start_c):
    
    distances = {}
    offsets = [(-1,0),(1,0),(0,-1),(0,1)]
    
    distances[start_r, start_c] = 0
    candidates = [(start_r, start_c)]
    
    while candidates:
        r, c= candidates.pop(0)
        
        for offset_r, offset_c in offsets:
            move_r, move_c = r + offset_r, c + offset_c
            if not (move_r, move_c) in distances and maze[move_r, move_c] == ".":
                distances[move_r, move_c] = distances[r, c] + 1
                candidates.append((move_r, move_c))
    
    return max(distances.values())
    

def main():
    h, w = get_next_ints()
    from collections import defaultdict
    maze = defaultdict(str)
    for r in range(h):
        line = get_next_str()
        for c in range(w):
            maze[r,c] = line[c]
    
    results = []
    for r in range(h):
        for c in range(w):
            if maze[r,c] != "
                result = solve(maze, r, c)
                results.append(result)
    
    print(max(results))
    
if __name__ == '__main__':
    main()

Solution (Python):
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 

def BFS(dziecko, listy_znajomosci): 
    do_przejrzenia = [dziecko]
    odleglosc = {dziecko:0}
    nr_przegladanego = 0 
    while nr_przegladanego < len(do_przejrzenia): 
        aktualnie_przegladany = do_przejrzenia[nr_przegladanego]
        for kumpel in listy_znajomosci[aktualnie_przegladany]: 
            if kumpel not in odleglosc: 
                do_przejrzenia.append(kumpel)
                odleglosc[kumpel] = odleglosc[aktualnie_przegladany] + 1 
        nr_przegladanego +=1
    return max(odleglosc.values())

def labirynt(): 
    H, W = wczytaj_liste()
    labirynt = []
    for i in range(H): 
        rzadek = [x for x in (input() + '
        labirynt.append(rzadek)
    labirynt.append(['
    lista_krawedzi = []
    for i in range(H):
        for j in range(W):
            if labirynt[i][j] == '.':
                if labirynt[i+1][j] == '.':
                    lista_krawedzi.append(((i,j),(i+1,j)))
                if labirynt[i][j+1] == '.':
                    lista_krawedzi.append(((i,j),(i,j+1)))
    listy_krawedzi = {}
    for x, y in lista_krawedzi:
        listy_krawedzi[x] = []
        listy_krawedzi[y] = []
    for x, y in lista_krawedzi:  
        listy_krawedzi[x].append(y)
        listy_krawedzi[y].append(x)
    maksymalny = 0
    for i in range(H):
        for j in range(W):
            if labirynt[i][j] == '.':
                kandydat = BFS((i,j),listy_krawedzi)
                if kandydat > maksymalny: 
                    maksymalny = kandydat
    print(maksymalny)

labirynt()

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

maze = [list(input()) for _ in range(h)]
directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
]

def bfs(start):

    visited = [[False] * w for _ in range(h)]
    que = deque([start + (0,)])

    max_cnt = -1
    while que:
        y, x, cnt = que.popleft()
        if 0 <= x < w and 0 <= y < h and maze[y][x] == '.' and not visited[y][x]:
            max_cnt = max(cnt, max_cnt)
            visited[y][x] = cnt + 1
            for dy, dx in directions:
                que.append((y + dy, x + dx, visited[y][x]))
    
    return max_cnt

ans = 0
for sx in range(w):
    for sy in range(h):
        ans = max(ans, bfs((sy, sx)))
print(ans)

Solution (Python):
from collections import deque

def mk_idx(y,x):
    return y*22+x

H,W=map(int, input().split())
DINF = 100000
S = []
S.append('
for i in range(H):
    S.append('
S.append('
dmax = 0
G = [ [] for _ in range( mk_idx(22,22) ) ]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y][x] == '.'):
            if (S[y-1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y-1,x) )
            if (S[y][x-1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x-1) )
            if (S[y+1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y+1,x) )
            if (S[y][x+1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x+1) )

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            d = [ DINF for _ in range( mk_idx(22,22) ) ]
            d[ mk_idx(y,x) ] = 0
            q = deque( [mk_idx(y,x)] )
            while len(q) != 0:
                v = q.popleft()
                n = d[v];
                dmax = max(dmax, n)
                for nv in G[v]:
                    if d[ nv ] <= n+1 :
                        continue
                    d[ nv ] = n+1
                    q.append(nv)
print(dmax)

Solution (Python):
from collections import deque

h, w = map(int, (input().split()))
maze = ['
directions = [[0, -1], [-1, 0], [1, 0], [0, 1]]
queue = deque()
answer = 0

for start_x in range(1, h + 1):
    for start_y in range(1, w + 1):
        if maze[start_x][start_y] == '.':
            distance = [[-1] * (w + 2) for i in range(h + 2)]
            distance[start_x][start_y] = 0
            queue.append([start_x, start_y])
            while queue:
                x, y = queue.popleft()
                for direction in directions:
                    next_x, next_y = x + direction[0], y + direction[1]
                    if maze[next_x][next_y] == '.' and distance[next_x][next_y] == -1:
                        distance[next_x][next_y] = distance[x][y] + 1
                        queue.append([next_x, next_y])
                        answer = max(answer, distance[next_x][next_y])

print(answer)

Solution (Python):
from collections import deque

def bfs(maze, sy, sx):
    visited = [[-1 for _ in range(W+2)] for _ in range(H+2)]
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    dist = 0
    
    while queue:
        y, x = queue.popleft()
        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])
                dist = max(dist, visited[new_y][new_x])
    return(dist)

H, W = map(int, input().split())
maze = ["
maze += ["
maze += ["

ans=0

for i in range(1, H+1):
    for j in range(1,W+1):
        if maze[i][j] == ".":
            ans = max(ans, bfs(maze, i, j))

print(ans)

Solution (Python):
from sys import stdin


def input():
	return stdin.readline().strip()

from collections import defaultdict, deque

R, C = map(int, input().split())

grid = [None]*R

for i in range(R):
	temp = input()
	grid[i] = temp

def get_neighs(r, c):
	is_valid = lambda x, y: 0 <= x < R and 0 <= y < C and grid[x][y]=='.'
	dr = [-1, 0, 1, 0]
	dc = [0, 1, 0, -1]
	return [(r+dr[i], c+dc[i]) for i in range(4) if is_valid(r+dr[i], c+dc[i])]


def get_max(r0, c0):
	visited = {(r0, c0),}
	dq = deque()
	dq.append((r0, c0, 0))
	max_steps = 0
	while dq:
		r, c, steps = dq.popleft()
		max_steps = max(max_steps, steps)
		for _r, _c in get_neighs(r, c):
			if (_r, _c) not in visited:
				dq.append((_r, _c, steps+1))
				visited.add((_r, _c))
	return max_steps

ans = 0
for r in range(R):
	for c in range(C):
		if grid[r][c]=='.':
			ans = max(get_max(r, c), ans)
print(ans)

Solution (Python):
import numpy as np

def bfs(que):
  if len(que) > 0:
    nh, nw = que[0]
    que.pop(0)
    for dh, dw in directions:
      
      if not ((0 <= nh+dh < H)and(0 <= nw+dw < W)):
        continue
      
      if G[nh+dh][nw+dw] == '
      	continue
   	  
      if dist[nh+dh][nw+dw] != -1:
      	continue
      dist[nh+dh][nw+dw] = dist[nh][nw]+1
      que.append([nh+dh, nw+dw])
    nh += dh
    nw += dw
    bfs(que)

    
      
ans_list = []
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]
directions = [[0,1],[1,0],[0,-1],[-1,0]] 

for nh in range(H):
  for nw in range(W):
    if G[nh][nw] == '
      continue
    dist = [[-1] * W for i in range(H)]
    que = [[nh,nw]] 
    dist[nh][nw] = 0
    bfs(que)
    ans = np.max(dist)
    ans_list.append(ans)
      
print(max(ans_list))

Solution (Python):
from collections import deque


def find_farthest(adj, start):
    distance = [float("inf")] * len(adj)
    q = deque([(start, 0)])
    while len(q):
        cur, d = q.popleft()
        if distance[cur] <= d:
            continue
        distance[cur] = d
        for nxt in adj[cur]:
            if distance[nxt] > d+1:
                q.append((nxt, d+1))
    ret = 0
    for i, d in enumerate(distance):
        if d != float("inf"):
            ret = max(ret, d)
    return ret


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    adj = [set() for _ in range(H*W)]
    start = None
    for i in range(H):
        for j in range(W):
            if S[i][j] == "
                continue
            if i >= 1 and S[i-1][j] == ".":
                adj[i*W+j].add((i-1)*W+j)
                adj[(i-1)*W+j].add(i*W+j)
            if j >= 1 and S[i][j-1] == ".":
                adj[i*W+j].add(i*W+(j-1))
                adj[i*W+(j-1)].add(i*W+j)
            start = i*W+j
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                ans = max(ans, find_farthest(adj, i*W+j))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]

h, w = map(int, input().split())
s = ["
h += 2
w += 2

s = ["


res_opt = -2


for h_i in range(h):
  for w_i in range(w):
    if s[h_i][w_i] != '
      
      visited = [ [-1] * w for _ in range(h) ]
      visited[h_i][w_i] = 0
      queue = deque([(h_i, w_i)])
      
      while queue:
        y, x = queue.popleft()
        
        
        opt = 0
        for i in range(4):
          
          dx, dy = dis_x[i], dis_y[i]
          if s[y+dy][x+dx] == '.' and visited[y+dy][x+dx] == -1:
            visited[y+dy][x+dx] = visited[y][x] + 1
            opt = max(opt, visited[y+dy][x+dx])
            queue.append((y+dy, x+dx))
        res_opt = max(res_opt, opt)

print(res_opt)

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

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

Solution (Python):
from collections import deque

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


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


directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]

ans = 0
for sh in range(H):
    for sw in range(W):
        
        if G[sh][sw] == '
            
            continue
        
        
        
        dist = [[-1] * W for i in range(H)]
        
        dist[sh][sw] = 0
        
        que = deque([[sh, sw]])
        
        
        
        while que:
            
            nh, nw = que.pop()
            
            
            for dh, dw in directions:
                
                if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
                    continue
                    
                
                if G[nh + dh][nw + dw] == '
                    continue
                    
                
                if dist[nh + dh][nw + dw] != -1:
                    continue
                
                
                dist[nh + dh][nw + dw] = dist[nh][nw] + 1
                
                que.appendleft([nh + dh, nw + dw])
                
                                
        ans = max(ans, max([max(d) for d in dist]))
print(ans)

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

def bfs(sw,sh):
    res = 0
    dw = [-1,1,0,0]
    dh = [0,0,1,-1]
    dist = [[-1 for _ in range(h)] for _ in range(w)]
    dist[sw][sh] = 0
    queue = deque()
    queue.append((sw,sh))
    while len(queue) != 0:
        cw,ch = queue.popleft()
        for i in range(4):
            nw,nh = cw + dw[i], ch + dh[i]
            if not (0<= nw < w and 0 <= nh < h): continue
            if path[nw][nh] == "
            if dist[nw][nh] != -1: continue
            dist[nw][nh] = dist[cw][ch] + 1
            queue.append((nw,nh))
            res = max(res, dist[nw][nh])
    return res

ans = 0
for i in range(w):
    for j in range(h):
        if path[i][j] == "
            continue
        ans = max(ans, bfs(i,j))
print(ans)

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

def bfs(sh,sw):
    dh = (1,-1,0,0)
    dw = (0,0,1,-1)
    dist = [[-1 for _ in range(w)] for _ in range(h)]
    queue = deque()
    queue.append((sh,sw))
    dist[sh][sw] = 0
    while len(queue) != 0:
        ch,cw = queue.popleft()
        for i in range(4):
            nh,nw = ch+dh[i],cw+dw[i]
            if not (0 <= nh <= h-1 and 0 <= nw <= w-1): continue
            if s[nh][nw] == "
            if dist[nh][nw] != -1: continue
            queue.append((nh,nw))
            dist[nh][nw] = dist[ch][cw]+1
    return dist[ch][cw]

for sh in range(h):
    for sw in range(w):
        if s[sh][sw] == "
            continue
        ans = max(ans,bfs(sh,sw))
        
print(ans)

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

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

Solution (Python):
from collections import *
from itertools import *
h, w = map(int, input().split())
maze = [input() for _ in range(h)]
dest = [(1, 0), (-1, 0), (0, 1), (0, -1)]
score = 0

for sx, sy in product(range(w), range(h)):
  if maze[sy][sx] == '
    continue
  r = [[-1] * w for _ in range(h)]
  r[sy][sx] = 0
  queue = deque([(sx, sy)])
  while queue:
    x, y = queue.popleft()
    for dx, dy in dest:
      nx, ny = x + dx, y + dy
      if not (0 <= nx < w and 0 <= ny < h):
        continue
      if maze[ny][nx] == '
        continue
      r[ny][nx] = r[y][x] + 1
      queue.append((nx, ny))
      score = max(score, r[ny][nx])
print(score)

Solution (Python):
import queue
dx=[1,0,-1,0]
dy=[0,1,0,-1]
H,W=map(int,input().split())
S=[]
for h in range(H):
  S.append(input())

def bfs(s):
  dist = [[-1]*W for _ in range(H)]
  
  h,w = s
  dist[h][w]=0
  que = queue.Queue()
  que.put(s)
  
  while not(que.empty()):
    h,w = que.get()
    for d in range(4):
      nh = h + dx[d]
      nw = w + dy[d]
      if nh<0 or H<=nh or nw<0 or W<=nw:
        continue
      if S[nh][nw]=="
        continue
      if dist[nh][nw]==-1:
        dist[nh][nw]=dist[h][w]+1
        que.put([nh,nw])
  return dist[h][w]

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

Solution (Python):

def bfs_len_max(ind,graph,q_num):
    distance_arr=[0 if i==ind  else -1 for i in range(len(graph))]
    q=[-1 for _ in range(q_num)]
    q[0]=ind
    l=1
    n=0
    while len(q)>l:
        for i in graph[ind]:
            if distance_arr[i]==-1:
                distance_arr[i]=distance_arr[ind]+1
                q[l]=i
                l+=1
        
        
        
        
        n+=1
        ind=q[n]


    return distance_arr
    

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




q_num=0
graph=[[] for _ in range(n*m)]
for i in range(n):
    for j in range(m):
        if maze[i][j]=="
            continue
        ind=i*m+j
        q_num+=1
        
        if i!=0:
            if maze[i-1][j]!="
                graph[ind].append((i-1)*m+j)
        if i!=n-1:
            if maze[i+1][j]!="
                graph[ind].append((i+1)*m+j)
        if j!=0:
            if maze[i][j-1]!="
                graph[ind].append(i*m+j-1)

        if j!=m-1:
            if maze[i][j+1]!="
                graph[ind].append(i*m+j+1)

ans=0
for s in range(m*n):
    if len(graph[s])==0:
        continue
    
    tmp=bfs_len_max(s,graph,q_num)
    
    ans=max(ans,max(tmp))
    
print(ans)

Solution (Python):
from collections import deque, defaultdict
from itertools import chain, combinations
import json


def main():
    
    H, W = [int(a) for a in input().split()]
    S = [
        input()
        for _ in range(H)
    ]

    def saitan(start, end):
        mem = {start}

        def get_rinsetsu(ii, jj):
            d = [
                (1, 0),
                (-1, 0),
                (0, 1),
                (0, -1),
            ]
            res = []
            for di, dj in d:
                ni = ii + di
                nj = jj + dj
                if ni < 0 or nj < 0:
                    continue
                if ni >= H or nj >= W:
                    continue
                if S[ni][nj] == '.':
                    if (ni, nj) not in mem:
                        res.append((ni, nj))
            return res

        q = [(start, 0)]
        while len(q) != 0:
            (i, j), distance = q.pop(0)
            rinsetsu = get_rinsetsu(i, j)
            for r in rinsetsu:
                if r == end:
                    return distance + 1, mem
                q.append((r, distance + 1))
                mem.add(r)
        return -1, mem

    res = -1
    for a in range(H * W):
        start = a // W, a % W
        mm = set()
        if S[start[0]][start[1]] == '
            continue
        for b in range(a + 1, H * W):
            end = b // W, b % W
            if S[end[0]][end[1]] == '
                continue
            if end in mm:
                continue
            ddd, m = saitan(start, end)
            mm |= m
            res = max(res, ddd)
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
import copy
from collections import deque

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

input_maze=[]
for i in range(h):
	input_maze.append(list(input()))

maze=[[-1 for j in range(w+2)] for i in range(h+2)]


for i in range(h):
    for j in range(w):
        if input_maze[i][j]=='.':
            maze[i+1][j+1]=0
        else:
            maze[i+1][j+1]=-1



max_route=0
direction=[[1,0],[-1,0],[0,1],[0,-1]]
for i in range(h):
    for j in range(w):
        copy_maze=copy.deepcopy(maze)
        start=[i+1,j+1]
        que=deque([])
        if maze[start[0]][start[1]]==0:
            copy_maze[start[0]][start[1]]=-1
            for d in direction:
                if copy_maze[start[0]+d[0]][start[1]+d[1]]==0:
                    que.append([start[0]+d[0],start[1]+d[1]])
                    copy_maze[start[0]+d[0]][start[1]+d[1]]=1
                    if max_route<1:
                    	max_route=1
            while len(que)>0:
                tmp=que.popleft()
                for d in direction:
                    if copy_maze[tmp[0]+d[0]][tmp[1]+d[1]]==0:
                        que.append([tmp[0]+d[0],tmp[1]+d[1]])
                        copy_maze[tmp[0]+d[0]][tmp[1]+d[1]]=copy_maze[tmp[0]][tmp[1]]+1
                        if max_route<copy_maze[tmp[0]+d[0]][tmp[1]+d[1]]:
                            max_route=copy_maze[tmp[0]+d[0]][tmp[1]+d[1]]

                
print(max_route)

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


def f(i, j):
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


result = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '
            result = max(result, f(i, j))
print(result)

Solution (Python):
from collections import deque

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


mvs = [(1,0),(-1,0),(0,1),(0,-1)]

ans = 0
for i1 in range(H):
    for j1 in range(W):
        if fields[i1][j1] == "
        s = (i1,j1)
        
        q = deque([])
        q.append(s)
        used = [[-1]*W for i in range(H)]
        used[i1][j1] = 0
        while len(q) > 0:
            h,w = q.popleft()
            for dh,dw in mvs:
                if 0 <= h+dh < H and 0 <= w+dw < W:
                    if used[h+dh][w+dw]==-1 and fields[h+dh][w+dw]==".":
                        q.append((h+dh,w+dw))
                        used[h+dh][w+dw] = used[h][w] + 1
        for i in range(H):
            for j in range(W):
                ans = max(ans, used[i][j])
print(ans)

Solution (Python):
import sys
from collections import deque
import numpy as np
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]
h, w = na()
g = [[1]*(w+2)]
for _ in range(h):
    g += [[1] + [1 if s=="
g += [[1]*(w+2)]
inf = 10**9
def bfs(sx, sy):
    dist = [[inf]*(w+2) for _ in range(h+2)] 
    dist[sx][sy] = 0
    que = deque([[sx, sy]])
    used = set([(sx, sy)])
    while que:
        x, y = que.popleft()
        for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = x+i, y+j
            if (nx, ny) in used:
                continue
            used.add((nx, ny))
            if g[nx][ny]==0:
                dist[nx][ny] = dist[x][y] + 1
                que.append([nx, ny])
    res = 0
    for i in range(h+2):
        for j in range(w+2):
            if g[i][j] == 1:
                dist[i][j] = 0
    return dist


ans = 0
for sx in range(1,h+1):
    for sy in range(1, w+1):
        if g[sx][sy]==0:
            
            res = np.max(np.array(bfs(sx, sy)))
            ans = max(ans, res)
print(ans)

Solution (Python):
import sys
from collections import deque
import copy
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

h, w = na()
g = [[1]*(w+2)]
for _ in range(h):
    g += [[1] + [1 if s=="
g += [[1]*(w+2)]
inf = 10**9
def bfs(sx, sy):
    dist = [[inf]*(w+2) for _ in range(h+2)] 
    dist[sx][sy] = 0
    que = deque([[sx, sy]])
    used = set([(sx, sy)])
    while que:
        x, y = que.popleft()
        for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = x+i, y+j
            if (nx, ny) in used:
                continue
            used.add((nx, ny))
            if g[nx][ny]==0:
                dist[nx][ny] = dist[x][y] + 1
                que.append([nx, ny])
    res = 0
    for i in range(h+2):
        for j in range(w+2):
            if g[i][j] == 0:
                res = max(res, dist[i][j])

    return res


ans = 0
for sx in range(1,h+1):
    for sy in range(1, w+1):
        if g[sx][sy]==0:  
            ans = max(ans, bfs(sx, sy))
print(ans)

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

maze = [["."for i in range(W)] for j in range(H)]

for h in range(H):
    ret = input()
    for i, x in enumerate(ret):
        if x == "
            maze[h][i] = "
        
        



def bfs(maze, y, x):
    q = [[y, x]]
    res = 0
    dist = [[-1] * W for j in range(H)]
    dist[y][x] = 0
    while len(q) > 0:
        yy, xx = q[0]
        res = max(res, dist[yy][xx])
        q.pop(0)
        for dy, dx in [[1,0], [0,1], [-1,0], [0,-1]]:
            ny = yy + dy
            nx = xx + dx
            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue
            if maze[ny][nx] == '
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[yy][xx] + 1
                q.append([ny, nx])
    return res

res_max = 0
for j in range(H):
    for i in range(W):
        if maze[j][i] == '
            continue
        res_max = max(res_max, bfs(maze, j, i))
print(res_max)

Solution (Python):
def bfs():
      global flag
      if len(que)==0:
         flag=False
      else:
         now=que.popleft()
         now_step=steps[now[0]][now[1]]
         for dx,dy in (0,-1),(1,0),(0,1),(-1,0):
            ny=now[0]+dy
            nx=now[1]+dx
            if 0<=ny<=H-1 and 0<=nx<=W-1:
               if maze[ny][nx]==".":
                  if ([ny,nx] in que)==False:
                     maze[ny][nx]="A"
                     que.append([ny,nx])
                     steps[ny][nx]=now_step+1
               else:
                  pass

import copy
from collections import deque

H,W=map(int,input().split())
maze=[]
for i in range(H):
   S=input()
   S=[c for c in S]
   maze.append(S)

maze_copy=copy.deepcopy(maze)
max_step=0

for s_i in range(H):
   for s_j in range(W):
      if maze[s_i][s_j]=="
         continue
            
      maze=copy.deepcopy(maze_copy)
      maze[s_i][s_j]="S"
      que=deque([[s_i,s_j]])
      steps=[[-1]*W for c in range(H)]
      steps[s_i][s_j]=0
      flag=True

      while(flag):
         bfs()

      toriaezu_max=0
      for i in range(H):
         toriaezu_max=max(toriaezu_max,max(steps[i]))
      max_step=max(max_step,toriaezu_max)

print(max_step)

Solution (Python):
from collections import deque

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

def bps(si,sj):
    distance=[[-1]*W for j in range(H)]
    distance[si][sj]=0
    deq=deque([[si,sj]])
    fdis=0
    while deq:
        i,j=deq.popleft()
        for dir_i,dir_j in [(-1,0),(1,0),(0,-1),(0,1)]:
            if 0<=i+dir_i<H and 0<=j+dir_j<W and distance[i+dir_i][j+dir_j]==-1 and Map[i+dir_i][j+dir_j]==".":
                distance[i+dir_i][j+dir_j]=fdis=distance[i][j]+1
                deq.append([i+dir_i,j+dir_j])
    return fdis

bestMapDistance=0
for i in range(H):
    for j in range(W):
        if Map[i][j]==".":
            bestMapDistance=max(bps(i,j),bestMapDistance)

print(bestMapDistance)