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):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    

    
    H,W = map(int, input().split())
    
    S = tuple(input() for i in range(H)) 
    
    
    n=H*W
    inf=10000000

    def warshall_floyd():
        
        
        d = [[inf]*n for i in range(n)] 
        for i in range(H):
            for j in range(W):
                if S[i][j]!=".":
                    continue
                for ni,nj in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
                    if 0<=ni<H and 0<=nj<W and S[ni][nj]==".":
                        d[i*W+j][ni*W+nj]=1
                        
        for i in range(n):
            d[i][i] = 0 
        for k in range(n):
            for i in range(n):
                for j in range(i+1,n):
                    x = min(d[i][j],d[i][k] + d[k][j])
                    d[i][j]=x
                    d[j][i]=x
                
                
        return d

    d=warshall_floyd()
    ans=0
    for i in range(H):
        for j in range(W):
            if S[i][j]!=".":
                continue
            for ni in range(H):
                for nj in range(W):
                    if d[i*W+j][ni*W+nj]<inf:
                        ans=max(ans,d[i*W+j][ni*W+nj])
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
import sys
import copy

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7




nextH = [0, 1, 0, -1]
nextW = [1, 0, -1, 0]


def bfs(u, S):

    S[u[0]][u[1]] = 0  

    q = deque()
    q.append(u)
    m = 0
    while q:
        u = q.popleft()
        for h, w in zip(nextH, nextW):
            h += u[0]
            w += u[1]
            if not (0 <= h < len(S) and 0 <= w < len(S[0])):
                continue

            if S[h][w] == '.':  
                S[h][w] = S[u[0]][u[1]] + 1  
                m = max(m, S[h][w])
                q.append((h, w))
    
    return m


def main():

    H, W = map(int, sys.stdin.readline().rstrip().split())
    S = []
    for _ in range(H):
        S.append([x for x in sys.stdin.readline().rstrip()])

    

    m = 0
    for h in range(H):
        for w in range(W):
            D = copy.deepcopy(S)
            if S[h][w] == '.':
                m = max(m, bfs((h, w), D))

    print(m)


main()

