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
h, w = map(int, input().split())

maze = [list(input()) for _ in range(h)]

ans = 0
def solve(sx, sy):
    INF = 1000000
    reached = [[INF for _ in range(w)] for _ in range(h)]
    reached[sx][sy] = 0
    d = deque()
    d.append([sx, sy])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]    
    while d:
        x, y = d.popleft()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if next_x < 0 or next_x > h - 1 or next_y < 0 or next_y > w - 1:
                continue
            if maze[next_x][next_y] == "
                continue
            if reached[next_x][next_y] != INF:
                continue
            d.append([next_x, next_y])
            reached[next_x][next_y] = reached[x][y] + 1
    gl = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == ".":
                gl = max(gl, reached[i][j])
    return gl

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

Solution (Python):
def warshall_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())
N = H * W

d = [[float("inf") for i in range(N)] for i in range(N)] 

M = [[1 for i in range(W+1)] for i in range(H+1)]
for i in range(H):
    m = input().strip()
    for j in range(W):
        if m[j] == '.':
            M[i][j] = 0

for i in range(H):
    for j in range(W):
        if M[i][j] == 0:
            d[W*i+j][W*i+j] = 0
            if M[i][j+1] == 0:
                d[W*i+j][W*i+j+1] = 1
                d[W*i+j+1][W*i+j] = 1
            if M[i+1][j] == 0:
                d[W*i+j][W*(i+1)+j] = 1
                d[W*(i+1)+j][W*i+j] = 1

o = warshall_floyd(d, N)
ans = 0
for i in range(N):
    for j in range(N):
        if o[i][j] != float('inf'):
            ans = max(ans, o[i][j])
print(ans)

