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


stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) 
rs = lambda: stdin.readline().rstrip()  

H, W = rl()
grid = [list(rs()) for _ in range(H)]
INF = 1000

def bfs(sx, sy):
    d = [[INF] * W for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque()
    que.append((sx, sy))
    d[sy][sx] = 0
    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]                
            if 0 <= ny and ny <= H-1 and 0 <= nx and nx <= W-1 and \
                    grid[ny][nx] != '
                d[ny][nx] = d[p[1]][p[0]] + 1
                que.append((nx, ny))
    dis = [[0 if x == INF else x for x in row] for row in d]
    return max([max(y) for y in dis])

answer = 0

for s in range(H):
    for t in range(W):
        if grid[s][t] == '
            continue
        distance = bfs(t, s)
        if distance > answer:
            answer = distance

print(answer)

Solution (Python):
h,w=map(int,input().split())
s=['
s+=['
s.append('
h+=2
w+=2
p=[[1,0],[0,1],[-1,0],[0,-1]]
st=[]
cnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            st.append((i,j))
            cnt+=1
ans=0
for i in range(cnt):
    n=[st[i]]
    route={n[0]:0}
    c=1
    count=1
    while c<cnt:
        n2=[]
        for i in n:
            for j in p:
                np=(i[0]+j[0],i[1]+j[1])
                if s[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                    n2.append(np)
                    route[np]=count
                    c+=1
        n=n2
        count+=1
    ans=max(ans,count-1)
print(ans)

Solution (Python):
from collections import deque

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

mymap = []
for h in range(H):
    mylist = list(input())
    mymap += [mylist]




d = [ [0 for w in range(W)] for h in range(H) ]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
INF = -999

def bfs(a, b):
    mymax = 0
    
    for h in range(H):
        for w  in range(W):
            d[h][w] = INF
    
    
    que = deque([[a,b]])
    d[a][b] = 0
    
    while que:
        y, x = que.popleft() 
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            
            if 0 <= ny and ny < H and 0 <= nx and nx < W and mymap[ny][nx] != '
                que.append([ny,nx])
                d[ny][nx] = d[y][x] + 1
                if d[ny][nx] > mymax:
                    mymax = d[ny][nx]
    
    return mymax

mymax = 0
for h in range(H):
    for w in range(W):
        if mymap[h][w] != '
            mine = bfs(h, w)
            
            if mymax < mine:
                mymax = mine

print(mymax)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True


def dijkstra(edge,st):
    
    
    n=len(edge)
    d=[(0 if st==i else inf,i) for i in range(n)]
    prev=[0]*n
    q=[i for i in d]
    heapify(q)
    
    
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur][0]+dist
            if alt<d[dst][0]:
                d[dst]=(alt,dst)
                prev[dst]=cur
                heappush(q,(alt,dst))
    return [i for i,j in d],prev

def cv(i,j):
    return i*w+j
def rcv(x):
    return x//w,x%w




ans=0

h,w=LI()

mp=[[1]*(w+2)]
for i in range(h):
    mp.append([1]+[1 if i=='
mp.append([1]*(w+2))
h+=2
w+=2

n=h*w

def bfs(sh,sw):
    g=[[-1]*w for i in range(h)]
    dd=[(0,1),(0,-1),(1,0),(-1,0)]
    
    q=deque()
    q.append((sh,sw))
    g[sh][sw]=0
    while q:
        ch,cw=q.popleft()
        
        for di,dj in dd:
            if mp[ch+di][cw+dj]==0 and g[ch+di][cw+dj]==-1:
                q.append((ch+di,cw+dj))
                g[ch+di][cw+dj]=g[ch][cw]+1
    MG=0
    for i in range(h):
        MG=max(MG,max(g[i]))
        
    
    return MG

ans=0
for i in range(1,h-1):
    for j in range(1,w-1):
        if mp[i][j]==1:continue
        ans=max(bfs(i,j),ans)

print(ans)

Solution (Python):
def Warshall_Floyd(edges,N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
    return edges


def main():
    H,W = map(int,input().split())
    ls = [list(input()) for _ in range(H)]
    for i in range(H):
        ls[i].insert(0,"
        ls[i].append("
    ls.append(["
    ls.insert(0,["
    graph = [[float("inf") for _ in range(H*W)] for _ in range(H*W)]

    for i in range(1,H+1):
        for j in range(1,W+1):
            if ls[i][j]==".":
                
                if ls[i-1][j]==".":
                    graph[(i-1)*W+(j-1)][(i-2)*W+(j-1)] = 1
                    graph[(i-2)*W+(j-1)][(i-1)*W+(j-1)] = 1
                
                if ls[i][j+1]==".":
                    graph[(i-1)*W+(j-1)][(i-1)*W+j] = 1
                    graph[(i-1)*W+j][(i-1)*W+(j-1)] = 1
                
                if ls[i+1][j]==".":
                    graph[(i-1)*W+(j-1)][i*W+(j-1)] = 1
                    graph[i*W+(j-1)][(i-1)*W+(j-1)] = 1
                
                if ls[i][j-1]==".":
                    graph[(i-1)*W+(j-1)][(i-1)*W+(j-2)] = 1
                    graph[(i-1)*W+(j-2)][(i-1)*W+(j-1)] = 1
                else:
                    pass

    a = Warshall_Floyd(graph,H*W)
    for i in range(H*W):
        for j in range(H*W):
            if a[i][j]==float("inf"):
                a[i][j]=0
    for i in range(H*W):
        a[i][i] = 0

    mx = 0
    for i in a:
        mx = max(mx,max(i))
    print(mx)
if __name__ == '__main__':
    main()

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

x=[["a"]*W for i in range(H)]
y=[[set() for i in range(W)] for j in range(H)]

done=set()
for i in range(H):
  x[i]=input()

for i in range(H):
  for j in range(W):
    if x[i][j]==".":
      if i>0:
        if x[i-1][j]==".":
          y[i][j].add(W*(i-1)+j)
      if i<H-1:
        if x[i+1][j]==".":
          y[i][j].add(W*(i+1)+j)
      if j>0:
        if x[i][j-1]==".":
          y[i][j].add(W*(i)+j-1)
      if j<W-1:
        if x[i][j+1]==".":
          y[i][j].add(W*(i)+j+1)
maxleng=0          
for i in range(H):
  for j in range(W):
    done={W*i+j}
    leng=0
    nxt=[set() for k in range(H*W)]
    nxt[0]=set(y[i][j])
    for k in range(H*W):
      done|=nxt[k]
      while len(nxt[k])>0:
        a=nxt[k].pop()
        nxt[k+1]|=y[a//W][a%W]
      nxt[k+1]=set(nxt[k+1]&(nxt[k+1]^done))
      if len(nxt[k+1])==0:
        if maxleng<k:
          maxleng=k
        break
print(maxleng+1)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
ans = 0
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for h in range(H):
    for w in range(W):
        if maze[h][w] == '
            continue
        queue = deque()
        depth = [[-1] * W for i in range(H)]
        depth[h][w] = 0
        queue.append((h, w))
        while queue:
            i, j = queue.popleft()
            for di, dj in move:
                ni, nj = i+di, j+dj
                if 0 <= ni < H and 0 <= nj < W and maze[ni][nj] == '.' and depth[ni][nj] == -1:
                    queue.append((ni, nj))
                    depth[ni][nj] = depth[i][j] + 1
        ans = max(ans, max(max(d) for d in depth))
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque

def main():
    h,w=map(int,input().split())
    MAP=[['
    for _ in range(h):
        S=list(input().strip())
        S=['
        MAP.append(S)
    MAP.append(['
    
    ans=0
    
    def Dist(k,l):
        delta=[[1,0],[0,1],[-1,0],[0,-1]]
        Dist=[[float('inf')]*(w+2) for _ in range(h+2)]
        Dist[k][l]=0
        Visited=[[False]*(w+2) for _ in range(h+2)]
        Visited[k][l]=True
        q=deque()
        q.append((k,l))
        while q:
            y,x=q.popleft()
            for dx,dy in delta:
                
                if Dist[y+dy][x+dx]==float('inf') and MAP[y+dy][x+dx]=='.':
                    q.append((y+dy,x+dx))
                    Dist[y+dy][x+dx]=Dist[y][x]+1
        ret=0
        for i in range(h+2):
            for j in range(w+2):
                if Dist[i][j]==float('inf'):
                    continue
                ret=max(ret,Dist[i][j])
        return ret
        
    for i in range(1,h+1):
        for j in range(1,w+1):
            if MAP[i][j]=='
                continue
            dist=Dist(i,j)
            ans=max(ans,dist)
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):
adjust_list = ((0,1),(0,-1),(1,0),(-1,0))
h, w = [int(v) for v in input().split()]
field = [list(input()) for i in range(h)]

def bfs(s, t):
    si, sj = s
    ti, tj = t
    if field[si][sj] == "." and field[ti][tj] == ".":

        search_field = [ [ -1 for i in range(w) ] for j in range(h) ]
        search_list = [s]
        turn = 0
        search_field[si][sj] = turn
        
        
        while search_list:
            turn += 1
            new_search_list = []
            for p in search_list:
                pi, pj = p
                
                for q in adjust_list:
                    qi, qj = q
                    if 0 <= pi+qi < h and 0 <= pj+qj < w:
                        if search_field[pi+qi][pj+qj] == -1 and field[pi+qi][pj+qj] == ".":
                            new_search_list.append((pi+qi,pj+qj))
                            search_field[pi+qi][pj+qj] = turn
            search_list = new_search_list
            if search_field[ti][tj] != -1:
                break
        return search_field[ti][tj]
    else:
        return -1
    

ans = 0
coodinate = [ (i, j) for i in range(h) for j in range(w) ]
k = h*w

for i in range(k-1):
    for j in range(i+1, k):
        ans = max(ans, bfs(coodinate[i], coodinate[j]))
print(ans)

Solution (Python):
import copy
height, width = map(int, input().split())
field = []
for i in range(height):
    e = list(input())
    field.append(e)

dir = ((0, 1), (1, 0), (-1, 0), (0, -1))

ans = 0

for start_y in range(height):
    for start_x in range(width):
        if field[start_y][start_x] == "
            pass
        else:
            new_field = copy.deepcopy(field)
            que1 = [(start_y, start_x)]
            cnt = 0
            new_field[start_y][start_x] = 0
            while True:
                que2 = []
                cnt += 1
                for y, x in que1:
                    for i, j in dir:
                        if y + i >= 0 and y + i < height and x + j >= 0 and x + j < width:
                            if new_field[y + i][x + j] == ".":
                                que2.append((y + i, x + j))
                                new_field[y + i][x + j] = cnt
                que1 = que2
                if len(que2) == 0:
                    ans = max(ans, cnt - 1)
                    break
print(ans)

Solution (Python):
h,w=map(int,input().split())
a=['*'*(w+2)]+['*'+input()+'*' for _ in range(h)]+['*'*(w+2)]
from collections import deque
ans=0
for p in range(h):
  for q in range(w):
    d=deque()
    m=0
    if a[p+1][q+1]=='.':
      d.append([p+1,q+1])
      c=[[10000]*w for _ in range(h)]
      c[p][q]=1
      di=[[0,1],[1,0],[-1,0],[0,-1]]
      while d:
        g=d.popleft()
        for i in di:
          x=g[0]+i[0]
          y=g[1]+i[1]
          if a[x][y]=='.':
            if c[x-1][y-1]==10000:
              d.append([x,y])
              c[x-1][y-1]=c[g[0]-1][g[1]-1]+1
      for i in range(h):
        for j in range(w):
          if c[i][j]!=10000:
            m=max(m,c[i][j])
    ans=max(ans,m)
print(ans-1)

Solution (Python):
import queue

def bfs(i,j,d):
    already[i][j] = d
    next = []
    for a,b in [[-1,0], [1,0],[0,1],[0,-1]]:
        if 0<=i+a<H and 0<=j+b<W and A[i+a][j+b]=='.' and already[i+a][j+b]==-1:
            if [i+a,j+b] not in next:
                next.append([i+a,j+b])
    for ni, nj in next:
        bfs(ni,nj,d+1)




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


ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j]!='.':
            continue
        q = queue.Queue()
        q.put((i,j))
        already = [[-1]*W for _ in range(H)]
        already[i][j] = 0
        while not q.empty():
            x,y = q.get()
            for a,b in [[-1,0], [1,0],[0,1],[0,-1]]:
                if 0<=x+a<H and 0<=y+b<W and A[x+a][y+b]=='.' and already[x+a][y+b]==-1:
                    q.put((x+a, y+b))
                    already[x+a][y+b] = already[x][y]+1
        t = 0
        for al in already:
            t = max(t, max(al))

        ans = max(ans, t)

print(ans)

Solution (Python):
from fractions import gcd


import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors





def main():
    
    
    

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



    l = []
    for i in range(h):
        for j in range(w):
            l.append((i, j))

    maze = s
    def Dijkstra_search(sx, sy, c):
        H = h
        W = w
        visited = [[False for i in range(W)] for j in range(H)]
        d = [[float("inf") for i in range(W)] for j in range(H)]  
        d[sx][sy] = 0

        queue = []
        heapq.heappush(queue, (0, (sx, sy)))
        while len(queue):
            cost, (x, y) = heapq.heappop(queue)


            if visited[x][y]:
                continue
            visited[x][y] = True

            for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                nx = x + dx
                ny = y + dy
                if nx >= 0 and ny >= 0 and nx < H and ny < W:
                    if visited[nx][ny] or maze[nx][ny] == "
                        continue

                    vd = 1 + cost
                    if d[nx][ny] > vd:
                        d[nx][ny] = vd
                        heapq.heappush(queue, (vd, (nx, ny)))

        ret = 0
        for i in range(h):
            for j in range(w):
                if s[i][j] == "
                    continue
                ret = max(d[i][j],ret)
        return ret
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
        

    
    
    ans = 0
    for v in l:
        if s[v[0]][v[1]] == "
            continue
        
        ans = max(ans , Dijkstra_search(v[0],v[1],1))
    print(ans)
                


                
        




    


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok


def main():
    H,W = mis()
    S = tuple(input() for _ in range(H))
    reached = set()
    q = deque()
    ans = 0
    def check():
        nonlocal ans
        while q:
            x, y, d = q.popleft()
            for nx, ny in ((x-1, y),(x+1, y),(x, y-1),(x, y+1)):
                if 0 <= nx < W and 0 <= ny < H and S[ny][nx]=='.' and (nx, ny) not in reached:
                    q.append((nx, ny, d+1))
                    reached.add((nx, ny))
                    ans = max(ans, d+1)
    for x in range(W):
        for y in range(H):
            if S[y][x] == '
                continue
            q.append((x, y, 0))
            reached.add((x, y))
            check()
            reached.clear()
    print(ans)

main()

Solution (Python):
from collections import deque
H, W = map(int, input().split())
sheet = [[0]*(W+2) for i in range(H+2)]
for i in range(H):
  s = input()
  for j in range(W):
    if s[j]=='.':
      sheet[i+1][j+1] = 1

ans = -1
for i in range(1, H+1):
  for j in range(1, W+1):
    m = -1
    if sheet[i][j]==0:
      continue
    stuck = deque([(j, i, 0)])
    log = [[10**5]*(W+2) for i in range(H+2)]
    log[i][j] = 0
    while stuck:
      x, y, c = stuck.popleft()
      if c>m:
        m = c
      for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
        if sheet[y+dy][x+dx]==1 and log[y+dy][x+dx]>c+1:
          log[y+dy][x+dx] = c+1
          stuck += [(x+dx, y+dy, c+1)]
    if ans<m:
      ans = m
print(ans)

Solution (Python):
import sys
from collections import *
from heapq import *
INF = 500000
mod = 10**9+7

def dijkstra(s):
    dist = defaultdict(lambda : INF)
    dist[s], h = 0, []
    heappush(h, (0, s))
    while (len(h)):
        dv, v = heappop(h)
        if dv > dist[v]:
            continue
        for u in es[v]:
            tmp = dv+1
            if tmp < dist[u]:
                dist[u] = tmp
                heappush(h, (tmp, u))
    return dist

H, W = map(int, input().split())
f = [input() for i in range(H)]
V = []
for i in range(H):
    for j in range(W):
        if f[i][j] == '.':
            V.append((i, j))
es = defaultdict(list)
for i in range(H):
    for j in range(W-1):
        if f[i][j] == '.' and f[i][j+1] == '.':
            es[(i, j)].append((i, j+1))
            es[(i, j+1)].append((i, j))
for i in range(H-1):
    for j in range(W):
        if f[i][j] == '.' and f[i+1][j] == '.':
            es[(i, j)].append((i+1, j))
            es[(i+1, j)].append((i, j))
ans = 0
for v in V:
    ans = max(ans, max(dijkstra(v).values()))
print(ans)

Solution (Python):
def main():
  import sys
  input = sys.stdin.readline
  
  H,W = map(int,input().split())
  S = [list(input()) for _ in range(H)]
  
  idx = 0
  for i in range(H):
    for j in range(W):
      if S[i][j] == '.':
        S[i][j] = idx
        idx += 1
  
  D = [[float('inf') for _ in range(idx)] for _ in range(idx)]
  for i in range(H):
    for j in range(W):
      if S[i][j] == '
        continue
      for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
        if 0 <= i+dy < H and 0 <= j+dx < W and S[i+dy][j+dx] != '
          D[S[i][j]][S[i+dy][j+dx]] = 1
          D[S[i+dy][j+dx]][S[i][j]] = 1
  for i in range(idx):
    D[i][i] = 0
  
  for k in range(idx):
    for i in range(idx):
      for j in range(idx):
        D[i][j] = min(D[i][k]+D[k][j],D[i][j])
  
  ans = 0
  for d in D:
    ans = max(max(d),ans)
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall

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

d = [[10**9] * (w*h) for _ in range(w*h)]

for i in range(h):
    for j in range(w):
        if(s[i][j] == '.'):
            if(i != h-1):
                if(s[i+1][j] == '.'):
                    d[(i*w + j)][((i+1)*w + j)] = 1
                    d[((i+1)*w + j)][(i*w + j)] = 1
            if(j != w-1):
                if(s[i][j+1] == '.'):
                    d[(i*w + j)][(i*w + j + 1)] = 1
                    d[(i*w + j + 1)][(i*w + j)] = 1

G = csgraph_from_dense(d, null_value=10**9)
len = floyd_warshall(G)

ans = 0
for i in range(h*w):
    for j in range(h*w):
        if(len[i][j] < 1000000):
            ans = max(len[i][j], ans)

print(int(ans))

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque


def main():
    H, W = [int(x) for x in input().split()]
    A = [["" for i in range(W)] for j in range(H)]

    for j in range(H):
        S = input().strip()
        for i, s in enumerate(list(S)):
            A[j][i] = s

    ma = 0

    dj = [1, 0, -1, 0]
    di = [0, 1, 0, -1]

    for sj in range(H):
        for si in range(W):
            if A[sj][si] == "
                continue
            d = [[-1 for i in range(W)] for j in range(H)]
            q = deque([])
            q.append((sj, si))
            d[sj][si] = 0

            while q:
                p = q.popleft()
                for i in range(4):
                    nj = p[0] + dj[i]
                    ni = p[1] + di[i]

                    if 0 <= nj < H and 0 <= ni < W and A[nj][ni] != "
                        q.append((nj, ni))
                        d[nj][ni] = d[p[0]][p[1]] + 1

            for gj in range(H):
                for gi in range(W):
                    ma = max(ma, d[gj][gi])

    print(ma)





    


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    H,W = [int(n) for n in input().split()]
    grid = [[0 if n=="." else 1 for n in input()] for _ in range(H)]
    INF = 10**10
    graph = [[INF]*H*W for _ in range(H*W)]
    for i in range(H):
        for j in range(W):
            if grid[i][j] == 0:
                graph[i*W+j][i*W+j]=0
                if i<H-1 and grid[i+1][j]==0:
                    graph[i*W+j][(i+1)*W+(j)] = 1
                    graph[(i+1)*W+(j)][i*W+j] = 1
                if j>0 and grid[i][j-1] == 0:
                    graph[i*W+j][(i)*W+j-1] = 1
                    graph[(i)*W+j-1][i*W+j] = 1
                if j<W-1 and grid[i][j+1] == 0:
                    graph[i*W+j][(i)*W+(j+1)] = 1
                    graph[(i)*W+(j+1)][i*W+j] = 1
                if i>0 and grid[i-1][j] == 0:
                    graph[i*W+j][(i-1)*W+(j)] = 1
                    graph[(i-1)*W+(j)][i*W+j] = 1
    
    
    for k in range(H*W):
        for i in range(H*W):
            for j in range(H*W):
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
    
    
    
    
    m = 0
    for i in range(H*W):
        for j in range(H*W):
            if graph[i][j] == INF:
                continue
            m = max(m,graph[i][j])
    print(m)
main()

Solution (Python):
h, w = map(int, input().split())
ans = 0
s = []
a = []
q = []
for i in range(h):
    s.append(input())


for yy in range(h):
    for xx in range(w):
        a = []
        for i in range(h):
            a.append([0] * w)

        d = 1
        q = [(xx, yy)]
        while True:
            nq = []
            while len(q) > 0:
                p = q.pop()
                x, y = p
                if x < 0 or x >= w or y < 0 or y >= h:
                    continue
                if s[y][x] == '
                    continue
                if a[y][x] > 0:
                    continue
                a[y][x] = d
                nq.append((x - 1, y))
                nq.append((x + 1, y))
                nq.append((x, y - 1))
                nq.append((x, y + 1))
            if len(nq) == 0:
                break
            q = nq
            d += 1

        b = []
        for i in range(h):
            b.extend(a[i])
        b = sorted(b, reverse=True)
        ans = max(ans, b[0])
print(ans - 1)

Solution (Python):
import numpy as np

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

maze = np.ones((h + 2, w + 2), dtype=np.int)

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


def bfs(maze, si, sj):
    assert maze[si, sj] == 0
    infty = -1
    distances = np.full((h + 2, w + 2), infty, dtype=np.int)
    queue = []
    queue.append((si, sj))
    distances[si, sj] = 0
    while len(queue) > 0:
        ci, cj = queue.pop(0)
        d = distances[ci, cj]
        left = (ci, cj - 1)
        right = (ci, cj + 1)
        up = (ci - 1, cj)
        down = (ci + 1, cj)
        nexts = [left, right, up, down]
        for ni, nj in nexts:
            if not (1 <= ni and ni <= h \
               and 1 <= nj and nj <= w):
                continue
            if distances[ni, nj] != infty:
                continue
            if maze[ni, nj] == 1:
                continue
            distances[ni, nj] = d + 1
            queue.append((ni, nj))

    return distances


max_dist = 0
for si in range(1, h + 1):
    for sj in range(1, w + 1):
        if maze[si, sj] == 0:
            distances = bfs(maze, si, sj)
            mx = np.max(distances)
            max_dist = max(max_dist, mx)

print(max_dist)

Solution (Python):
from queue import Queue
INF = float("inf")
R, C = map(int,input().split())
M = [input() for k in range(R)]
ans = 0
for k in range(C):
    for l in range(R):
        if M[l][k] == ".":
            D = [[INF for k in range(C)] for l in range(R)]
            sx, sy = l, k
            Q = Queue()
            Q.put([sx,sy])
            D[sx][sy] = 0
            dx = [1,0,-1,0]
            dy = [0,1,0,-1]
            while not Q.empty():
                t = Q.get()
                x = t[0]
                y = t[1]
                for d in range(4):
                    if 0 <= x + dx[d] < R and 0 <= y + dy[d] < C:
                        if M[x+dx[d]][y+dy[d]] == "." and D[x+dx[d]][y+dy[d]] > D[x][y]+1:
                            D[x+dx[d]][y+dy[d]] = D[x][y]+1
                            Q.put([x+dx[d],y+dy[d]])
            for p in range(C):
                for q in range(R):
                    if D[q][p] != float("inf"):
                        ans = max(ans,D[q][p])
print(ans)

Solution (Python):



from collections import Counter,deque


from sys import stdin,setrecursionlimit










setrecursionlimit(10**6)
input=stdin.readline
def m(t):
    r=0
    for i in t:
        r=max(r,max(i))
    return r

h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
dx=[0,0,1,-1]
dy=[1,-1,0,0]
ans=0
rf=range(4)
rh=range(h)
rw=range(w)
for sy in rh:
    for sx in rw:
        if s[sy][sx]=="
            continue
        dis=[[-1]*w for _ in rh]
        dis[sy][sx]=0
        q=deque([(sy,sx)])
        while len(q)>0:
            y,x=q.popleft()
            for i in rf:
                ny=y+dy[i]
                nx=x+dx[i]
                if ny<0 or nx<0 or ny==h or nx==w:
                    continue
                if s[ny][nx]=="
                    continue
                if dis[ny][nx]==-1:
                    dis[ny][nx]=dis[y][x]+1
                    q.append((ny,nx))
        ans=max(ans,m(dis))
print(ans)