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

h, w = [int(_) for _ in input().split()]
s = []
M = -1
for i in range(h):
    s.append(input())
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            continue
        dp = [[-1 for _ in range(w)] for i in range(h)]
        dp[i][j] = 0
        que = deque([(i, j)])
        
        while len(que) != 0:
            i_f, j_f = que.popleft()
            
            d_f = dp[i_f][j_f]
            l = [(i_f, j_f + 1),(i_f, j_f - 1), (i_f - 1, j_f), (i_f + 1, j_f)]
            for p in range(len(l)):
                i_t, j_t = l[p]
                if 0 <= i_t <= h - 1 and 0 <= j_t <= w - 1:
                    
                    
                    
                    
                    
                    if dp[i_t][j_t] == -1 and s[i_t][j_t] == '.':
                        que.append((i_t, j_t))
                        dp[i_t][j_t] = d_f + 1
            
            
            
            
            
            
        
        
        
        
        
        for i_q in range(h):
            for j_q in range(w):
                M = max(dp[i_q][j_q], M)
print(M)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
h,w=map(int,input().split())
s=[input() for i in range(h)]


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


n=h*w
d = [[float("inf") for i in range(h*w)] for i in range(h*w)]


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




for i in range(h*w):
    d[i][i] = 0 

li=warshall_floyd(d)
ans=0
for i in range(len(li)):
    for j in range(len(li[i])):
        if li[i][j]!=float("inf"):
            ans=max(ans,li[i][j])

print(ans)

Solution (Python):
from queue import Queue
from copy import deepcopy

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

WHITE = 0
GRAY = 1
BLACK = 2

dhw = [[-1, 0], [1, 0], [0, -1], [0, 1]]

color_orginal = [[WHITE] * w for _ in range(h)]
for hi in range(h):
    for wi in range(w):
        if s[hi][wi] == "
            color_orginal[hi][wi] = BLACK


def dfs(sh, sw):
    q = Queue()
    q.put([sh, sw])

    color = deepcopy(color_orginal)
    d = [[-1] * w for _ in range(h)]

    d[sh][sw] = 0
    dd = 0

    while not q.empty():
        uh, uw = q.get()
        color[uh][uw] = BLACK
        for dh, dw in dhw:
            nxth = uh + dh
            nxtw = uw + dw
            if 0 <= nxth <= h - 1 and 0 <= nxtw <= w - 1:
                if color[nxth][nxtw] == WHITE:
                    q.put([nxth, nxtw])
                    color[nxth][nxtw] = GRAY
                    d[nxth][nxtw] = d[uh][uw] + 1
                    dd = max(d[nxth][nxtw], dd)

    return dd


ans = 0
for hi in range(h):
    for wi in range(w):
        if s[hi][wi] == ".":
            ans = max(ans, dfs(hi, wi))

print(ans)

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

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

def nexts(h, w):
    pq = []
    if h != 0: pq.append((h-1, w))
    if w != 0: pq.append((h, w-1))
    if h != H-1: pq.append((h+1, w))
    if w != W-1: pq.append((h, w+1))
    return pq


def bfs(sh, sw):
    Ds = [[-1]*W for _ in range(H)]
    q = [(sh, sw)]
    d = 0
    Ds[sh][sw] = 0
    while q:
        qq = []
        d += 1
        for h, w in q:
            for nh, nw in nexts(h, w):
                if state[nh][nw] == "
                    Ds[nh][nw] = -2
                elif Ds[nh][nw] == -1:
                    Ds[nh][nw] = d
                    qq.append((nh, nw))
        q = qq
    
    maxd = 0
    for h in range(H):
        for w in range(W):
            if maxd < Ds[h][w]:
                maxd = Ds[h][w]
                lh, lw = h, w
    return maxd

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

print(ans)

Solution (Python):

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