Solution (Python):
import sys
import numpy as np
from heapq import heappop, heappush
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 

 
H,W = map(int,readline().split())
grid = np.full((H+2,W+2),b'
grid[1:-1,1:-1] = np.frombuffer(read(),'S1').reshape(H,-1)[:,:W]
INF = 400
def shortest(grid, start, cost=0):
    dist = np.array([[INF for _ in range(W+2)] for _ in range(H+2)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    st = [(cost, start)]
    dist[start[0]][start[1]]=0
    while(st):
        c, [sx, sy] = heappop(st)
        for a, b in zip(dx, dy):
            x = sx + a
            y = sy + b
            if grid[x][y]==b'
              continue
            dxy = dist[sx][sy] + 1
            if dist[x][y] <= dxy:
                continue
            dist[x][y] = dxy
            heappush(st, (dist[x][y], [x, y]))
    return np.max(dist[dist<INF])

m=0
for i in range(1,H+1):
  for j in range(1,W+1):
    if grid[i,j]==b'
      continue
    tm = shortest(grid, [i, j])
    if m < tm:
      m=tm
print(m)

Solution (Python):
h,w=map(int,input().split())
field=[]
field.append([True for i in range(w+2)])
start=[]
for i  in range(h):
    s=input()
    sub=[True]
    for j in range(w):
        if s[j]=="
            sub.append(True)
        else:
            sub.append(False)
            start.append((i+1,j+1))
    
    sub.append(True)
    field.append(sub)

            
        
    
field.append([True for i in range(w+2)])

from collections import deque
import copy
dis=[]
for i in range(len(start)):

        fields=copy.deepcopy(field)
        d=deque()
        e=deque()
        distance=0
        fields[start[i][0]][start[i][1]]=True

        d.append((start[i][0],start[i][1]))
        while d:
            for some in d:
                index1,index2=some[0],some[1]
                if fields[index1-1][index2]==False:
                    fields[index1-1][index2]=True
                    e.append((index1-1,index2))
                if fields[index1+1][index2]==False:
                    fields[index1+1][index2]=True
                    e.append((index1+1,index2))
                if fields[index1][index2+1]==False:
                    fields[index1][index2+1]=True
                    e.append((index1,index2+1))
                if  fields[index1][index2-1]==False:
                    fields[index1][index2-1]=True
                    e.append((index1,index2-1))
            distance+=1
            d=e
            e=deque()

        dis.append(distance)
    


print(max(dis)  -1)

Solution (Python):
H, W = map(int, input().split())
S = []
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]
for _ in range(H):
  S.append(input())

ans = 0
for si in range(H):
  for sj in range(W):
    if S[si][sj] == "
      continue
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    dist[si][sj] = 0
    queue = [[si, sj]]
    while len(queue) > 0:
      q = queue.pop(0)
      i = q[0]
      j = q[1]
      for dir in range(4):
        ni = i + di[dir]
        nj = j + dj[dir]
        if ni < 0 or ni >= H or nj < 0 or nj >= W:
          continue
        if S[ni][nj] == "
          continue
        if dist[ni][nj] == -1:
          dist[ni][nj] = dist[i][j] + 1
          queue.append([ni, nj])
    for i in range(H):
      for j in range(W):
        ans = max(ans, dist[i][j])

print(ans)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = list(map(int, input().split()))
S = ["
                     "
 
ans = 0
 
for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]
 
        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0
 
        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)

Solution (Python):
H,W=map(int,input().split())
s="
f=-~W*-~H
d=[[0]*f for _ in range(f)]
for i in range(W,f-1):
 d[i][i-1]=s[i]==s[i-1]=="."
 d[i][i-W-1]=s[i]==s[i-W-1]=="."
from scipy.sparse.csgraph import csgraph_from_dense as C,floyd_warshall as F
import numpy as p
Q=F(C(d),directed=False)
print(int(max(Q[Q!=p.inf])))

Solution (Python):

import sys
from collections import deque
from collections import defaultdict

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

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

def bfs(start):
    Visit={}
    q=deque()
    q.append(start)
    Visit[start]=1
    L=defaultdict(lambda: 0)    

    while q:
        fro_x,fro_y=q.popleft()
        for dx,dy in D:
            to_x=fro_x+dx
            to_y=fro_y+dy
            if 0<=to_x<H and 0<=to_y<W:
                if S[to_x][to_y]=="." and (to_x,to_y) not in Visit:
                    Visit[to_x,to_y]=1
                    L[(to_x,to_y)]=L[(fro_x,fro_y)]+1
                    q.append((to_x,to_y))

    return max(L.values())

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

print ans

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

H, W = list(map(int, input().split()))
S = ["
                     "

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0

        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)

Solution (Python):

import sys
from collections import deque
from collections import defaultdict
 
H,W=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]
 
D=[(1,0),(-1,0),(0,1),(0,-1)]
 
def bfs(start):
    Visit={}
    q=deque()
    q.append(start)
    Visit[start]=1
    L=defaultdict(lambda: float("inf"))    
    L[start]=0
 
    while q:
        fro_x,fro_y=q.popleft()
        for dx,dy in D:
            to_x=fro_x+dx
            to_y=fro_y+dy
            if 0<=to_x<H and 0<=to_y<W:
                if S[to_x][to_y]=="." and (to_x,to_y) not in Visit:
                    Visit[to_x,to_y]=1
                    L[(to_x,to_y)]=min(L[(to_x,to_y)],L[(fro_x,fro_y)]+1)
                    q.append((to_x,to_y))
    if len(L.values())==0:
        return 0
    else:
        return max(L.values())
 
ans=0
for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            ans=max(ans,bfs((h,w)))
 
print ans

Solution (Python):
h,w=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(input()))
s=[]
for i in range(h):
    for j in range(w):
        if l[i][j]=='.':
            s.append([i,j])
