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):
def grid_bfs():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    from collections import deque
    dire = ((0, -1), (-1, 0), (1, 0), (0, 1))
    def bfs(sx, sy):
        dist = [[-1]*W for _ in range(H)] 
        dist[sx][sy] = 0
        que = deque([(sx, sy)]) 
        while que:
            x, y = que.popleft()
            d = dist[x][y]
            for dx, dy in dire:
                nx,ny = x+dx,y+dy
                
                if 0<=nx<H and 0<=ny<W and S[nx][ny] == '.' and dist[nx][ny] == -1:
                    dist[nx][ny] = d+1
                    que.append((nx, ny))
        return max(map(lambda x: max(x), dist)) 



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

grid_bfs()

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

nei = []
ans = 0
color = []

def dfs(i, fr, hop):
    global nei, color, ans
    ans = max(ans, hop)
    color[i] = 1
    for k in nei[i]:
        if k != fr and color[k] == -1:
            dfs(k, i, hop+1)

def dijkstra(n, start, nbl):
    """n: 頂点数, start: 始点, nbl: 隣接リスト"""
    import heapq
    WHITE = 1<<5
    GRAY = 1<<10
    BLACK = 1<<15
    INF = 1<<20
    color = [WHITE] * n
    distance = [INF] * n
    
    q = []

    distance[start] = 0
    heapq.heappush(q, (0, start))
    while len(q) != 0:
        du, u = heapq.heappop(q)
        
        color[u] = BLACK
        if distance[u] < du:
            continue
        for next, cost in nbl[u]:
            if color[next] != BLACK and distance[u] + cost < distance[next]:
                distance[next] = distance[u] + cost
                color[next] = GRAY
                heapq.heappush(q, (distance[next], next))
    for i, v in enumerate(distance[:]):
        if v == INF:
            distance[i] = -1
    return distance

def main():
    global nei, color
    h, w = list(map(int, input().strip().split()))
    G = [0] * h
    nei = [[] for _ in range(w*h)]
    color = [-1] * (w*h)
    for i in range(h):
        G[i] = input().strip()
    for i in range(h):
        for j in range(w):
            if G[i][j] == '.':
                if i != 0 and G[i-1][j] == '.':
                    nei[w*i+j].append((w*(i-1)+j, 1))
                if i != h-1 and G[i+1][j] == '.':
                    nei[w*i+j].append((w*(i+1)+j, 1))
                if j != 0 and G[i][j-1] == '.':
                    nei[w*i+j].append((w*i+j-1, 1))
                if j != w-1 and G[i][j+1] == '.':
                    nei[w*i+j].append((w*i+j+1, 1))
    ans = 0
    for i in range(h):
        for j in range(w):
            if G[i][j] == '.':
                
                ans = max(max(dijkstra(w*h, w*i+j, nei)), ans)
    print(ans)

if __name__ == '__main__':
    main()

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

start = []
for i in range(h):
    for j in range(w):
        if s[i][j:j+1] == ".":
            start.append([i,j])


def meiro(ss,count):
    if len(ss) == 0:
  
  
  
        global ans
        ans = max(ans,count-1)
    else:
        kouho = [[0,1],[0,-1],[1,0],[-1,0]]
        next_s = []
        for hw in ss:
            for i in range(4):    
                next_w = hw[1]+kouho[i][1]
                next_h = hw[0]+kouho[i][0]
                if next_w < w and next_w >= 0:
                    if next_h < h and next_h >= 0:
                        if s[next_h][next_w:next_w+1] == "." and jokyo[next_h][next_w] == -1:
                            next_s.append([next_h,next_w])
                            jokyo[next_h][next_w] = count + 1
        meiro(next_s,count+1)

ans = 0
for i in range(len(start)):
    jokyo = [[-1 for i in range(w)] for j in range(h)]
    jokyo[start[i][0]][start[i][1]] = 0
    meiro([start[i]],0)

print(ans)

Solution (Python):
from collections import deque