myinf = 10 ** 9 + 7
tab_graph = [[myinf] * (H * W) for _ in range(H * W)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if i + di < 0: continue
            if i + di >= H: continue
            if j + dj < 0: continue
            if j + dj >= W: continue
            
            if S[i + di][j + dj] == '
            
            src = i * W + j
            dst = (i + di) * W + (j + dj)
            tab_graph[src][dst] = 1

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

G = csgraph_from_dense(tab_graph, null_value=myinf)
d = floyd_warshall(G)


ans = 0
for i in range(H * W):
    for j in range(H * W):
        if i == j: continue
        
        if d[i][j] < myinf: ans = max(ans, int(d[i][j]))

print(ans)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

import heapq

def dijkstra():
    
    n,w = map(int,input().split())

    edge = [[] for i in range(n)]
    dg = 10**7
    
    for i in range(n-1):
        x,y = map(int,input().split())
        z = 1
        x -= 1
        y -= 1
        edge[x].append(dg + y)
        edge[y].append(dg + x)
    
    s = w-1
    d = [-1]*n
    d[s] = 0

    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)

        

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        v,c = minedge%dg,minedge//dg
        if d[v] >= 0:
            continue
        d[v] = c
        for e in edge[v]:
            vNext = e%dg
            if d[vNext]:
                heapq.heappush(edgelist, (e//dg+d[v])*dg + vNext)

    return d


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




N,M = m()


d = [[mod for i in range(N*M)] for j in range(N*M)]
for i in range(N*M):
    d[i][i] = 0
a = []
for i in range(N):
    a.append(list(input()))
    for j in range(M):
        if i != 0:
            if a[-1][j] == "." and a[-2][j] == ".":
                d[i*M+j-M][i*M+j] = 1
                d[i*M+j][i*M+j-M] = 1
        if j != 0:
            if a[-1][j] == "." and a[-1][j-1] == ".":
                d[i*M+j][i*M+j-1] = 1
                d[i*M+j-1][i*M+j] = 1

for k in range(N*M):
    for i in range(N*M):
        for j in range(N*M):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])

ma = 0
for i in range(N*M):
    for j in range(N*M):
        if d[i][j] != mod:
            ma = max(ma,d[i][j])

print(ma)

Solution (Python):
h,w = map(int,input().split())

a= []

for i in range(h):
    arrc = input()
    a.append(arrc)
ans = 0
for gg in range(1,h+1):
    for bb in range(1,w+1):
        if a[gg-1][bb-1] == ".":
            ys=gg
            xs=bb
            n=[(ys-1,xs-1)]
            route={n[0]:0}
            p=[[1,0],[0,1],[-1,0],[0,-1]]
            count=1
            while count != 401:
                n2=[]
                for i in n:
                    for j in p:
                       
                        np=(i[0]+j[0],i[1]+j[1])
                        if 0<=np[0]<=h-1 and 0<=np[1]<=w-1:
                            if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                                n2.append(np)
                                route[np]=count
                n=n2
                count+=1
            
            ll= max(list(route.values()))
            if ll > ans:
                ans = ll

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
S = [input() for _ in range(H)]

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
search = [[0]*W for _ in range(H)]
max_num = 0
q = deque()

def BFS(point):  
	global max_num
	while q:
		point = q.popleft()
		for i in range(4):
			x = point[1] + dx[i]
			y = point[0] + dy[i]
			if 0 <= x <= W-1 and 0 <= y <= H-1 and S[y][x] != "
				search[y][x] = search[point[0]][point[1]] + 1
				max_num = max(search[y][x], max_num)
				q.append((y, x))

ans = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == "
			continue
		q = deque()
		search = [[-1]*W for _ in range(H)]
		search[i][j] = 0
		start = (i, j)
		q.append(start)
		max_num = 0
		BFS(start)
		
		ans = max(ans, max_num)
print(ans)

Solution (Python):

get = lambda: int(raw_input().strip())
gets = lambda: map(int, raw_input().strip().split())
getss = lambda x: [gets() for _ in xrange(x)]
getl = lambda x: [gets() for _ in xrange(x)]


m, n = gets()
A0 = [list(raw_input().strip()) for _ in xrange(m)]

for i in xrange(m):
    for j in xrange(n):
        if A0[i][j] == '.':
            A0[i][j] = 0
        else:
            A0[i][j] = -1


def test(i, j):
    
    A = [row[:] for row in A0]
    bfs = [[i, j]]
    A[i][j] = 1
    dep = 0
    while bfs:
        dep += 1
        bfs2 = []
        for i, j in bfs:
            for di, dj in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
                i2, j2 = i + di, j + dj
                if 0 <= i2 < m and 0 <= j2 < n and A[i2][j2] == 0:
                    A[i2][j2] = dep + 1
                    bfs2.append([i2, j2])
        bfs = bfs2
    
    
    
    return dep