def solve(s):
    v=[[0 for i in range(w)] for j in range(h)]       
    v[s[0]][s[1]]=1
    mc=0
    q=[[s,0]]
    while len(q):
        p=q.pop(0)
        x=p[0][0]
        y=p[0][1]
        c=p[1]
        k=[[0,1],[0,-1],[1,0],[-1,0]]
        for j in k:
            nx=x+j[0]
            ny=y+j[1]
            if 0<=nx<h and 0<=ny<w and l[nx][ny]=='.' and v[nx][ny]==0:
                v[nx][ny]=1
                q.append([[nx,ny],c+1])
                if mc<=c+1:
                    mc=c+1
                    
    return mc 
ans=0
for i in s:
    ans=max(ans,solve(i))
print(ans)
exit()

v=[[0 for i in range(w)] for j in range(h)]       
v[ms[0]][ms[1]]=1
ans=0
q=[[ms,0]]
while len(q):
    p=q.pop(0)
    x=p[0][0]
    y=p[0][1]
    c=p[1]
    k=[[0,1],[0,-1],[1,0],[-1,0]]
    for j in k:
        nx=x+j[0]
        ny=y+j[1]
        if 0<=nx<h and 0<=ny<w and l[nx][ny]=='.' and v[nx][ny]==0:
            v[nx][ny]=1
            q.append([[nx,ny],c+1])
            ans=max(ans,c+1)
                
print(ans)

Solution (Python):
h, w = map(int, input().split())
grid = []
inf = 400
for i in range(h):
    grid.append(list(input()))
graph = [[0 for i in range(h*w)] for j in range(h*w)]
for i in range(h):
    for j in range(1,w):
        u = i * w + j - 1
        v = i * w + j
        if grid[i][j-1] != '
            graph[u][v] = graph[v][u] = 1
for i in range(w):
    for j in range(1,h):
        u = (j - 1) * w + i
        v = j * w + i
        if grid[j-1][i] != '
            graph[u][v] = graph[v][u] = 1
distance = [[inf for i in range(h*w)] for j in range(h*w)]
for i in range(h*w):
    for j in range(w*h):
        if graph[i][j] == 1:
            distance[i][j] = 1
    distance[i][i] = 0
for k in range(h*w):
    for j in range(w*h):
        for i in range(w*h):
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
ans = 0
for i in range(h*w):
    for j in range(h*w):
        if distance[i][j] != inf:
            ans = max(ans, distance[i][j])
print(ans)

Solution (Python):

import sys
from collections import deque
from collections import defaultdict
 
H,W=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]
 
D=[(1,0),(-1,0),(0,1),(0,-1)]
 
def bfs(start):
    Visit={}
    q=deque()
    q.append(start)
    L=defaultdict(lambda: float("inf")) 
    L[start]=0
 
    while q:
        fro_x,fro_y=q.popleft()
        for dx,dy in D:
            to_x=fro_x+dx
            to_y=fro_y+dy
            alt=L[(fro_x,fro_y)]+1
            if 0<=to_x<H and 0<=to_y<W:
                if S[to_x][to_y]=="." and alt<L[(to_x,to_y)]:
                    L[(to_x,to_y)]=alt
                    q.append((to_x,to_y))
    return max(L.values())
 
ans=0
for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            ans=max(ans,bfs((h,w)))
print ans

Solution (Python):
h,w = map(int,input().split())
field = [list(input())for i in range(h)]
a= [[0]*w for i in range(h)]