def bfs(sx, sy):
    cnt = 0
    f_inf = float('inf')
    dist = [[f_inf] * m for _ in range(n)]

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

    
    que = deque([])
    que.append((sx, sy))
    dist[sx][sy] = 0

    while que:
        p = que.popleft()

        for i in range(4):
            
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            
            
            if n > nx >= 0 and \
               m > ny >= 0 and \
               s[nx][ny] != '
               dist[nx][ny] == f_inf:
                que.append((nx, ny))
                dist[nx][ny] = dist[p[0]][p[1]] + 1
                cnt = dist[nx][ny]

    return cnt


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

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

Solution (Python):
from  collections import  deque
H , W = map(int, input().split())
mp = []
for i in range(H):
    mp.append(list(input()))


class node():
    def __init__(self):
        self.wall = 0
        self.reaf = []
        self.tansaku = 0
        self.cost = 0


nodelist = [node() for i in range(H * W)]
count = 0
for i in range(len(mp)):
    for j in range(len(mp[i])):
        if mp[i][j] == "
            nodelist[count].wall = 1
        count += 1
count2 = 0
for i in range(len(nodelist)):

    if count2 != 0:
        if nodelist[i-1].wall == 0:
            nodelist[i].reaf.append(i-1)
    if count2 != W-1:
        if nodelist[i+1].wall == 0:
            nodelist[i].reaf.append(i+1)
    if i+W < len(nodelist):
        if nodelist[i+W].wall == 0:
            nodelist[i].reaf.append(i+W)
    if i-W >= 0:
        if nodelist[i-W].wall == 0:
            nodelist[i].reaf.append(i-W)

    count2 += 1
    if count2 == W:
        count2 = 0

def tansaku(nodelist,que):
    data = que.popleft()
    for j in nodelist[data].reaf:
        if nodelist[j].tansaku == 0:
            que.append(j)
            nodelist[j].tansaku = 1
            nodelist[j].cost = nodelist[data].cost + 1
    if len(que) != 0:
        tansaku(nodelist, que)


def nodereset(nodelist):
    for i in range(len(nodelist)):
        nodelist[i].tansaku = 0
        nodelist[i].cost = 0
    return nodelist

maxnum = 0

for i in range(len(nodelist)):
    if nodelist[i].wall == 0:
        nodelist = nodereset(nodelist)
        que = deque()
        que.append(i)
        nodelist[i].tansaku = 1
        tansaku(nodelist, que)
        for j in range(len(nodelist)):
            if nodelist[j].cost > maxnum:

                maxnum = nodelist[j].cost
print(maxnum)

Solution (Python):
from collections import deque
 