res = 0
for i in xrange(m):
    for j in xrange(n):
        if A0[i][j] < 0: continue
        res = max(res, test(i, j) - 1)
print res

Solution (Python):
from heapq import heappush, heappop
from collections import deque
import re
import math
import functools
import itertools
import fractions

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29


def mk1d(n, val=INF):
    return [val for i in range(n)]

def mk2d(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]

DIV = 998244353

def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)


def floyd_warshall(costs):
    N = len(costs)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                costs[i][j] = min(costs[i][j], costs[i][k]+costs[k][j])
    return costs

def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)

def main():
    H,W = isRaw()
    SS = [sRaw() for _ in range(H)]
    costs = mk2d(H*W, H*W, INF)
    for h in range(H):
        for w in range(W):
            cur = h*W+w
            costs[cur][cur] = 0
            if h<H-1 and SS[h][w]=="." and SS[h+1][w]==".":
                costs[cur][cur+W] = 1
                costs[cur+W][cur] = 1
            if w < W-1 and SS[h][w] == "." and SS[h][w+1] == ".":
                costs[cur][cur+1] = 1
                costs[cur+1][cur] = 1                
    costs = floyd_warshall(costs)
    maxCost = 0
    for cur in range(H*W):
        for nxt in range(H*W):
            if(costs[cur][nxt]!=INF) and cur!=nxt:
                maxCost = max(maxCost,costs[cur][nxt])
    return maxCost

if __name__ == "__main__":
    print(main())

Solution (Python):

import sys
from collections import defaultdict, deque
from operator import itemgetter
from heapq import heappop, heappush