Solution (Python):
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = ''.join(['
S[-1] = ''.join(['
for i in range(1,H+1):
  S[i] = '

maxd = 0
import queue
dy = [1,0,-1,0]
dx = [0,1,0,-1]
for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]=='.':
      visited = [[False]*(W+2) for _ in range(H+2)]
      q = queue.Queue()
      visited[h][w] = True
      q.put([h,w,0])
      while not q.empty():
        a,b,c = q.get()
        
        for i in range(4):
          y,x = a+dy[i], b+dx[i]
          if S[y][x]=='.' and visited[y][x]==False:
            q.put([y,x,c+1])
            visited[y][x]=True
      maxd = max(maxd,c)
print(maxd)

Solution (Python):
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = ''.join(['
S[-1] = ''.join(['
for i in range(1,H+1):
  S[i] = '

maxd = 0
import queue
dy = [1,0,-1,0]
dx = [0,1,0,-1]
for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]=='.':
      visited = [[False]*(W+2) for _ in range(H+2)]
      q = queue.Queue()
      visited[h][w] = True
      q.put([h,w,0])
      while not q.empty():
        a,b,c = q.get()
        
        for i in range(4):
          y,x = a+dy[i], b+dx[i]
          if S[y][x]=='.' and visited[y][x]==False:
            q.put([y,x,c+1])
            visited[y][x]=True
      maxd = max(maxd,c)
print(maxd)

Solution (Python):
inf=float("inf")  


h,w=map(int,input().split())
s=[["
for i in range(h):
    s[i+1]=["




nv=h*w
dp=[[inf]*nv for i in range(nv)] 

def nhw(hi,wi):
    return (hi-1)*w+wi-1

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="
            continue
        vij=nhw(i,j)
        if s[i-1][j]==".":
            vij2=nhw(i-1,j)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i+1][j]==".":
            vij2=nhw(i+1,j)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i][j-1]==".":
            vij2=nhw(i,j-1)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i][j+1]==".":
            vij2=nhw(i,j+1)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
for i in range(nv):
    dp[i][i]=0
           

for k in range(nv):
    for i in range(nv):
        for j in range(nv):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])


dpmax=0
for i in range(nv):
    for j in range(nv):
        if dp[i][j]!=inf:
            if dpmax<dp[i][j]:
                dpmax=dp[i][j]
print(dpmax)

Solution (Python):
"""
解法１：
startとgoalの組み合わせの全探索で調べる。
マス目の数は最大で400なので、組み合わせの数は最大で約160000.
各組み合わせごとにBFSで最短経路を調べるので、400回ループが必要。
なので計算時間としてはO(H^3W^3)

解法２：
ワーシャルフロイドで各ノードから各ノードへの最短経路を求める。
計算量としては、O(H^3W^3となる)。

解法１だとなんかTLEするので、解法２で行く。
"""

H,W = map(int,input().split())
MAP = [list(input()) for _ in range(H)]
dp = [[float("INF")]*(H*W) for _ in range(H*W)]
adjecents = [(1,0),(-1,0),(0,1),(0,-1)]

for i in range(H):
    for j in range(W):
        if MAP[i][j] == ".":
            pointer = i*W + j
            dp[pointer][pointer] = 0
            for a,b in adjecents:
                x = i + a
                y = j + b
                if 0<=x<H and 0<=y<W and MAP[x][y] == ".":
                    pointer2 = x*W + y
                    dp[pointer][pointer2] = 1

for i in range(H*W):
    for j in range(H*W):
        for k in range(H*W):
            dp[j][k] = min(dp[j][k],dp[j][i]+dp[i][k])

ans = 0
for i in range(H*W):
    for j in range(H*W):
        if dp[i][j] != float("INF"):
            ans = max(ans,dp[i][j])
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]









def maze_solve(S_1,S_2,maze_list):
    d = deque()
    d.append([S_1,S_2])
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    while d:
        v = d.popleft()
        x = v[0]
        y = v[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
    return max(list(map(lambda x: max(x), dist)))
h,w = MI()
if h==1 and w == 2:
  print(1)
elif h == 2 and w == 1:
  print(1)
else:
  ans = 0
  maze = [list(input()) for _ in range(h)]
  dist = [[-1]*w for _ in range(h)]
  start_list = []
  for i in range(h):
      for j in range(w):
          if maze[i][j] == "
              dist[i][j] = 0
          else:
              start_list.append([i,j])
  dist_copy = deepcopy(dist)
  for k in start_list:
      dist = deepcopy(dist_copy)
      ans = max(ans,maze_solve(k[0],k[1],maze))
  print(ans+1)

Solution (Python):

from collections import deque

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


def bfs(sx, sy):
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    d = [[-1] * w for _ in range(h)]
    q = deque([])

    q.append((sx, sy))
    d[sx][sy] = 0
    ans = 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 maze[nx][ny] != "
                    ny] == -1:
                q.append((nx, ny))
                d[nx][ny] = d[x][y] + 1
                ans = max(ans, d[nx][ny])
    return ans


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

Solution (Python):
from collections import deque
H, W = map(int, input().split())
maze = [list(input()) for _ 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 maze[sh][sw] == "
            continue
        dist = [[-1] * W for _ in range(H)]
        dist[sh][sw] = 0
        que = deque([[sh, sw]])

        while que:
            nh, nw = que.pop()
            for dh, dw in directions:
                tmp_h, tmp_w = nh + dh, nw + dw
                if not ((0 <= tmp_h < H) and (0 <= tmp_w < W)):
                    continue
                if maze[tmp_h][tmp_w] == "
                    continue
                if dist[tmp_h][tmp_w] != -1:
                    continue

                dist[tmp_h][tmp_w] = dist[nh][nw] + 1
                que.appendleft([tmp_h, tmp_w])

        ans = max(ans, max([max(d) for d in dist]))

print(ans)

Solution (Python):
import sys
from collections import deque

H,W=map(int,input().split())
S=list(sys.stdin)

ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]=='
            continue
        dist=[[-1]*W for _ in range(H)]
        dist[i][j]=0
        que=deque()
        que.append((i,j))
        while que:
            i,j=que.popleft()
            ans=max(ans,dist[i][j])
            for ni,nj in (i-1,j),(i,j+1),(i+1,j),(i,j-1):
                if not (0<=ni<H and 0<=nj<W):
                    continue
                if S[ni][nj]=='
                    continue
                dist[ni][nj]=dist[i][j]+1
                que.append((ni,nj))

print(ans)

Solution (Python):
import sys
from collections import deque

H,W=map(int,input().split())
S=list(sys.stdin)

ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]=='
            continue
        dist=[[-1]*W for _ in range(H)]
        dist[i][j]=0
        que=deque()
        que.append((i,j))
        while que:
            i,j=que.popleft()
            ans=max(ans,dist[i][j])
            for ni,nj in (i-1,j),(i,j+1),(i+1,j),(i,j-1):
                if 0<=ni<H and 0<=nj<W and S[ni][nj]=='.' and dist[ni][nj]==-1:
                    dist[ni][nj]=dist[i][j]+1
                    que.append((ni,nj))

print(ans)

Solution (Python):
from collections import deque

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

mp = [input() for _ in range(H)]

rlt = 0
dxy = [[-1,0],[1,0],[0,-1],[0,1]]

for i in range(H):
  for j in range(W):
    if mp[i][j] == '
      continue
    memo = [[405]*W for _ in range(H)]
    memo[i][j] = 0
    q = deque([[i, j, 0]])
    tmp = 0
    while q:
      t = q.popleft()
      for d in dxy:
        if t[0]+d[0] >= 0 and t[0]+d[0] < H and t[1]+d[1] >= 0 and t[1]+d[1] < W:
          if mp[t[0]+d[0]][t[1]+d[1]] == '.' and memo[t[0]+d[0]][t[1]+d[1]] == 405:
            memo[t[0]+d[0]][t[1]+d[1]] = t[2] + 1
            q.append([t[0]+d[0], t[1]+d[1], t[2] + 1])
            tmp = max(tmp, t[2]+1)
    rlt = max(rlt, tmp)
    
print(rlt)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
S=[[c=='

def bfs(i,j):
    if S[i][j]:
        return 0
    que=deque()
    que.append((i,j))
    vis=[row[:] for row in S]
    vis[i][j]=1
    ans=-1
    while que:
        ans+=1
        for _ in range(len(que)):
            i,j=que.popleft()
            for ni,nj in nbs(i,j):
                if not vis[ni][nj]:
                    que.append((ni,nj))
                    vis[ni][nj]=1
    return ans

def nbs(i,j):
    for ni,nj in (i-1,j),(i,j+1),(i+1,j),(i,j-1):
        if 0<=ni<H and 0<=nj<W:
            yield ni,nj

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

print(ans)

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

ans = 0
for sh in range(H):
    for sw in range(W):
        if maze[sh][sw] == "
            continue

        dist = [[-1] * W for _ in range(H)]
        dist[sh][sw] = 0
        que = deque([[sh, sw]])

        while que:
            nh, nw = que.pop()
            for dh, dw in direction:
                if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
                    continue
                if maze[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):
import sys
from collections import deque

input = sys.stdin.readline


def bfs(S, sh, sw, dist):
    dist[sh][sw] = 0
    queue = deque([(sh, sw)])
    while queue:
        h, w = queue.popleft()
        for i, j in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            y, x = h + i, w + j
            if S[y][x] == "
                continue
            if dist[y][x] == -1:
                dist[y][x] = dist[h][w] + 1
                queue.append((y, x))


def main():
    H, W = map(int, input().split())
    S = [None] * (H + 2)
    S[0] = S[-1] = "
    for i in range(1, H + 1):
        S[i] = "".join(["

    ans = 0
    for sh in range(1, H + 1):
        for sw in range(1, W + 1):
            if S[sh][sw] == "
                continue
            dist = [[-1] * (W + 2) for _ in range(H + 2)]
            bfs(S, sh, sw, dist)
            max_dist = max(map(max, dist))
            ans = max(ans, max_dist)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import os
import sys
import numpy as np

def solve(H, W, S):
    N = H*W
    G = np.empty((N, N), dtype=np.int64)
    G[:] = 9999999
    for h in range(H):
        for w in range(W):
            i = h*W + w
            G[i, i] = 0
            if w < W-1 and S[h][w] == S[h][w+1] == 46:
                G[i, i+1] = G[i+1, i] = 1
            if h < H-1 and S[h][w] == S[h+1][w] == 46:
                G[i, i+W] = G[i+W, i] = 1
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i, j] > G[i, k] + G[k, j]:
                    G[i, j] = G[i, k] + G[k, j]
    
    G = np.where(G>=9999999, 0, G)

    ans = G.max()
    return ans



numba_config = [
    [solve, "i8(i8,i8,u1[:,:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)



import sys
def main():
    input= sys.stdin.buffer.readline
    H, W = map(int, input().split())
    S = np.array([np.frombuffer(input(), dtype=np.uint8) for _ in range(H)])
    print(solve(H, W, S))

main()

Solution (Python):
class Graph:
    
    def __init__(self,vertex=[]):
        self.vertex=list(vertex)
        self.edge_number=0
        self.adjacent={v:set() for v in vertex}

    
    def add_vertex(self,*adder):
        k=len(self.vertex)
        m=0

        for u in adder:
            if u not in self.adjacent:
                self.adjacent[u]=set()
                self.vertex.append(u)

    
    def add_edge(self,From,To):
        for w in [From,To]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if To not in self.adjacent[From]:
            self.adjacent[From].add(To)
            self.adjacent[To].add(From)
            self.edge_number+=1

    
    def remove_edge(self,u,v):
        for w in [u,v]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if u in self.adjacent[v]:
            self.adjacent[u].remove(v)
            self.adjacent[v].remove(u)
            self.edge_number-=1

    
    def remove_vertex(self,*v):
        for w in v:
            if w in self.adjacent:
                self.edge_number-=len(self.adjacent[w])
                for u in self.adjacent[w]:
                    self.adjacent[u].remove(w)
                del self.adjacent[w]


    
    def add_walk(self,*walk):
        n=len(walk)
        for i in range(n-1):
            self.add_edge(walk[i],walk[i+1])

    
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])

    
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    
    def vertex_exist(self,v):
        return v in self.adjacent

    
    def edge_exist(self,u,v):
        if not(self.vertex_exist(u) and self.vertex_exist(v)):
            return False
        return u in self.adjacent[v]

    
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent[v])

    
    def vertex_count(self):
        return len(self.vertex)

    
    def edge_count(self):
        return self.edge_number

    
    def connected_component(self,v):
        if v not in self.adjacent:
            return []

        from collections import deque
        T={u:False for u in self.adjacent}
        T[v]=True
        S=deque([v])

        while S:
            u=S.popleft()
            for w in self.adjacent[u]:
                if not T[w]:
                    T[w]=True
                    S.append(w)

        return [x for x in self.adjacent if T[x]]

    
    def distance(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in self.adjacent}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
                    if x==v:
                        return T[x]
        return inf

    
    def distance_all(self,u):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in self.adjacent}

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
        return T

    
    def shortest_path(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:[] for v in self.vertex}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=[u]
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if not T[x]:
                    T[x]=T[w]+[x]
                    Q.append(x)
                    if x==v:
                        return T[x]
        return None

    
    def diameter(self):
        from collections import deque
        inf=float("inf")

        u=self.vertex[0]
        T={u:inf  for u in self.vertex}

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)

        w=max(T,key=lambda x:T[x])
        T={u:inf  for u in self.vertex}

        Q=deque([w])
        T[w]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
        w=max(T,key=lambda x:T[x])
        return T[w]

def Grid_Graph(m,n):
    E=[]
    for x in range(1,m+1):
        E+=[(x,y) for y in range(1,n+1)]

    G=Graph(E)
    H=[(1,0),(0,1)]

    for y in range(1,n+1):
        for x in range(1,m+1):
            for a,b in H:
                p=x+a
                q=y+b
                if 1<=p<=m and 1<=q<=n:
                    G.add_edge((x,y),(p,q))
    return G

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

G=Grid_Graph(W,H)
for y in range(H):
    S=input()
    for x in range(W):
        if S[x]=="
            G.remove_vertex((x+1,y+1))

M=-1
for a in G.adjacent:
    U=G.distance_all(a)
    M=max(M,max(U.values()))
print(M)

Solution (Python):
import queue
h,w = map(int,input().split())
v = [(1, 0), (0, 1), (-1, 0), (0, -1)]
s = [input() for i in range(h)]

ans = 0
que = queue.Queue()
for i in range(h * w):
    c = 0
    d = [[h*w] * w for i in range(h)]
    p = (i//w, i%w)
    if s[p[0]][p[1]] == '
        continue
    d[p[0]][p[1]] = 0
    que.put(p)
    while not que.empty():
        y,x = que.get()
        c = d[y][x]
        for dy, dx in v:
            yy = y + dy
            xx = x + dx
            if yy < 0 or xx < 0 or h <= yy or w <= xx:
                continue
            if s[yy][xx] == '
                continue
            if d[yy][xx] < h*w:
                continue
            que.put((yy, xx))
            d[yy][xx] = c + 1
    ans = max(ans, c)
print(ans)

Solution (Python):
from collections import deque
import sys


H, W = map(int, input().split())
field = ["o" for _ in range(H+2)] 
for i in range(1, H+1):
    field[i] = "
field[0] = "
field[H+1] = "

idxs = []
dxdy = [(1,0), (-1,0), (0,1), (0,-1)]
for row in range(1, H+1):
    for col in range(1, W+1):
        if field[row][col] == ".":
            idxs.append((row, col))









def bfs(u,v):
    dist = [[-1] * (W+1) for _ in range(H+1)] 
    seen = [[0] * (W+1) for _ in range(H+1)] 
    queue = deque()
    seen[u][v] = 1
    dist[u][v] = 0
    queue.append((u,v))
    graph = {idx: deque() for idx in idxs}
    for idx in idxs:
        x = idx[0]
        y = idx[1]
        for dx, dy in dxdy:
            if field[x+dx][y+dy] == ".":
                graph[idx].append((x+dx, y+dy))
    while queue:
        p, q = queue[0]
        if not graph[(p,q)]:
            queue.popleft()
            continue
        g,h = graph[(p,q)].popleft()
        if seen[g][h]:
            continue
        seen[g][h] = 1
        dist[g][h] = dist[p][q] + 1
        queue.append((g,h))
    ans = -1
    for i in range(1, H+1):
        for j in range(1, W+1):
            ans = max(ans, dist[i][j])
    return ans


res = -1
for sx, sy in idxs:
    res = max(res, bfs(sx, sy))
print(res)

Solution (Python):
from collections import deque
import copy

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

def bfs(x,y):
    check = copy.deepcopy(S)
    que = deque()
    que.append((x,y))
    check[y][x] = 0
    while que.__len__() != 0:
        x,y = que.popleft()
        tmp = check[y][x]
        for dx,dy in (1,0),(-1,0),(0,1),(0,-1):
            sx = x + dx
            sy = y + dy
            if -1 < sx < W and -1 < sy < H:
                if check[sy][sx] == '.':
                    check[sy][sx] = tmp + 1
                    que.append((sx,sy))
    return tmp

ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == '.':
            ans = max(bfs(x,y),ans)

print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
S = [input() + "
S.append("

todo = deque()
done = set()
ans = 0
for sh in range(H):
    for sw in range(W):
        if S[sh][sw] == "
            continue
        s = (sh, sw)
        done.clear()
        done.add(s)
        todo.append((s, 0))
        while todo:
            p, count = todo.popleft()
            ncount = count + 1
            for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nh, nw = p[0] + dh, p[1] + dw
                if S[nh][nw] == "
                    continue
                np = (nh, nw)
                if np in done:
                    continue
                done.add(np)
                ans = max(ans, ncount)
                todo.append((np, ncount))
print(ans)

Solution (Python):
from collections import deque



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

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


def solve():
    ans = 0
    for i in range(H):
        for j in range(W):
            
            if maze[i][j] == "
                continue
        
            
            dist = [[-1] * W for _ in range(H)]
            dist[i][j] = 0
            que = deque()
            que.append([i, j])

            
            while que:
                y, x = que.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]

                    
                    if nx >= W or nx < 0 or ny >= H or ny < 0:
                        continue
                    
                    if dist[ny][nx] != -1:
                        continue
                    
                    if maze[ny][nx] == "
                        continue
                    dist[ny][nx] = dist[y][x] + 1
                    que.append([ny, nx])

            ans = max(ans, max(max(steps) for steps in dist))
    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque


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

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


def solve():
    ans = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == ".":
                dist = [[-1] * W for _ in range(H)]
                dist[i][j] = 0
                que = deque()
                que.append([i, j])

                while que:
                    y, x = que.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if nx >= W or nx < 0 or ny >= H or ny < 0:
                            continue
                        if dist[ny][nx] != -1:
                            continue
                        if maze[ny][nx] == "
                            continue
                        dist[ny][nx] = dist[y][x] + 1
                        que.append([ny, nx])
            else:
                continue
            ans = max(ans, max(max(steps) for steps in dist))
    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque
import copy
H,W = map(int,input().split())
grid = [[0]*W for _ in range(H)]
for i in range(H):
    grid[i] = list(input())
ans = 0
for sy in range(H):
    for sx in range(W):
        if grid[sy][sx] == '
            continue
        now_grid = copy.deepcopy(grid)
        time_grid = [[-1]*W for _ in range(H)]
        queue = deque()
        queue.append([sy,sx,0])
        now_grid[sy][sx] = '
        while queue:
            y,x,t = queue.popleft()
            for next_y, next_x in [[y+1, x],[y,x+1],[y-1,x],[y,x-1]]:
                if 0<= next_y < H and 0 <= next_x < W and now_grid[next_y][next_x] != '
                    queue.append([next_y,next_x,t+1])
                    time_grid[next_y][next_x] = t+1
                    now_grid[next_y][next_x] = '
        Max= 0
        for i in range(H):
            for j in range(W):
                Max = max(Max,time_grid[i][j])
        ans = max(ans, Max)
print(ans)