h, w = map(int, input().split())
a = ''.join(input() + '
n = len(a) - 1
b = ['
q = deque()
d = -1, 1, -w - 1, w + 1
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in d:
        j += i
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Solution (Python):
from collections import deque
 
h, w = map(int, input().split())
a = ''.join(input() + '
n = len(a) - 1
b = ['
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q = deque([i])
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (i - 1, i + 1, i - w - 1, i + w + 1):
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Solution (Python):
from collections import deque
 
h, w = map(int, input().split())
a = ''.join(input() + '
n = len(a)
b = ['
q = deque()
d = -1, 1, -w - 1, w + 1
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in d:
        j += i
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Solution (Python):
from collections import deque
 
h, w = map(int, input().split())
a = ''.join(input() + '
n = len(a)
b = ['
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q = deque([i])
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (i - 1, i + 1, i - w - 1, i + w + 1):
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
a = ''.join(input() + '
n = len(a)
b = ['
q = deque()
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (-1, 1, -w - 1, w + 1):
        j += i
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Solution (Python):
from collections import deque
 
h, w = map(int, input().split())
a = ''.join(input() + '
n = len(a)
b = ['
q = deque()
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (i - 1, i + 1, i - w - 1, i + w + 1):
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
a = ''.join(input() + '
n = len(a)
b = ['
w += 1
q = deque()
r = 0
for i in range(n):
  if a[i] == '.':
    b[: 1 - w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (-1, 1, -w, w):
        j += i
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
a = ''.join(input() + '
n = len(a)
b = ['
q = deque()
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (i - 1, i + 1, i - w - 1, i + w + 1):
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
a = ''.join(input() + '
n = len(a)
b = ['
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q = deque([i])
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (i - 1, i + 1, i - w - 1, i + w + 1):
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

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
    queue = deque([start])
    while queue:
        v = queue.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
            queue.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):
from collections import deque
H, W = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "
X += [1] * (W + 2)
H, W = H+2, W+2
 
def BFS(i0=0):
    Q = deque([i0])
    D = [-1] * (H * W)
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for y in (x+W, x-W, x+1, x-1):
            if X[y] == 0:
                if D[y] == -1:
                    D[y] = D[x] + 1
                    Q.append(y)
    return D
 
ma = 0
for i in range(H):
    for j in range(W):
        if X[i*W+j] == 0:
            ma = max(ma, max(BFS(i*W+j)))
print(ma)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "
X += [1] * (W + 2)
H, W = H+2, W+2

def BFS(i0=0):
    Q = deque([i0])
    D = [-1] * (H * W)
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for y in (x+W, x-W, x+1, x-1):
            if X[y] == 0:
                if D[y] == -1:
                    D[y] = D[x] + 1
                    Q.append(y)
    return D

ma = 0
for i in range(H):
    for j in range(W):
        if X[i*W+j] == 0:
            ma = max(ma, max(BFS(i*W+j)))
print(ma)

Solution (Python):

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


import numpy as np

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

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "
            dp = np.full((H, W), INF)
            q = []
            q.insert(0, (i, j))
            dp[i, j] = 0
            while len(q):
                x, y = q.pop()

                for t in range(4):
                    nx, ny = x + dx[t], y + dy[t]

                    if (0 <= nx < H) and (0 <= ny < W) and (S[nx][ny] != "
                        q.insert(0, (nx, ny))
                        dp[nx, ny] = dp[x, y] + 1
            for row in dp:
                answer = max(answer, max(row))
print(int(answer))

Solution (Python):
from collections import deque

h,w = map(int, input().split())
PATH = "."
WALL = "
z=0

maze=list()
for a in range(h):
 mazew=list()
 mazeh = input()
 for b in range(w):
  mazew.append(mazeh[b])
 maze.append(mazew)
for c in range(h):
 for d in range(w):
   
   
  if maze[c][d]==WALL:
   continue
  else:
   distance_visited = list()
   for l in range(h):
    distance_visited.append([-1] * w)
   
   queue = deque([[c, d]])
   distance_visited[c][d] = 0
   while True:
    x,y = queue.popleft()
      
    for i,j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
     new_x, new_y = x + i, y + j
       
     if new_x>=0 and new_x<=h-1 and new_y>=0 and new_y<=w-1:
      if maze[new_x][new_y] != WALL and distance_visited[new_x][new_y] == -1:
               
       distance_visited[new_x][new_y] = distance_visited[x][y] + 1
       queue.append([new_x, new_y])
       if distance_visited[new_x][new_y]>z:
        z=distance_visited[new_x][new_y]
    if queue==deque([]):
     break
print(z)

Solution (Python):
from collections import deque

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

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

r=[[1,0],[-1,0],[0,1],[0,-1]]
def bfs(i,j):
    global h,w,r
    f=[-1 for _ in range(h*w)]
    que = collections.deque([[i,j,0]])
    f[i*w+j] =0
    while que:
        i,j,k = que.popleft()
        for sr in r:
            ti = i + sr[0]
            tj = j + sr[1]
            if ti>=0 and tj>=0 and ti<h and tj<w:
                if s[ti][tj] == ".":
                    if f[ti*w+tj] == -1:
                        f[ti*w+tj] = k+1
                        que.append([ti,tj,k+1])
    return max(f)


res = 0
for i in range(h):
    for j in range(w):
        if s[i][j] ==".":
            tres = bfs(i,j)
            res = max(res,tres)
print(res)

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

r=[[1,0],[-1,0],[0,1],[0,-1]]
def bfs(i,j):
    global h,w,r
    f=[-1 for _ in range(h*w)]
    que = collections.deque([[i,j,0]])
    f[i*w+j] =0
    while que:
        i,j,k = que.popleft()
        for sr in r:
            ti = i + sr[0]
            tj = j + sr[1]
            if ti>=0 and tj>=0 and ti<h and tj<w:
                if s[ti][tj] == ".":
                    if f[ti*w+tj] == -1:
                        f[ti*w+tj] = k+1
                        que.append([ti,tj,k+1])
    return max(f)


res = 0
for i in range(h):
    for j in range(w):
        if s[i][j] ==".":
            tres = bfs(i,j)
            res = max(res,tres)
print(res)

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

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

def BFS(i,j,que):
    count = 0
    for k in range(4):
        row = i + di[k]
        col = j + dj[k]
        if H > row >=0 and W >col >= 0 \
            and dist[row][col] == float('inf')\
                and S[row][col] != "
            
            que.append([row,col])
            dist[row][col] = dist[i][j] + 1
            count = dist[row][col]
    return count


path_max = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            continue
        que = []
        stt = [i,j]
        que.append(stt)
        dist = [[float('inf') for ii in range(W)] for jj in range(H)]
        dist[i][j] = 0
        while que:
            idx = que[0]
            que.pop(0)
            count  = BFS(idx[0],idx[1],que)
            path_max = max(path_max,count)

print(path_max)

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


from collections import deque

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

sum_sharp = sum([A[i].count('

fin_d_max = 1

for s_i in range(H):
    for s_j in range(W):
        d_max = 0
        
        q_i = deque()
        
        q_j = deque()
        D = [[-1]*W for i in range(H)]
        flag = 1

        if A[s_i][s_j] == '.':
            D[s_i][s_j] = 0
            
            q_i.append(s_i)
            
            q_j.append(s_j)
            
            while len(q_i)!=0:
                
                i = q_i.popleft()
                
                j = q_j.popleft()
                for x in range(4):
                    ni = i+di[x]
                    nj = j+dj[x]
                    if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '
                        continue
                    else:
                        flag += 1
                        D[ni][nj] = D[i][j]+1
                        d_max = max(d_max, D[ni][nj])
                        
                        q_i.append(ni)
                        
                        q_j.append(nj)
        fin_d_max = max(fin_d_max, d_max)
                
print(fin_d_max)

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

A = [list(input()) for i in range(H)]




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

sum_sharp = sum([A[i].count('

fin_d_max = 1

for s_i in range(H):
    for s_j in range(W):
        
        d_max = 0
        q_i = []
        
        
        q_j = []
        
        
        D = [[-1]*W for i in range(H)]
        
        flag = 1

        if A[s_i][s_j] == '.':
            D[s_i][s_j] = 0
            
            q_i.append(s_i)
            
            q_j.append(s_j)
            
            
            
            while len(q_i)!=0:
            
                
                i = q_i.pop(0)
                
                
                j = q_j.pop(0)
                
                for x in range(4):
                    ni = i+di[x]
                    nj = j+dj[x]
                    
                    if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '
                    
                        continue
                    
                        
                        
                    else:
                        
                            
                        flag += 1
                        D[ni][nj] = D[i][j]+1
                        d_max = max(d_max, D[ni][nj])
                        
                        q_i.append(ni)
                        q_j.append(nj)
                        
        fin_d_max = max(fin_d_max, d_max)
                
print(fin_d_max)

Solution (Python):
from collections import deque

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

Solution (Python):
h,w=map(int,input().split())
M=[]
for i in range(h):
    s=input()
    H=[]
    for j in range(w):
        H.append(0) if s[j]=="." else H.append(1)
    M.append(H)

def make2D(x,y):
    aM=[]
    for i in range(h):
        aH=[]
        for j in range(w):
            aH.append(0) if M[i][j]==0 else aH.append(-1)
        aM.append(aH)
    return aM

from collections import deque
ans=0
for i in range(h):
    for j in range(w):
        if M[i][j]==1:
            continue
        aM=make2D(h,w)
        q=deque()
        q.append([i,j])
        while q:
            now=q.popleft()
            for a,b in ([0,1],[1,0],[0,-1],[-1,0]):
                if 0<=now[0]+a<h and 0<=now[1]+b<w:
                    if aM[now[0]+a][now[1]+b]==0 and (now[0]+a!=i or now[1]+b!=j):
                        aM[now[0]+a][now[1]+b]=aM[now[0]][now[1]]+1
                        q.append([now[0]+a,now[1]+b])
            if len(q)==0:
                break
        m=0
        for z in range(h):
            m=max(m,max(aM[z]))
        ans=max(ans,m)
print(ans)

Solution (Python):
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): 
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if s.L[hh + 1][ww + 1] >= 0 and T[hh][ww] == -1:
          q.put([hh, ww])
          T[hh][ww] = k + 1
    return T, k

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

for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      S[i][j] = 0
    else:
      S[i][j] = -1
g = gridMan(S)
g.makeWall()
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == 0:
      ans = max(ans, g.dist([i, j])[1])

print(ans)

Solution (Python):
import sys
from queue import Queue


def print_costs(costs):
    for c in costs:
        print(c)


def solve(inp):
    (H, W) = map(int, inp.readline().strip().split(' '))
    S = [list(inp.readline().strip()) for i in range(H)]

    max_cost = 0
    for start_y in range(H):
        for start_x in range(W):
            if S[start_y][start_x] == '
                continue
            costs = [[0 for w in range(W)] for h in range(H)]
            costs[start_y][start_x] = 1
            queue = Queue()
            queue.put((start_y, start_x))
            cost = 1
            while not queue.empty():
                (y, x) = queue.get()
                
                for (next_y, next_x) in [(y - 1, x), (y, x + 1), (y + 1, x), (y, x - 1)]:
                    if 0 <= next_y < H and 0 <= next_x < W and S[next_y][next_x] == '.' and costs[next_y][next_x] == 0:
                        costs[next_y][next_x] = costs[y][x] + 1
                        if cost < costs[next_y][next_x]:
                            cost = costs[next_y][next_x]
                        queue.put((next_y, next_x))
            if cost > max_cost:
                max_cost = cost
            
            
            

    return str(max_cost - 1)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


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

INF = 1001001001
dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

ans = 0
for i, j in product(range(H), range(W)):
    if S[i][j] == '
        continue
    d = [[INF] * W for i in range(H)]
    d[i][j] = 0
    q = deque([(i, j)])
    while len(q) > 0:
        x, y = q.popleft()
        for dx, dy in dr:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != '
                d[nx][ny] = d[x][y] + 1
                ans = max(d[nx][ny], ans)
                q.append((nx, ny))
print(ans)

Solution (Python):
h,w=map(int,input().split())
inf=10**3
d=((-1,0),(1,0),(0,-1),(0,1))
S=[["
S.extend([["
S.append(["
import collections
def dist(a,b):
  D=[[inf]*(w+2) for _ in range(h+2)]
  D[a][b]=0
  Visit=collections.deque()
  Visit.append(100*a+b)
  while Visit:
    v=Visit.popleft()
    va,vb=v//100,v%100
    for dx,dy in d:
      if S[va+dx][vb+dy]=="." and D[va+dx][vb+dy]==inf:
        Visit.append((va+dx)*100+(vb+dy))
        D[va+dx][vb+dy]=D[va][vb]+1
  ret=0
  for i in range(h):
    for j in range(w):
      if D[i+1][j+1]<inf:
        ret=max(ret,D[i+1][j+1])
  return ret
ans=0
for i in range(h):
  for j in range(w):
    if S[i+1][j+1]==".":
      ans=max(dist(i+1,j+1),ans)
print(ans)

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

A = [list(input()) for i in range(H)]


from collections import deque

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

sum_sharp = sum([A[i].count('

fin_d_max = 1

for s_i in range(H):
    for s_j in range(W):
        
        d_max = 0
        
        q_i = deque()
        
        q_j = deque()
        D = [[-1]*W for i in range(H)]
        
        flag = 1

        if A[s_i][s_j] == '.':
            D[s_i][s_j] = 0
            
            q_i.append(s_i)
            
            q_j.append(s_j)
            
            
            
            while len(q_i)!=0:
            
                
                i = q_i.popleft()
                
                j = q_j.popleft()
                for x in range(4):
                    ni = i+di[x]
                    nj = j+dj[x]
                    
                    if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '
                    
                        continue
                    
                        
                        
                    else:
                        
                            
                        flag += 1
                        D[ni][nj] = D[i][j]+1
                        d_max = max(d_max, D[ni][nj])
                        
                        q_i.append(ni)
                        q_j.append(nj)
                        
        fin_d_max = max(fin_d_max, d_max)
                
print(fin_d_max)

Solution (Python):
from collections import deque
INF = 1001001001
di = [-1, 0, 1, 0]
dj = [ 0,-1, 0, 1]

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

ans = 0
for si in range(H):
    for sj in range(W):
        if S[si][sj] == '
        dist = [[INF] * W for _ in range(H)]
        dist[si][sj] = 0
        q = deque([(si, sj)])
        while q:
            i, j = q.popleft()
            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] == '
                if dist[ni][nj] != INF: continue
                dist[ni][nj] = dist[i][j] + 1
                q.append([ni, nj])
        for i in range(H):
            for j in range(W):
                if dist[i][j] == INF: continue
                ans = max(ans, dist[i][j])
print(ans)

Solution (Python):
h,w=map(int,input().split())
inf=10**3
d=((-1,0),(1,0),(0,-1),(0,1))
S=[["
S.extend([["
S.append(["
import heapq

def dist(a,b):
  D=[[inf]*(w+2) for _ in range(h+2)]
  D[a][b]=0
  Visit=[100*a+b]
  heapq.heapify(Visit)
  while Visit:
    v=heapq.heappop(Visit)
    vd,va,vb=v//(10**4),(v%(10**4))//100,v%100
    for dx,dy in d:
      if S[va+dx][vb+dy]=="." and D[va+dx][vb+dy]==inf:
        heapq.heappush(Visit,(vd+1)*(10**4)+(va+dx)*(10**2)+vb+dy)
        D[va+dx][vb+dy]=vd+1
  ret=0
  for i in range(h):
    for j in range(w):
      if D[i+1][j+1]<inf:
        ret=max(ret,D[i+1][j+1])
  return ret
ans=0
for i in range(h):
  for j in range(w):
    if S[i+1][j+1]==".":
      ans=max(dist(i+1,j+1),ans)
print(ans)

Solution (Python):
def search(y, x):
    dy_list = [-1, 0, 1, 0]
    dx_list = [0, -1, 0, 1]

    queue = [(y, x)]
    dist = [[-1 for _ in range(w)] for _ in range(h)]
    dist[y][x] = 0
    while queue:
        
        now_y, now_x = queue.pop(0)
        for dy, dx in zip(dy_list, dx_list):
            next_y = now_y+dy
            next_x = now_x+dx

            
            if not(0 <= next_y < h and 0 <= next_x < w):
                continue
            
            elif s_list[next_y][next_x] == '
                continue
            
            elif dist[next_y][next_x] != -1:
                continue

            dist[next_y][next_x] = dist[now_y][now_x]+1
            
            
            queue.append((next_y, next_x))

    return max(max(d) for d in dist)


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

ans = 0
for i in range(h):
    for j in range(w):
        if s_list[i][j] == '.':
            ans = max(search(i, j), ans)
print(ans)