def inpl(): return list(map(int, input().split()))
H, W = inpl()
G = [[1]*(W+2)]
for _ in range(H):
    G.append([1] + [int(s=="
G.append([1]*(W+2))

ans = 0
for h in range(1, H+1):
    for w in range(1, W+1):
        if G[h][w] == 1:
            continue
        dist = [[-1]*(W+2) for _ in range(H+2)]
        dist[h][w] = 0
        Q = deque()
        Q.append([h, w])
        while Q:
            ph, pw = Q.popleft()
            for dh, dw in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                qh, qw = ph+dh, pw + dw
                if G[qh][qw]:
                    continue
                if dist[qh][qw] == -1:
                    dist[qh][qw] = dist[ph][pw] + 1
                    Q.append([qh, qw])
                
        for y in range(1, H+1):
            for x in range(1, W+1):
                ans = max(ans, dist[y][x])
print(ans)

Solution (Python):
import copy
import queue
q=queue.Queue()
dx=[-1,0,1,0]
dy=[0,1,0,-1]
n,m=map(int,input().split())
b=[list(input()) for i in range(n)]
def abc(s,sy,sx):
    q=queue.Queue()
    for i in range(n):
        if 'S' in s[i]:
            sy=s[i].index('S')
            sx=i
            break
    
    
    
    
    
    d=[[-1 for i in range(m)] for j in range(n)]
    q.put([sx,sy])
    d[sx][sy]=0
    while not q.empty():
        p=q.get()
        
        
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]
            if 0<=nx<n and 0<=ny<m and s[nx][ny]!='
                q.put([nx,ny])
                d[nx][ny]=d[p[0]][p[1]]+1
    return d

s=copy.deepcopy(b)
res=0
for i in range(n):
    for j in range(m):
        if s[i][j]==".":
            a=abc(s,j,i)
            for k in range(n):
                a_max=max(a[k])
                if res<a_max:
                    res=a_max
print(res)

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

ans = 0
inf = 10**12
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            continue
        q = deque()
        q.append((i, j, 0))
        used = [[inf]*W for _ in range(H)]
        used[i][j] = 0
        while q:
            temp = q.popleft()
            k = temp[0]
            l = temp[1]
            d = temp[2]
            if k > 0 and S[k-1][l] == "." and used[k-1][l] > d+1:
                used[k-1][l] = d+1
                q.append((k-1, l, d+1))
            if k < H-1 and S[k+1][l] == "." and used[k+1][l] > d+1:
                used[k+1][l] = d+1
                q.append((k+1, l, d+1))
            if l > 0 and S[k][l-1] == "." and used[k][l-1] > d+1:
                used[k][l-1] = d+1
                q.append((k, l-1, d+1))
            if l < W-1 and S[k][l+1] == "." and used[k][l+1] > d+1:
                used[k][l+1] = d+1
                q.append((k, l+1, d+1))

        for s in range(H):
            for t in range(W):
                if used[s][t] < inf:
                    ans = max(ans, used[s][t])

print(ans)

Solution (Python):
from collections import deque
 
INF = float('inf')
MOD = 10 ** 9 + 7
dy = (0, -1, 0, 1)
dx = (1, 0, -1, 0)


H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dx = [0,0,-1,1]
dy = [1,-1,0,0]
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for _ in range(H)]
        if M[i][j] == '.':
            Ma = 0
            q.append((i, j))
            dist[i][j] = 0
            while q:
                cx,cy = q.popleft()
                for nx,ny in zip(dx,dy):
                    x ,y= cx+nx,cy+ny
                    if x<0 or y<0 or x>=H or y>=W or dist[x][y]>0:
                        continue
                    if M[x][y] == "." and dist[x][y] == -1:
                        dist[x][y]=dist[cx][cy]+1
                        Ma = max(Ma,dist[x][y])
                        q.append((x,y))
            
            Max_list.append(Ma)


print(max(Max_list))

Solution (Python):
import sys
input = sys.stdin.readline
 
def warshal_floyd(d, n):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
        
  return d

h, w = map(int, input().split())
m = [str(input()) for _ in range(h)]
d = [[float('inf') for i in range(h*w)] for j in range(h*w)]
for i in range(h*w):
  d[i][i] = 0
  
for i in range(h*w):
  for j in range(h*w):
    py, px = i//w, i%w
    qy, qx = j//w, j%w
    if (px == qx and abs(py-qy) == 1) or (py == qy and abs(px-qx) == 1):
      pm = m[py][px]
      qm = m[qy][qx]
      if qm in ['.'] and pm in ['.']:
        d[i][j] = 1
        

d = warshal_floyd(d, h*w)


ans = 0
for i in range(h*w):
  for j in range(h*w):
    if d[i][j] != float('inf'):
      ans = max(ans, d[i][j])
print(ans)

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

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            dis = [[-1] * w for _ in range(h)]
            dis[i][j] = 0
            q = [(i,j)]
            while q:
                l0,l1 = q.pop(0)
                if l0 > 0:
                    if s[l0-1][l1] == '.':
                        if dis[l0-1][l1] > dis[l0][l1] + 1 or dis[l0-1][l1] == -1:
                            dis[l0-1][l1] = dis[l0][l1] + 1
                            q.append((l0-1,l1))
                if l0 < h - 1:
                    if s[l0+1][l1] == '.':
                        if dis[l0+1][l1] > dis[l0][l1] + 1 or dis[l0+1][l1] == -1:
                            dis[l0+1][l1] = dis[l0][l1] + 1
                            q.append((l0+1,l1))
                if l1 > 0:
                    if s[l0][l1-1] == '.':
                        if dis[l0][l1-1] > dis[l0][l1] + 1 or dis[l0][l1-1] == -1:
                            dis[l0][l1-1] = dis[l0][l1] + 1
                            q.append((l0,l1-1))
                if l1 < w - 1:
                    if s[l0][l1+1] == '.':
                        if dis[l0][l1+1] > dis[l0][l1] + 1 or dis[l0][l1+1] == -1:
                            dis[l0][l1+1] = dis[l0][l1] + 1
                            q.append((l0,l1+1))
            dis_max = 0
            for k in dis:
                dis_max = max(max(k), dis_max)
            ans = max(dis_max,ans)

print(ans)

Solution (Python):
import sys
from collections import deque
input=sys.stdin.readline
h,w=map(int,input().split())
s=[]
for i in range(h):
    sub=input().rstrip()
    s.append(sub)
dire=[(1,0),(-1,0),(0,1),(0,-1)]
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            l=[[-1]*w for _ in range(h)]
            q=[(i,j)]
            q=deque(q)
            l[i][j]=0
            while len(q)!=0:
                now=q.popleft()
                for d in dire:
                    x=now[0]+d[0]
                    y=now[1]+d[1]
                    if 0<=x<h and 0<=y<w:
                        if s[x][y]=='.':
                            if l[x][y]==-1:
                                l[x][y]=l[now[0]][now[1]]+1
                                ans=max(ans,l[x][y])
                                q.append((x,y))
print(ans)

Solution (Python):
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(input()))
c = 0
inds = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            inds[i][j] = c
            c += 1