vec = [(-1,0),(1,0),(0,1),(0,-1)]
ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == "
        stack = [(i,j)]
        visited = [[0]*w for i in range(h)]
        a[i][j] = 0
        
        while stack:
            next = []
            for x,y in stack:
                
                if visited[x][y]:continue

                visited[x][y] = 1
                

                for tx,ty in vec:
                    nx = x+tx
                    ny = y+ty
                    if nx < 0 or ny <0 or nx >=h or ny >=w:continue
                    if field[nx][ny] == "
                    if visited[nx][ny]:continue
                    next.append((nx,ny))
                    a[nx][ny] = a[x][y] + 1
                    
                    
            stack = next
   
        for k in range(h):
            ans = max(ans,max(a[k]))
            a[k] = [0]*w
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return [list(map(int, input().split())) for _ in range(n)]
 
 
def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    
    ans = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    for i in range(h):
        for j in range(w):
            if s[i][j] == '
    
            q = []
            q.append([i, j])
            dist = [[-1 for _ in range(w+5)] for _ in range(h + 5)]
            dist[i][j] = 0
            M = 0
            while q:
                x, y = q[0]
                q.pop(0)
                for p in range(4):
                    nx, ny = x + dx[p], y + dy[p]
                    if 0 <= nx < h and 0 <= ny < w:
                        if dist[nx][ny]==-1 and s[nx][ny] == '.':
                            q.append([nx, ny])
                            dist[nx][ny] = dist[x][y] + 1
                            if M<dist[nx][ny]:
                                M = dist[nx][ny]
            ans = max(ans,M)
    print(ans)
 
if __name__ == "__main__":
    main()

Solution (Python):
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    judge = [[False]*W for _ in range(H)]
    judge[i][j]=True
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='
          continue
        c = b+1
        if judge[h][w]:
          continue
        A[h][w]=c
        judge[h][w]=True
        q.append([h,w])
        
    A = [a for b in A for a in b if a!=inf]
    ans = max(ans,max(A))
    
print(ans)

Solution (Python):

import queue
import copy
import time
sss = time.time()
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**2 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()

for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start, bb):
    dist = [[10**2 for _ in range(W)] for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        olddist = dist[x][y]
        bb[x][y] = '
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            xx = x+dx
            yy = y+dy
            if xx>=0 and xx<= H-1 and yy>=0 and yy<=W-1:
                if bb[xx][yy] != '
                    if dist[xx][yy] == 10**2:
                        dist[xx][yy] = olddist + 1
                        far = max([far,olddist+1])
                        q.put((xx,yy))
        if q.empty():
            break
    return far
res = 0
while 1:
    ttt = time.time()
    if sss-ttt >= 1.8:
        break
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)

Solution (Python):
from collections import deque
import copy

def bfs(grid, start):
    H, W = len(grid), len(grid[0])
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()
 
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return max(map(max, distance))

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


