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):
h,w = map(int,input().split())
S = [input() for i in range(h)]

ans = -1

for si in range(h):
    for sj in range(w):
        if S[si][sj] == ".":
            V = [[-1] * w for i in range(h)]
            Q = [[si, sj, 0]]
            s = 0
            V[si][sj] = 0
            while s < len(Q):
                i = Q[s][0]
                j = Q[s][1]
                d = Q[s][2]
                for t in [[-1,0], [1,0], [0,-1], [0,1]]:
                    di = t[0]
                    dj = t[1]
                    if 0 <= i+di < h and 0 <= j+dj < w and V[i+di][j+dj] == -1 and S[i+di][j+dj] == ".":
                        V[i+di][j+dj] = d+1
                        Q.append([i+di, j+dj, d+1])
                s += 1

            

            ans = max(ans, max([max(V[i]) for i in range(h)]))
print(ans)

Solution (Python):
from collections import deque
import copy
h,w = map(int,input().split())
maze = [["
for i in range(h):
    lu = list(input())
    l = ["
    maze.append(l)
maze.append(["


def breadth_first_search(start,W,Wn):
    work_q = deque([])
    visited = set()
    work_q.append(start)
    visited.add(start)
    Wn[start[0]][start[1]] = 0
    max_dist = 0
    while work_q:
        here = work_q.popleft()
        move = [(here[0]+1,here[1]), (here[0],here[1]+1),
                (here[0]-1,here[1]),(here[0],here[1]-1)]
        for i in move:
            if W[i[0]][i[1]] == "." and i not in visited:
                work_q.append(i)
                visited.add(i)
                Wn[i[0]][i[1]] = Wn[here[0]][here[1]] + 1
                max_dist = max(max_dist, Wn[i[0]][i[1]])
    return Wn, max_dist


ans = 0
for i in range(h+2):
    for j in range(w+2):
        maze_num = copy.deepcopy(maze)
        if maze[i][j] == ".":
            start = (i,j)
            wn, wn_max = breadth_first_search(start,maze, maze_num)
            ans = max(ans, wn_max)
print(ans)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,input().split())
s=[input() for _ in range(h)]
n=w*h
e=[[0]*n for _ in range(n)]
d=[(1,0),(0,1),(-1,0),(0,-1)]
for i in range(h):
  for j in range(w):
    if s[i][j]==".":
      for x,y in d:
        ni,nj=i+x,j+y
        if 0<=ni<h and 0<=nj<w and s[ni][nj]==".":
          e[w*i+j][w*ni+nj]=1
ans=floyd_warshall(e)
INF=float("inf")
print(int(max(max(a if a != INF else 0 for a in a) for a in ans)))

Solution (Python):
import queue
def search(sy,sx):
    global H,W,Maze
    q = queue.Queue()

    Visit = [[-1]*W for _ in range(H)]
    Dir = [[0,1],[0,-1],[1,0],[-1,0]]

    Visit[sy][sx] = 0 
    q.put([sy,sx])

    while not q.empty():
        ty,tx = q.get()
        path = Visit[ty][tx]

        for dy,dx in Dir:
            ny = ty + dy
            nx = tx + dx
            if 0 <= ny and ny < H and 0 <= nx and nx < W:
                if Maze[ny][nx] == '.':
                    if Visit[ny][nx] == -1:
                        Visit[ny][nx] = path+1
                        q.put([ny,nx])
    max1 = 0
    for h in range(H):
        for w in range(W):
            max1 = max(max1,Visit[h][w])
    return max1

H,W = map(int,input().split())
Maze = []
for h in range(H):
    Maze.append(input())

ans = 0
for sy in range(H):
    for sx in range(W):
        if Maze[sy][sx] == '
            continue
        p = search(sy,sx)          
        if p > 0:
            ans = max(ans,p)
print(ans)

Solution (Python):
def A():
    c = input()
    print(chr(ord(c)+1))

def B():
    temp = [int(k) for k in input().split()]
    N = temp[0]
    K = temp[1]
    M = temp[2]
    A = [int(k) for k in input().split()]
    ans = M*N - sum(A)
    if ans <= K:
        print(max(0, ans))
    else:
        print(-1)

from collections import defaultdict
def C():
    temp = [int(k) for k in input().split()]
    N = temp[0]
    M = temp[1]
    penal = defaultdict(int)
    P = []
    S = []
    for i in range(M):
        temp = input().split()
        P.append(int(temp[0]))
        S.append(temp[1])
    ac_problems = set()

    for i in range(M-1, -1, -1):
        if P[i] not in ac_problems and S[i] == 'AC':
            ac_problems.add(P[i])
        elif P[i] in ac_problems:
            if S[i] == 'WA':
                penal[P[i]] += 1
            elif S[i] == 'AC':
                penal[P[i]] = 0
    
    print(len(ac_problems), sum(penal.values()))

def D():
    temp = [int(k) for k in input().split()]
    H = temp[0]
    W = temp[1]
    S = []
    for i in range(H):
        S.append(input())
    ans = 0
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    def bfs(x, y):
        to_visit = [(x, y, 0)]
        visited = set()
        ret = 0
        while to_visit:
            x, y, distance = to_visit[0]
            del to_visit[0]
            if (x, y) in visited:
                continue
            visited.add((x, y))
            ret = max(distance, ret)
            for d in directions:
                if x+d[0] < H and x+d[0] >= 0:
                    if y+d[1] < W and y+d[1] >= 0:
                        if (x+d[0], y+d[1]) not in visited:
                            if S[x+d[0]][y+d[1]] == '.':
                                to_visit.append((x+d[0], y+d[1], distance+1))
        
        return ret

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

    print(ans)

D()

Solution (Python):
M=410
e=enumerate
_,*s=open(0)
r=s+['
d=eval('[M]*M,'*M)
for i,t in e(s):
  for j,u in e(t):
    k=i*20+j
    if u>'
      d[k][k+1]=1
      d[k+1][k]=1
    if u>'
      d[k][k+20]=1
      d[k+20][k]=1
r=range(M)
for i in r:d[i][i]=0
for k in r:
  for i in r:
    for j in r:d[i][j]=min(d[i][j],d[i][k]+d[k][j])
print(max(u for t in d for u in t if u<M))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
from collections import deque
def resolve():
    h,w=map(int,input().split())
    G=[list(input()) for _ in range(h)]

    D=[(-1,0),(1,0),(0,-1),(0,1)]
    ans=0
    for si,sj in product(range(h),range(w)):
        if(G[si][sj]=='

        
        dist=[[INF]*w for _ in range(h)]
        dist[si][sj]=0
        Q=deque([(si,sj)])
        while(Q):
            i,j=Q.popleft()
            for di,dj in D:
                ni,nj=i+di,j+dj
                if(not (0<=ni<h and 0<=nj<w)): continue
                if(G[ni][nj]=='
                if(dist[ni][nj]>dist[i][j]+1):
                    dist[ni][nj]=dist[i][j]+1
                    Q.append((ni,nj))

        ans=max(ans,max(dist[i][j] for i,j in product(range(h),range(w)) if dist[i][j]!=INF))

    print(ans)
resolve()

Solution (Python):
import sys
from collections import deque

inf = float('inf')

delta = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def bfs(sy, sx):
    dist_max = 0
    visited = set()
    queue = deque([(0, sy, sx)])
    while queue:
        d, y, x = queue.popleft()
        if (y, x) in visited:
            continue
        visited.add((y, x))
        dist_max = max(dist_max, d)
        for dy, dx in delta:
            i = y + dy
            j = x + dx
            if maze[i][j] == '.' and not (i, j) in visited:
                queue.append((d+1, i, j))
    return dist_max
        
h, w = map(int, sys.stdin.readline().split())
maze = ['
maze += ['
maze += ['

def main():
    res = 0
    for sy in range(1, h+1):
        for sx in range(1, w+1):
            if maze[sy][sx] == '
                continue
            res = max(res, bfs(sy, sx))
    
    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
from scipy.sparse import*
e=enumerate
_,*s=open(0)
r=s+['
*g,=eval('[0]*500,'*500)
for i,t in e(s):
 for j,u in e(t):k=i*20+j;g[k][k+1]=u>'
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<999])))

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



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


def bfs(y, x, t):
    steps = [0, 1, 0, -1, 0]
    queue = deque([[y, x]])
    ret = 0
    while len(queue) > 0:
        cur_y, cur_x = queue.popleft()
        for i in range(4):
            next_y, next_x = cur_y + steps[i], cur_x + steps[i + 1]
            if 0 <= next_y < h and 0 <= next_x < w:
                if t[next_y][next_x] == ".":
                    t[next_y][next_x] = t[cur_y][cur_x] + 1
                    ret = max(ret, t[next_y][next_x])
                    queue.append([next_y, next_x])

    return ret


ans = 0
for sy in range(h):
    for sx in range(w):
        
        if table[sy][sx] != ".":
            continue
        mytable = deepcopy(table)
        mytable[sy][sx] = 0
        ret = bfs(sy, sx, mytable)
        ans = max(ans, ret)

print(ans)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
a = [input() for _ in range(h)]
r = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == '.':
      b = list(map(list, a))
      q = deque()
      b[i][j] = 0
      q.append((i, j))
      while(q):
        i, j = q.popleft()
        r = max(r, b[i][j])
        for di in range(-1, 2):
          i1 = i + di
          if 0 <= i1 < h:
            for dj in range(di % 2 - 1, 2, 2):                
              j1 = j + dj
              if 0 <= j1 < w and b[i1][j1] == '.':
                b[i1][j1] = b[i][j] + 1
                q.append((i1, j1))
print(r)

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

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
r = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == '.':
      b = deepcopy(a)
      q = deque()
      b[i][j] = 0
      q.append((i, j))
      while(q):
        i, j = q.popleft()
        r = max(r, b[i][j])
        for di in range(-1, 2):
          i1 = i + di
          if 0 <= i1 < h:
            for dj in range(di % 2 - 1, 2, 2):                
              j1 = j + dj
              if 0 <= j1 < w and b[i1][j1] == '.':
                b[i1][j1] = b[i][j] + 1
                q.append((i1, j1))
print(r)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
a = [input() for _ in range(h)]
r = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == '.':
      b = list(map(list, a))
      q = deque()
      b[i][j] = 0
      q.append((i, j))
      while(q):
        i, j = q.popleft()
        r = max(r, b[i][j])
        for di in range(-1, 2):
          i1 = i + di
          if 0 <= i1 < h:
            for dj in range(di % 2 - 1, 2, 2):                
              j1 = j + dj
              if 0 <= j1 < w and b[i1][j1] == '.':
                b[i1][j1] = b[i][j] + 1
                q.append((i1, j1))
print(r)

Solution (Python):
from scipy.sparse import*
e=enumerate
_,*s=open(0)
r=s+['
*g,=eval('[0]*500,'*500)
for i,t in e(s):
 for j,u in e(t):k=i*20+j;g[k][k+1]=u>'
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<999])))

Solution (Python):
from scipy.sparse import*
e=enumerate
_,*s=open(0)
r=s+['
*g,=eval('[0]*500,'*500)
for i,t in e(s):
 for j,u in e(t):k=i*20+j;g[k][k+1]=u>'
a=csgraph.johnson(csr_matrix(g),0)
print(int(a[a<999].max()))

Solution (Python):
from scipy.sparse import*
e=enumerate
_,*s=open(0)
r=s+['
*g,=eval('[0]*500,'*500)
for i,t in e(s):
  for j,u in e(t):
    k=i*20+j
    g[k][k+1]=u>'
    g[k][k+20]=u>'
a=csgraph.johnson(csr_matrix(g),0)
print(int(a[a<999].max()))

Solution (Python):
from scipy.sparse import*
e=enumerate
h,*s=open(0)
h=int(h[:2])
*g,=eval('[0]*500,'*500)
for i,t in e(s):
  for j,u in e(t):
    k=i*20+j
    g[k][k+1]=u>'
    g[k][k+20]=(i<h-1)*u>'
a=csgraph.johnson(csr_matrix(g),0)
print(int(a[a<999].max()))

Solution (Python):
from scipy.sparse import*
e=enumerate
h,*s=open(0)
h,w=map(int,h.split())
*g,=eval('[0]*500,'*500)
for i,t in e(s):
  for j,u in e(t):
    k=i*w+j
    g[k][k+1]=u>'
    g[k][k+w]=(i<h-1)*u>'
a=csgraph.johnson(csr_matrix(g),0)
print(int(a[a<999].max()))

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

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

N = W * H
E = [[INF] * N  for _ in range(N)]

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

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            for di, dj in dij:
                ni, nj = i + di, j + dj
                if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
                    E[W * i + j][W * ni + nj] = 1

from scipy.sparse.csgraph import floyd_warshall
A = floyd_warshall(E)
INF = float("inf")

print(int(max(max(a if a != INF else 0 for a in a) for a in A)))

Solution (Python):
from collections import deque
import copy

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

road = []
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            road.append((h, w))

ans = 0
for rh, rw in road:
    SC, q = copy.deepcopy(S), deque([(rh, rw, 0)])
    SC[rh][rw] = 0
    while len(q) > 0:
        h, w, i = q.popleft()
        for nh, nw in neig:
            if 0 <= h - nh < H and 0 <= w - nw < W and SC[h - nh][w - nw] == '.':
                SC[h - nh][w - nw] = i + 1
                ans = max(ans, i + 1)
                q.append([h - nh, w - nw, i + 1])

print(ans)

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

N = W * H
E = [[0] * N  for _ in range(N)]

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

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            for di, dj in dij:
                ni, nj = i + di, j + dj
                if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
                    E[W * i + j][W * ni + nj] = 1

from scipy.sparse.csgraph import floyd_warshall
A = floyd_warshall(E)
INF = float("inf")

print(int(max(max(a if a != INF else 0 for a in a) for a in A)))

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

N = W * H
E = [[0] * N  for _ in range(N)]



    



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

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            for di, dj in dij:
                ni, nj = i + di, j + dj
                if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
                    E[W * i + j][W * ni + nj] = 1



from scipy.sparse.csgraph import floyd_warshall
INF = float("inf")

A = floyd_warshall(E)

print(int(max(max(a if a != INF else 0 for a in a) for a in A)))

Solution (Python):
H,W = (int(x) for x in input().split())
a = []
que = []
dis =[]
longDis = 0

for i in range(H):
    a += list(input().split())

h = -1
w = 0

for _ in range(H*W):
    com = [[0 for i in range(W)] for j in range(H)]
    k = 0
    dis = [k]
    l = 0

    if h < H-1:
        h += 1
    else:
        h = 0
        w += 1

    if a[h][w] != '.':
        continue

    que += [[h,w]]
    com[h][w] = 1
    i = h
    j = w
    
    while True:
        k = dis[l] + 1

        
        if i-1 >= 0 and a[i-1][j] == '.':
            if com[i-1][j] == 0:
                que += [[i-1,j]]
                dis += [k]
                com[i-1][j] = 1

        
        if i+1 < H and a[i+1][j] == '.':
            if com[i+1][j] == 0:
                que += [[i+1,j]]
                dis += [k]
                com[i+1][j] = 1

        
        if j-1 >= 0 and a[i][j-1] == '.':
            if com[i][j-1] == 0:
                que += [[i,j-1]]
                dis += [k]
                com[i][j-1] = 1 

        
        if j+1 < W and a[i][j+1] == '.':
            if com[i][j+1] == 0:
                que += [[i,j+1]]
                dis += [k]
                com[i][j+1] = 1

        l += 1

        if l == len(que):
            break
        
        i = que[l][0]
        j = que[l][1]

    for i in range(len(dis)):
        if dis[i] > longDis:
            longDis = dis[i]

    dis.clear()
    que.clear()

print(longDis)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
S=[[False]*(W+2)]
for i in range(H):
    S.append([False]+[c=='.' for c in input()]+[False])
S.append([False]*(W+2))

r=[] 
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j]:
            r.append((i,j))
m=len(r)
d=[[10**3 for j in range(m)] for i in range(m)] 
for u in range(m-1):
    d[u][u]=0
    si,sj=r[u]
    for v in range(u+1,m):
        ti,tj=r[v]
        if (si==ti and abs(sj-tj)==1) or (abs(si-ti)==1 and sj==tj):
            d[u][v]=d[v][u]=1
'''
print(r)
for di in d:
    print(di)
'''
for k in range(m):
    for s in range(m):
        for g in range(m):
            d[s][g]=min(d[s][g], d[s][k]+d[k][g])
    '''
    for di in d:
        print(di)
    print()
    '''
ans=0
for i in range(m-1):
    for j in range(i+1,m):
        ans=max(ans,d[i][j])

print(ans)

Solution (Python):
import numpy as np
n, m = map(int, input().split())
g = [input() for _ in range(n)]
maze = np.array(list(map(list, g)))

from collections import deque


def dfs(s, maze):
    H, W = maze.shape

    visited = np.array([[-1 for _ in range(W)] for _ in range(H)])
    visited[s[0]][s[1]] = 0

    actions = [(-1,0),(1,0),(0,-1),(0,1)]
    queue = deque([s])

    while queue:
        x,y = queue.popleft()
        for action in actions:
            nx = x + action[0]
            ny = y + action[1]
            if nx in range(H) and ny in range(W) and maze[(nx,ny)]=='.' and visited[(nx,ny)]==-1:
                visited[(nx,ny)] = visited[(x,y)] + 1
                queue.append((nx,ny))
    return np.max(visited)
    
ret = -1
H, W = maze.shape

for sx in range(H):
    for sy in range(W):
        if maze[sx][sy] == '.':
            ret = max(dfs((sx,sy), maze), ret)
print(ret)

Solution (Python):
import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
for i in range(len(CORD)):
    st = CORD[i]
    if MP[st[0]][st[1]] == ".":
        QUE=deque()
        visited = [[0]*W for i in range(H)]
        visited[st[0]][st[1]] = 1
        QUE.append((st[0], st[1], 0))
        res = 0
        while QUE:
            ii, jj, dist = QUE.popleft()
            max_dist = max(max_dist, dist)
            for iii, jjj in [(ii-1,jj),(ii+1,jj),(ii,jj-1),(ii,jj+1)]:
                if iii >= 0 and jjj >= 0 and iii < H and jjj < W and MP[iii][jjj] != '
                    QUE.append((iii, jjj, dist+1))
                    visited[iii][jjj] = 1


print(max_dist)

Solution (Python):
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq


def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()


def in_range(t, l, r):
    return l <= t and t < r

def main():
    H, W = rip()
    S = [""] * H
    for i in range(H): S[i] = rs()

    inf = int(1e9)
    ma = 0
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '

            mi = [[inf] * W for i in range(H)]
            mi[i][j] = 0
            q = collections.deque()
            q.append((i,j))
            while len(q) > 0:
                y, x = q.popleft()
                for t in range(4):
                    ny = y + dy[t]
                    nx = x + dx[t]
                    if (not in_range(nx, 0, W)) or (not in_range(ny, 0, H)) : continue
                    if S[ny][nx] == '
                    if mi[ny][nx] == inf:
                        mi[ny][nx] = mi[y][x] + 1
                        q.append((ny, nx))
            for k in range(H):
                for l in range(W):
                    if S[k][l] == '
                    ma = max(ma, mi[k][l])
    
    print(ma)




if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def solve(s, start):
    if s[start[0]][start[1]] == "
        return -1 
    q = deque([start])
    distance = [[-1] * w for _ in range(h)]
    distance[start[0]][start[1]] = 0

    while q:
        y, x = q.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + i, x + j
            if not(0 <= new_y < h and 0 <= new_x < w): continue
            if s[new_y][new_x] == "
            if distance[new_y][new_x] == -1:
                distance[new_y][new_x] = distance[y][x] + 1
                q.append([new_y, new_x])

    return max(map(max, distance))


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

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, solve(s, [i, j]))

print(ans)

Solution (Python):
import numpy as np
h,w=map(int,input().split())
l=set()
for i in range(h):
    t=input()
    for j in range(w):
        if t[j]==".":
            l.add((i,j))

s=set()
from collections import deque
graph=np.zeros((h*w,h*w),dtype=np.int64)
for x,y in l:
        if (x+1,y) in l and (x*w+y,(x+1)*w+y) not in s:
            graph[x*w+y,(x+1)*w+y]=1
            s.add((x*w+y,(x+1)*w+y))
        if (x,y+1) in l and (x*w+y,x*w+y+1) not in s:
            graph[x*w+y,x*w+y+1]=1
            s.add((x*w+y,x*w+y+1))

from scipy.sparse.csgraph import floyd_warshall


ans=floyd_warshall(graph,directed=False)
cond=ans!=float("inf")
print(int(ans[cond].max()))

Solution (Python):
import copy, collections, itertools
H, W = [int(_) for _ in input().split()]
S_ = [['
                          for _ in range(H)] + [['
ans = 0
for i, j in itertools.product(range(1, H + 1), range(1, W + 1)):
    if S_[i][j] == '.':
        S = copy.deepcopy(S_)
        S[i][j] = '
        q = collections.deque([(i, j, 0)])
        while q:
            x, y, d = q.popleft()
            for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                if S[x + dx][y + dy] == '.':
                    X, Y = x + dx, y + dy
                    S[X][Y] = '
                    q += [(X, Y, d + 1)]
        ans = max(d, ans)
print(ans)

Solution (Python):

from collections import deque

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

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

ans = 0
for si in range(H):
    for sj in range(W):
        if graph[si][sj] == "
        que = deque()
        que.append([si, sj])

        dist = [[-1 for _ in range(W)] for _ in range(H)]
        dist[si][sj] = 0
        
        while que:
            y, x = que.popleft()

            for dir in range(4):
                ny = y + dy[dir]
                nx = x + dx[dir]
                if ny < 0 or ny >= H or nx < 0 or nx >= W: continue
                if graph[ny][nx] == "
                if dist[ny][nx] != -1: continue

                if graph[ny][nx] == ".":
                    dist[ny][nx] = dist[y][x] + 1
                    que.append([ny, nx])

        for i in range(H):
            for j in range(W):
                if dist[i][j] == -1: continue
                ans = max(ans, dist[i][j])

print(ans)

Solution (Python):
'''input
3 3
.

.
'''

from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	arr = map(str, arr)
	return ' '.join(arr)


def bfs(source):
	myq = deque()
	myq.append(source)
	visited = dict()
	visited[mp(source)] = True
	dist = -1
	while len(myq) > 0:
		temp = deque()
		dist += 1
		while len(myq) > 0:
			x, y  = myq.popleft()
			if x - 1 >= 0 and maze[x - 1][y] != '
					visited[mp([x -1, y])] = True
					temp.append([x - 1, y])
			if x + 1 < n and maze[x + 1][y] != '
					visited[mp([x + 1, y])] = True
					temp.append([x + 1, y])
			if y - 1 >= 0 and maze[x][y - 1] != '
					visited[mp([x, y - 1])] = True
					temp.append([x, y - 1])
			if y + 1 < m and maze[x][y + 1] != '
					visited[mp([x, y + 1])] = True
					temp.append([x, y + 1])
		myq = temp
	return dist		



n, m = list(map(int, input().split()))
maze = []
for _ in xrange(n):
	state = list(input().strip())
	maze.append(state)
















ans = 0
for i in xrange(n):
	for j in xrange(m):
		if maze[i][j] != '
			first = [i, j]
			ans = max(ans, bfs(first))
print(ans)

Solution (Python):
'''input
3 3
.

.
'''

from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	arr = map(str, arr)
	return ' '.join(arr)


def bfs(source):
	myq = deque()
	myq.append(source)
	visited = dict()
	visited[mp(source)] = True
	dist = -1
	while len(myq) > 0:
		temp = deque()
		dist += 1
		while len(myq) > 0:
			x, y  = myq.popleft()
			if x - 1 >= 0 and maze[x - 1][y] != '
					visited[mp([x -1, y])] = True
					temp.append([x - 1, y])
			if x + 1 < n and maze[x + 1][y] != '
					visited[mp([x + 1, y])] = True
					temp.append([x + 1, y])
			if y - 1 >= 0 and maze[x][y - 1] != '
					visited[mp([x, y - 1])] = True
					temp.append([x, y - 1])
			if y + 1 < m and maze[x][y + 1] != '
					visited[mp([x, y + 1])] = True
					temp.append([x, y + 1])
		myq = temp
	return dist		



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
















ans = 0
for i in range(n):
	for j in range(m):
		if maze[i][j] != '
			first = [i, j]
			ans = max(ans, bfs(first))
print(ans)

Solution (Python):
'''input
3 3
.

.
'''

from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	arr = map(str, arr)
	return ' '.join(arr)


def bfs(source):
	myq = deque()
	myq.append(source)
	visited = dict()
	visited[mp(source)] = True
	dist = -1
	while len(myq) > 0:
		temp = deque()
		dist += 1
		while len(myq) > 0:
			x, y  = myq.popleft()
			if x - 1 >= 0 and maze[x - 1][y] != '
					visited[mp([x -1, y])] = True
					temp.append([x - 1, y])
			if x + 1 < n and maze[x + 1][y] != '
					visited[mp([x + 1, y])] = True
					temp.append([x + 1, y])
			if y - 1 >= 0 and maze[x][y - 1] != '
					visited[mp([x, y - 1])] = True
					temp.append([x, y - 1])
			if y + 1 < m and maze[x][y + 1] != '
					visited[mp([x, y + 1])] = True
					temp.append([x, y + 1])
		myq = temp
	return dist		



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
















ans = 0
for i in range(n):
	for j in range(m):
		if maze[i][j] != '
			first = [i, j]
			ans = max(ans, bfs(first))
print(ans)

Solution (Python):
'''input
3 3
.

.
'''

from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	arr = map(str, arr)
	return ' '.join(arr)


def bfs(source):
	myq = deque()
	myq.append(source)
	visited = dict()
	visited[mp(source)] = True
	dist = -1
	while len(myq) > 0:
		temp = deque()
		dist += 1
		while len(myq) > 0:
			x, y  = myq.popleft()
			if x - 1 >= 0:
				if maze[x - 1][y] != '
					visited[mp([x -1, y])] = True
					temp.append([x - 1, y])
			if x + 1 < n:
				if maze[x + 1][y] != '
					visited[mp([x + 1, y])] = True
					temp.append([x + 1, y])
			if y - 1 >= 0:
				if maze[x][y - 1] != '
					visited[mp([x, y - 1])] = True
					temp.append([x, y - 1])
			if y + 1 < m:
				if maze[x][y + 1] != '
					visited[mp([x, y + 1])] = True
					temp.append([x, y + 1])
		myq = temp
	return dist		



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
















ans = 0
for i in range(n):
	for j in range(m):
		if maze[i][j] != '
			first = [i, j]
			ans = max(ans, bfs(first))
print(ans)

Solution (Python):
'''input
3 3
.

.
'''

from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	arr = map(str, arr)
	return ' '.join(arr)


def bfs(source):
	myq = deque()
	myq.append(source)
	visited = dict()
	visited[mp(source)] = True
	dist = -1
	while len(myq) > 0:
		temp = deque()
		dist += 1
		while len(myq) > 0:
			x, y  = myq.popleft()
			if x - 1 >= 0:
				if maze[x - 1][y] != '
					visited[mp([x -1, y])] = True
					temp.append([x - 1, y])
			if x + 1 < n:
				if maze[x + 1][y] != '
					visited[mp([x + 1, y])] = True
					temp.append([x + 1, y])
			if y - 1 >= 0:
				if maze[x][y - 1] != '
					visited[mp([x, y - 1])] = True
					temp.append([x, y - 1])
			if y + 1 < m:
				if maze[x][y + 1] != '
					visited[mp([x, y + 1])] = True
					temp.append([x, y + 1])
		myq = temp
	return dist		



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
















ans = 0
for i in range(n):
	for j in range(m):
		if maze[i][j] != '
			first = [i, j]
			ans = max(ans, bfs(first))
print(ans)