inf = 10**10
graph = [[inf] * c for _ in range(c)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            d = inds[i][j]
            graph[d][d] = 0
            if j > 0 and s[i][j-1] == '.':
                graph[d][inds[i][j-1]] = 1
            if j < w-1 and s[i][j+1] == '.':
                graph[d][inds[i][j+1]] = 1
            if i >0 and s[i-1][j] == '.':
                graph[d][inds[i-1][j]] = 1
            if i < h-1 and s[i+1][j] == '.':
                graph[d][inds[i+1][j]] = 1
for k in range(c):
    for i in range(c):
        for j in range(c):
            graph[i][j] = min(graph[i][j],graph[i][k] + graph[k][j])
mins = 0
for i in range(c):
    for j in range(c):
        if graph[i][j] > mins:
            mins = graph[i][j]
print(mins)

Solution (Python):
from collections import deque

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

s = [['
for _ in [0]*h:
    s.append(['
s.append(['

res = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] == '
            continue
        d = [[0]*(w+2) for _ in [0]*(h+2)]
        
        start = i*dg+j
        tank = deque([start])
        while tank:
            x = tank.popleft()
            
            go = x-dg
            if go != start and s[go//dg][go%dg] == '.' and d[go//dg][go%dg] == 0:
                d[go//dg][go%dg] = d[x//dg][x%dg] + 1
                res = max(res,d[go//dg][go%dg])
                tank.append(go)
            go = x+dg
            if go != start and s[go//dg][go%dg] == '.' and d[go//dg][go%dg] == 0:
                d[go//dg][go%dg] = d[x//dg][x%dg] + 1
                res = max(res,d[go//dg][go%dg])
                tank.append(go)
            go = x+1
            if go != start and s[go//dg][go%dg] == '.' and d[go//dg][go%dg] == 0:
                d[go//dg][go%dg] = d[x//dg][x%dg] + 1
                res = max(res,d[go//dg][go%dg])
                tank.append(go)
            go = x-1
            if go != start and s[go//dg][go%dg] == '.' and d[go//dg][go%dg] == 0:
                d[go//dg][go%dg] = d[x//dg][x%dg] + 1
                res = max(res,d[go//dg][go%dg])
                tank.append(go)

print(res)

Solution (Python):
INFTY = 10**13
def floyd():
    for k in range(n):
        for i in range(n):
            if d[i][k] == INFTY:
                continue
            for j in range(n):
                if d[k][j] == INFTY:
                    continue
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

H, W = map(int, input().split())
S = [list(input()) for h in range(H)]
n = H*W
d = [[0 if i == j else INFTY for j in range(n)]for i in range(n)]

for h in range(H):
    for w in range(W):
        if S[h][w] == '
            continue
        for dh, dw in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            if 0 <= h + dh < H and 0 <= w + dw < W and S[h+dh][w+dw] == '.':
                d[h*W+w][(h+dh)*W+(w+dw)] = 1

floyd()

ans = max([x for row in d for x in row if x != INFTY])
print(ans)

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

    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        line = input().rstrip('\n')
        grid.append(line)

    d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '
                continue
            ans_new = 0
            seen = [[-100] * W for _ in range(H)]
            seen[i][j] = 0
            que = deque()
            que.append(i*W+j)
            while que:
                v = que.popleft()
                y, x = divmod(v, W)
                for dx, dy in d:
                    x_new = x+dx
                    y_new = y+dy
                    if 0 <= y_new < H and 0 <= x_new < W:
                        if seen[y_new][x_new] == -100:
                            if grid[y_new][x_new] == '.':
                                que.append(y_new * W + x_new)
                                seen[y_new][x_new] = seen[y][x] + 1
                                if ans_new < seen[y_new][x_new]:
                                    ans_new = seen[y_new][x_new]
            ans = max(ans, ans_new)

    print(ans)


if __name__ == '__main__':
    main()

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):
import sys
input = sys.stdin.readline

H,W=map(int,input().split())
S=[input().strip() for i in range(H)]
from collections import deque

def bfs(x,y):
    if S[x][y]=="
        return 0
    
    Q=deque()
    Q.append((x,y))
    count=[[-1]*W for i in range(H)]
    count[x][y]=0

    while Q:
        x,y=Q.pop()
        for z,w in [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]:
            if 0<=z<H and 0<=w<W and count[z][w]==-1 and S[z][w]==".":
                count[z][w]=count[x][y]+1
                Q.appendleft((z,w))

    
    
    

    return max([max(c) for c in count])

ANS=0

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

print(ANS)

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

field = [[] for _ in range(H)]
for i in range(H):
    for s in input():
        field[i].append(s)




def bfs(sy, sx, field, H, W):
    field[sy][sx] = 0
    pre_list = [(sy,sx)]
    count = 0
    while len(pre_list) > 0:
        count += 1
        next_list = []
        for y,x in pre_list:
            for i,j in ((1,0),(0,-1),(0,1),(-1,0)):
                if y+i < 0 or x+j < 0 or y+i >= H or x+j >= W:
                    continue
                if field[y+i][x+j] == '.':
                    field[y+i][x+j] = count
                    next_list.append((y+i,x+j))
        pre_list = next_list
    return count

ret = 0
for h in range(H):
    for w in range(W):
        if field[h][w] == '
            continue
        ret = max(ret, bfs(h, w, copy.deepcopy(field), H, W))

print(ret-1)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

H,W = map(int,readline().split())
H += 2; W += 2
grid = '
for _ in range(H-2):
    grid += '
grid += '

def bfs(start):
    INF = 10 ** 9
    dist = [INF] * (H*W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1,1,W,-W):
            w = v + move
            if grid[w] == '
                continue
            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)
    return max(x for x in dist if x < INF)

answer = max(bfs(v) for v in range(H*W) if grid[v] != '
print(answer)

Solution (Python):
def main():

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

    ans = 0
    mv = [[1,0], [-1,0], [0, 1], [0,-1]]
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                cnt = 0
                cur = [[i, j]]
                visited = set([(i, j)])
                while cur:
                    temp = []
                    for k, l in cur:
                        for dk, dl in mv:
                            k1, l1 = k+dk, l+dl
                            if 0<=k1<H and 0<=l1<W and S[k1][l1] == "." and (k1,l1) not in visited:
                                visited.add((k1,l1))
                                temp.append([k1, l1])
                    cur = temp
                    if len(cur) > 0: cnt += 1
                ans = max(ans, cnt)
    return ans

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

Solution (Python):
from collections import deque

h, w = map(int, input().split())
s = ['


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


def bfs(si, sj):
    queue = deque([(si, sj, 0)])
    cost = [[-1] * (w + 2) for _ in range(h + 2)]
    cost[si][sj] = 0
    while queue:
        ci, cj, cc = queue.popleft()
        for k in range(4):
            ni = ci + di[k]
            nj = cj + dj[k]
            if s[ni][nj] == '
                continue
            if cost[ni][nj] != -1:
                continue
            queue.append((ni, nj, cc + 1))
            cost[ni][nj] = cc + 1

    return max(map(lambda x: max(x), cost))


ans = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i][j] == '.':
            ans = max(ans, bfs(i, j))
print(ans)

Solution (Python):
H,W=map(int,input().split())
L=[]
Z=["
L.append(Z)
for i in range(H):
    S=["
    L.append(S)
L.append(Z)


X=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if L[i][j]==".":
            X.append([i,j])

x=[1,-1,0,0]
y=[0,0,1,-1]
import copy
ans=0
for i in range(len(X)):
    l=copy.deepcopy(L)
    l[X[i][0]][X[i][1]]=0
    Q=[[X[i][0],X[i][1]]]
    for j in range(10**9):
        if j==len(Q):
            break
        for k in range(4):
            if l[Q[j][0]+x[k]][Q[j][1]+y[k]]==".":
                l[Q[j][0]+x[k]][Q[j][1]+y[k]]=l[Q[j][0]][Q[j][1]]+1
                Q.append([Q[j][0]+x[k],Q[j][1]+y[k]])
    for a in range(1,H+1):
        for b in range(1,W+1):
            if l[a][b]!="
                if l[a][b]>ans:
                    ans=l[a][b]
print(ans)