res = -1
for i in range(h):
    for j in range(w):
        if(maze[i][j] == '
        tmpmaze = copy.deepcopy(maze)
        steps = bfs(tmpmaze, [i, j])
        if(steps > res):
            res = steps
print(res)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
maze = []
def mazecal(hs,ws):
    calmaze = [[-1 for _ in range(w)] for _ in range(h)]
    que = deque([[hs,ws,0]])
    smax = 0
    while len(que)!=0:
        cur = que.popleft()
        calmaze[cur[0]][cur[1]] = cur[2]
        smax = max(smax,cur[2])
        if cur[0]>0   and maze[cur[0]-1][cur[1]]==0:
            if calmaze[cur[0]-1][cur[1]] ==-1 or calmaze[cur[0]-1][cur[1]] > cur[2]+1:
                calmaze[cur[0]-1][cur[1]] = cur[2]+1
                que.append([cur[0]-1,cur[1],  cur[2]+1])
        if cur[0]<h-1 and maze[cur[0]+1][cur[1]]==0:
            if calmaze[cur[0]+1][cur[1]] ==-1 or calmaze[cur[0]+1][cur[1]] > cur[2]+1:
                calmaze[cur[0]+1][cur[1]] = cur[2]+1
                que.append([cur[0]+1,cur[1],  cur[2]+1])
        if cur[1]>0   and maze[cur[0]][cur[1]-1]==0:
            if calmaze[cur[0]][cur[1]-1] ==-1 or calmaze[cur[0]][cur[1]-1] > cur[2]+1:
                calmaze[cur[0]][cur[1]-1] = cur[2]+1
                que.append([cur[0]  ,cur[1]-1,cur[2]+1])
        if cur[1]<w-1 and maze[cur[0]][cur[1]+1]==0:
            if calmaze[cur[0]][cur[1]+1] ==-1 or calmaze[cur[0]][cur[1]+1] > cur[2]+1:
                calmaze[cur[0]][cur[1]+1] = cur[2]+1
                que.append([cur[0]  ,cur[1]+1,cur[2]+1])
    return smax

for i in range(h):maze.append([0 if c=='.' else 1 for c in input()])
gmax = 0
for i in range(h):
    for j in range(w):
        if maze[i][j]==0:gmax = max(gmax,mazecal(i,j))
print(gmax)

Solution (Python):
H, W = map(int, input().split())
s="
f=(W+1)*(H+1)
d=[[0]*f for _ in range(f)]
for i in range(W,f-1):
 d[i][i-1]=s[i]==s[i-1]=="."
 d[i][i-W-1]=s[i]==s[i-W-1]=="."
from scipy.sparse.csgraph import csgraph_from_dense as C,floyd_warshall as F
Q=F(C(d),directed=False)
r=-1
for q in Q:
 for x in q:
  if f>x:
   r=max(r,int(x))
print(r)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
S = tuple(map(tuple, read().split()))


def bfs(grid, start):
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
        if not queue:
            return distance[x][y]


answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue

        tmp = bfs(S, (i, j))
        if tmp > answer:
            answer = tmp

print(answer)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return max(map(max, distance))


answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue

        tmp = bfs(S, (i, j))
        if tmp > answer:
            answer = tmp

print(answer)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
        if not queue:
            return distance[x][y]


answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue

        tmp = bfs(S, (i, j))
        if tmp > answer:
            answer = tmp

print(answer)

Solution (Python):
import sys
from collections import deque
from itertools import product

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return max(map(max, distance))


answer = 0
for i, j in product(range(H), range(W)):
    if S[i][j] == '
        continue

    tmp = bfs(S, (i, j))
    if tmp > answer:
        answer = tmp

print(answer)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return [list(map(int, input().split())) for _ in range(n)]
 
 
def main():
    h,w = inpm()
    maze = []
    for _ in range(h):
        s = list(input())
        maze.append(s)
    ans = 0
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    for sx in range(h):
        for sy in range(w):
            if maze[sx][sy] == '
                continue
            else:
                d = [[-1 for _ in range(w)] for _ in range(h)]
                que = []
                d[sx][sy] = 0
                que.append((sx,sy))
                M = 0
                while que:
                    [qx,qy]=que[0]
                    que.pop(0)
                    for i in range(4):
                        nx=qx+dx[i]
                        ny=qy+dy[i]
                        if nx>=0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                            d[nx][ny]=d[qx][qy]+1
                            if d[qx][qy]+1>M:
                                M= d[qx][qy]+1
                            que.append((nx,ny))
                ans = max(ans,M)
    print(ans)
 
 
if __name__ == "__main__":
    main()

Solution (Python):


INF = float('inf')

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

point_list = []
for i in range(w*h):
    point_list.append([w*h]*w*h)
maze = []

Q = []

for i in range(h):
    tmp = list(input())
    maze.append(tmp)

for s_y in range(h):
    for s_x in range(w):
        if maze[s_y][s_x] == "
            continue
        check = []
        Q.append((s_y,s_x))
        check.append((s_y,s_x))
        point_list[s_x+s_y*w][s_x+s_y*w] = 0
        while Q:
            y, x = Q.pop(0)
            if y == 0:
                pass
            elif maze[y-1][x]=="
                pass
            else:
                point_list[s_x+s_y*w][x+(y-1)*w] = min(point_list[s_x+s_y*w][x+(y-1)*w],point_list[s_x+s_y*w][x+y*w]+1)
                if (y-1,x) in check:
                    pass
                else:
                    check.append((y-1,x))
                    Q.append((y-1,x))
                    

            if y == h-1 :
                pass
            elif maze[y+1][x]=="
                pass
            else:
                point_list[s_x+s_y*w][x+(y+1)*w] = min(point_list[s_x+s_y*w][x+(y+1)*w],point_list[s_x+s_y*w][x+y*w]+1)
                if (y+1,x) in check:
                    pass
                else:
                    check.append((y+1,x))
                    Q.append((y+1,x))
                    

            if x==0:
                pass
            elif maze[y][x-1]=="
                pass
            else:
                point_list[s_x+s_y*w][(x-1)+y*w] = min(point_list[s_x+s_y*w][(x-1)+y*w],point_list[s_x+s_y*w][x+y*w]+1)
                if (y,x-1) in check:
                    pass
                else:
                    check.append((y,x-1))
                    Q.append((y,x-1))
                    

            if x==w-1:
                pass
            elif maze[y][x+1]=="
                pass
            else:
                point_list[s_x+s_y*w][(x+1)+y*w] = min(point_list[s_x+s_y*w][(x+1)+y*w],point_list[s_x+s_y*w][x+y*w]+1)
                if (y,x+1) in check:
                    pass
                else:
                    check.append((y,x+1))
                    Q.append((y,x+1))
                    
max_list = []
for i in range(w*h):
    tmp = set(point_list[i])
    if min(tmp)==w*h:
        continue
    if w*h in tmp:
        tmp.remove(w*h)
    max_list.append(max(tmp))

ans = max(max_list)
print(ans)

Solution (Python):
h,w = map(int,input().split())
meiro = [list(input()) for i in range(h)]
max_d = 0
from collections import deque

def bfs(sx,sy):
    que = deque([(sx,sy,0)])
    d = [[0]*w for i in range(h)]
    d[sx][sy] = 1
    max_len=0
    while que:
        x,y,tmp_len = que.popleft()
        for dx,dy in [(0,1),(1,0),(-1,0),(0,-1)]:
            tmp = tmp_len
            nx,ny = x+dx,y+dy
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 0 and meiro[nx][ny] =='.':
                d[nx][ny] = 1
                max_len = max(max_len, tmp+1)
                que.append((nx,ny,tmp+1))
    return max_len

for s_i in range(h):
    for s_j in range(w):
        if meiro[s_i][s_j] == "
            continue
        max_d = max(bfs(s_i,s_j), max_d)
print(max_d)

Solution (Python):
from collections import deque    
H,W = map(int, input().split())
maze = []
ans = 0
dist =[]
q = deque([])
tmp = 0

for i in range(H):
    maze.append(input())

for i in range(H):
    for j in range(W):
        if maze[i][j] == '
            continue
        dist = [[-1]*W for i in range(H)] 
        q.append([i,j]) 
        dist[i][j] = 0
        while(q):
            a,b = q.popleft()
            if a + 1 < H:
                if maze[a+1][b] == '.' and dist[a+1][b] == -1:
                    q.append([a+1, b])
                    dist[a+1][b] = dist[a][b] + 1
                    tmp = dist[a+1][b] 
            if a > 0:
                if maze[a-1][b] == '.' and dist[a-1][b] == -1:
                    q.append([a-1, b])
                    dist[a-1][b] = dist[a][b] + 1
                    tmp = dist[a-1][b]
            if b + 1 < W:
                if maze[a][b+1] == '.' and dist[a][b+1] == -1:
                    q.append([a, b+1])
                    dist[a][b+1] = dist[a][b] + 1
                    tmp = dist[a][b+1]
            if b > 0:
                if maze[a][b-1] == '.' and dist[a][b-1] == -1:
                    q.append([a, b-1])
                    dist[a][b-1] = dist[a][b] + 1
                    tmp = dist[a][b-1]
        ans = max(ans,tmp)


print(ans)