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 = [input() for _ in range(h)]
check = [[-1]*w for _ in range(h)]

def BFS(maze,check,si,sj):
    queue = deque([[si,sj]])
    check[si][sj] = 0
    maxd = 0
    while queue:
        x,y = queue.popleft()
        for k,l in ([0,1], [0,-1], [1,0], [-1,0]):
            i2, j2= x+k, y+l
            if i2<0 or i2>=h or j2<0 or j2>=w:
                continue
            if maze[i2][j2] == '.' and check[i2][j2] == -1:
                check[i2][j2] = check[x][y] + 1
                maxd = max(maxd,check[i2][j2])
                queue.append([i2,j2])
    return maxd

ans = 0
for i in range(h):
    for j in range(w):
        check = [[-1]*w for _ in range(h)]
        if maze[i][j] == '.':
            si , sj = i, j
            ans = max(ans,BFS(maze,check,si,sj))
print(ans)

Solution (Python):
from collections import deque
def bfs(S,H,W,sh,sw):
    dist=[[-1]*W for i in range(H)]
    dist[sh][sw]=0

    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    lo=0
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            nh=h+dx[dir]
            nw=w+dy[dir]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(dist[nh][nw]!=-1 or S[nh][nw]=='
                continue
            dist[nh][nw]=dist[h][w]+1
            lo=max(lo,dist[nh][nw])
            S[nh][nw]=='
            d.append([nh,nw])
    return lo

H,W=map(int,input().split())
S=[input() for i in range(H)]
ans=-1
for i in range(H):
    for j in range(W):
        if(S[i][j]!='
            ans=max(ans,bfs(S,H,W,i,j))
print(ans)

Solution (Python):
from collections import deque
H, W = list(map(int, input().split()))

S = [['
max_n = 0

for h1 in range(1,H+1):
  for w1 in range(1,W+1):
    if S[h1][w1] == '
      continue
    distance = [[-1 for _ in range(W+2)] for _ in range(H+2)]
    distance[h1][w1] = 0
    que = deque([])
    que.append([h1,w1])
    while que:
      h, w = que.popleft()
      if S[h-1][w] == '.' and distance[h-1][w] == -1:
        que.append([h-1,w])
        distance[h-1][w] = distance[h][w] + 1
      if S[h+1][w] == '.' and distance[h+1][w] == -1:
        que.append([h+1,w])
        distance[h+1][w] = distance[h][w] + 1
      if S[h][w-1] == '.' and distance[h][w-1] == -1:
        que.append([h,w-1])
        distance[h][w-1] = distance[h][w] + 1
      if S[h][w+1] == '.' and distance[h][w+1] == -1:
        que.append([h,w+1])
        distance[h][w+1] = distance[h][w] + 1
    hw_max_n = max([max(dis) for dis in distance])
    max_n = max(max_n, hw_max_n)
print(max_n)

Solution (Python):

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


S = [['


max_n = 0

for h1 in range(1,H+1):
  for w1 in range(1,W+1):
    if S[h1][w1] == '
      continue
    distance = [[1000 for _ in range(W+2)] for _ in range(H+2)]
    done_que = [[0 for _ in range(W+2)] for _ in range(H+2)]
    distance[h1][w1] = 0
    que = []
    que.append([h1,w1])
    que_i = 0
    while que_i < len(que):
      h, w = que[que_i]
      if S[h-1][w] == '.' and done_que[h-1][w] == 0:
        done_que[h-1][w] = 1
        que.append([h-1,w])
        distance[h-1][w] = min(distance[h][w] + 1, distance[h-1][w])
      if S[h+1][w] == '.' and done_que[h+1][w] == 0:
        done_que[h+1][w] = 1
        que.append([h+1,w])
        distance[h+1][w] = min(distance[h][w] + 1, distance[h+1][w])
      if S[h][w-1] == '.' and done_que[h][w-1] == 0:
        done_que[h][w-1] = 1
        que.append([h,w-1])
        distance[h][w-1] = min(distance[h][w] + 1, distance[h][w-1])
      if S[h][w+1] == '.' and done_que[h][w+1] == 0:
        done_que[h][w+1] = 1
        que.append([h,w+1])
        distance[h][w+1] = min(distance[h][w] + 1, distance[h][w+1])
      que_i += 1
    hw_max_n = 0
    for h2 in range(1,H+1):
      for w2 in range(1,W+1):
        if distance[h2][w2] != 1000:
          hw_max_n = max(hw_max_n, distance[h2][w2])
    max_n = max(max_n, hw_max_n)
print(max_n)

Solution (Python):
from collections import deque

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

max_cnt = 0

for h in range(H):
    for w in range(W):
        d = [[-1 for _ in range(W)] for _ in range(H)]
        que = deque([(h, w, 0)])
        while len(que) > 0:
            x, y, c = que.popleft()
            if x >= H or x < 0 or y >= W or y < 0:
                continue
            if d[x][y] == -1 and S[x][y] == ".":
                d[x][y] = c
                max_cnt = max(c, max_cnt)
            else:
                continue
            que.append((x + 1, y, c + 1))
            que.append((x - 1, y, c + 1))
            que.append((x, y + 1, c + 1))
            que.append((x, y - 1, c + 1))


print(max_cnt)

Solution (Python):
def main():
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    for i in range(h):
        for j in range(w):
            if a[i][j]==".":
                a[i][j]=99999
    ans=0
    import collections
    from copy import deepcopy
    direction=[[0,1],[0,-1],[1,0],[-1,0]]
    for sh in range(h):
        for sw in range(w):
            if a[sh][sw]==99999:
                field=deepcopy(a)
                field[sh][sw]=0
                next_list=collections.deque([[sh,sw]])
                while next_list:
                    n=next_list.popleft()
                    for dx,dy in direction:
                        ny,nx=n[0]+dy,n[1]+dx
                        if 0<=ny<=h-1 and 0<=nx<=w-1 and field[ny][nx]!="
                            field[ny][nx]=field[n[0]][n[1]]+1
                            if field[ny][nx]>ans:
                                ans=field[ny][nx]
                            next_list.append([ny,nx])
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    for i in range(h):
        for j in range(w):
            if a[i][j]==".":
                a[i][j]=99999
    ans=0
    import collections
    from copy import deepcopy
    direction=[[0,1],[0,-1],[1,0],[-1,0]]
    for sh in range(h):
        for sw in range(w):
            if a[sh][sw]==99999:
                field=deepcopy(a)
                field[sh][sw]=0
                next_list=collections.deque([[sh,sw]])
                while next_list:
                    n=next_list.popleft()
                    for dx,dy in direction:
                        ny,nx=n[0]+dy,n[1]+dx
                        if 0<=ny<=h-1 and 0<=nx<=w-1 and field[ny][nx]!="
                            field[ny][nx]=field[n[0]][n[1]]+1
                            ans=max(ans,field[ny][nx])
                            next_list.append([ny,nx])
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
h,w=map(int,input().split())
m=np.zeros((h,w))
for i in range(h):
  for j,c in enumerate(list(input())):
    if c=='
      m[i,j]=-1
def dis(mc,i,j):
  if mc[i,j]!=0:return 0
  q=[(i,j,1)]
  mc[i,j]=-1
  while 0<len(q):
    i,j,x=q.pop(0)
    if i+1<h and mc[i+1,j]==0:
      mc[i+1,j]=x
      q.append((i+1,j,x+1))
    if i-1>=0 and mc[i-1,j]==0:
      mc[i-1,j]=x
      q.append((i-1,j,x+1))
    if j+1<w and mc[i,j+1]==0:
      mc[i,j+1]=x
      q.append((i,j+1,x+1))
    if j-1>=0 and mc[i,j-1]==0:
      mc[i,j-1]=x
      q.append((i,j-1,x+1))
  return np.max(mc)
max=0
for i in range(h):
  for j in range(w):
    mc = np.copy(m)
    tmp=dis(mc,i,j)
    if max<tmp:max=tmp
print(int(max))

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

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

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

def update(vs, i, j, x, q):
  if vs[i][j] != -1 or S[i][j] == '
    return
  vs[i][j] = x
  q.append((i,j))

mx = 0
for i, j in product(range(h), range(w)):
  if S[i][j] == '
    continue
  q = deque([])
  vs = [[-1 for i in range(w)] for j in range(h)]
  update(vs, i, j, 0, q)
  while len(q) > 0:
    
    
    
    current_q = q.popleft()
    qi, qj = current_q[0], current_q[1]
    for k in range(4):
      ni, nj = qi + di[k], qj + dj[k]
      if not(0 <= ni < h) or not(0 <= nj < w):
        continue
      update(vs, ni, nj, vs[qi][qj]+1, q)
  for i, j in product(range(h),range(w)):
    if vs[i][j] == -1:
      continue
    mx = max(mx, vs[i][j])
print(int(mx))

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

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

maze_array = [input().split()[0] for _ in range(H)]

ans = 0
for hh in range(H):
    for ww in range(W):
        if maze_array[hh][ww] == "
            continue
        flag = [[0 for _ in range(W)] for _ in range(H)]
        queue = deque()
        queue.append((hh,ww,0))
        flag[hh][ww] = 1
        while len(queue):
            h, w, p = queue.popleft()
            
            if w != W - 1 and flag[h][w+1] == 0 and maze_array[h][w+1] == ".":
                flag[h][w+1] = 1
                ans = max(ans,p+1)
                queue.append((h,w+1,p+1))
            if h != H - 1 and flag[h+1][w] == 0 and maze_array[h+1][w] == ".":
                flag[h+1][w] = 1
                ans = max(ans,p+1)
                queue.append((h+1,w,p+1))
            if w != 0 and flag[h][w-1] == 0 and maze_array[h][w-1] == ".":
                flag[h][w-1] = 1
                ans = max(ans,p+1)
                queue.append((h,w-1,p+1))  
            if h != 0 and flag[h-1][w] == 0 and maze_array[h-1][w] == ".":
                flag[h-1][w] = 1
                ans = max(ans,p+1)
                queue.append((h-1,w,p+1))
print(ans)

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

load=[]
for i in range(0,H):
    for j in range(0,W):
        if S[i][0][j]=='.':
            load.append((i,j))

ans=0
for i,j in load:
    start=(i,j)
    dp=[[500 for i in range(0,W)] for i in range(0,H)]
    dp[i][j]=0
    q=[]
    q.append((i,j))
    sub=[]
    while q!=[]:
        while q!=[]:
            x=q[0]
            q.remove(x)
            s=x[0]
            t=x[1]
            if (s+1,t) in load and dp[s+1][t]>dp[s][t]+1:
                sub.append((s+1,t))
                dp[s+1][t]=dp[s][t]+1
            if (s,t+1) in load and dp[s][t+1]>dp[s][t]+1:
                sub.append((s,t+1))
                dp[s][t+1]=dp[s][t]+1
            if (s-1,t) in load and dp[s-1][t]>dp[s][t]+1:
                sub.append((s-1,t))
                dp[s-1][t]=dp[s][t]+1
            if (s,t-1) in load and dp[s][t-1]>dp[s][t]+1:
                sub.append((s,t-1))
                dp[s][t-1]=dp[s][t]+1
            if q==[]:
                q=sub
                sub=[]
                break
    test=max(dp[i][j] for i in range(0,H) for j in range(0,W) if (i,j) in load)
    if test>ans:
        ans=test
print(ans)

Solution (Python):
H, W = map(int, input().split())
cost_list = [[0]*W for i in range(H)]
cost_check = [[0]*W for i in range(H)]
path_list = [] 
max_cost = 0 

def path_cost(x, y):
    if path_list[x][y]=="
        return -1
    
    for i in range(H):
        for j in range(W):
            cost_check[i][j] = 0
            cost_list[i][j] = 0
    
    path_queue = [[x,y]]
    cost_check[x][y] = 1
    
    while len(path_queue)>0:
        
        path = path_queue.pop(0)
        next_x, next_y = path[0], path[1]
        
        if next_x+1<H:
            if path_list[next_x+1][next_y]=="." and cost_check[next_x+1][next_y]==0:
                cost_list[next_x+1][next_y] = max(cost_list[next_x+1][next_y], cost_list[next_x][next_y]+1)
                path_queue.append([next_x+1, next_y])
                cost_check[next_x+1][next_y] = 1

        
        if next_y+1<W:
            if path_list[next_x][next_y+1]=="." and cost_check[next_x][next_y+1]==0:
                cost_list[next_x][next_y+1] = max(cost_list[next_x][next_y+1], cost_list[next_x][next_y]+1)
                path_queue.append([next_x, next_y+1])
                cost_check[next_x][next_y+1] = 1

        
        if next_x-1>=0:
            if path_list[next_x-1][next_y]=="." and cost_check[next_x-1][next_y]==0:
                cost_list[next_x-1][next_y] = max(cost_list[next_x-1][next_y], cost_list[next_x][next_y]+1)
                path_queue.append([next_x-1, next_y])
                cost_check[next_x-1][next_y] = 1

        
        if next_y-1>=0:
            if path_list[next_x][next_y-1]=="." and cost_check[next_x][next_y-1]==0:
                cost_list[next_x][next_y-1] = max(cost_list[next_x][next_y-1], cost_list[next_x][next_y]+1)
                path_queue.append([next_x, next_y-1])
                cost_check[next_x][next_y-1] = 1

    tmp_max_cost = max(sum(cost_list,[]))
    return tmp_max_cost


for i in range(H):
    path_in = input()
    path = []
    for j in range(W):
        path.append(path_in[j])
    path_list.append(path)


for i in range(H):
    for j in range(W):
        max_cost = max(max_cost,path_cost(i, j))

print(max_cost)

Solution (Python):
from collections import deque
import itertools

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

for i in range(H):
  w = list(input())
  labyrinth[i] = w
  for j in range(W):
    if w[j] == ".":
      points.append([j,i])

com = list(itertools.combinations(points,2))


movex = [1,0,-1,0]
movey = [0,1,0,-1]

def shortest_path(sx,sy,labyrinth):
  INF = -(10 ** 6)

  x_length = W
  y_length = H
  distance = [[INF for i in range(x_length)] for j in range(y_length)]
  
  queue = deque()
  queue.append((sx,sy))
  distance[sy][sx] = 0
  
  
  def bfs():
    
    while len(queue) > 0:
      x,y = queue.popleft()

      
      for i in range(0, 4):
        nx = x + movex[i]
        ny = y + movey[i]
        
        
        if (0 <= nx and ny < y_length and 0 <= ny and nx < x_length):
          
          if (labyrinth[ny][nx] != "
            queue.append((nx,ny))
            distance[ny][nx] = distance[y][x] + 1
    
    dismax = max(list(itertools.chain.from_iterable(distance)))

    return dismax
    
  return bfs()

path = 0

for i in range(len(points)):
  sx = points[i][0]
  sy = points[i][1]
  dist = shortest_path(sx,sy,labyrinth)
  if path < dist:
    path = dist
  
print(path)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0
for i in range(h):
   for j in range(w):
      if S[i][j]=="
         continue
      else:
         DP=[[inf for _ in range(w)]for _ in range(h)]
         DP[i][j]=0
         que=deque([(i,j)])
         while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
               if 0<=ni<h and 0<=nj<w and S[ni][nj]!="
                  if DP[ni][nj]>DP[si][sj]+1:
                     DP[ni][nj]=DP[si][sj]+1
                     que.append((ni,nj))
                     ans=max(ans,DP[si][sj]+1)
print(ans)

Solution (Python):
import queue

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

ans=0
e=True
for i in range(1,H+1):
    for g in range(1,W+1):
        if c[i][g]==".":
            MAX=0
            dist=[[-1]*(W+2) for _ in range(H+2)]
            que=queue.Queue()
            que.put((i,g))
            dist[i][g]=0

            while not que.empty():
                h,w=que.get()
                direction=[(0,-1),(0,1),(1,0),(-1,0)]
                for y,x in direction:
                    if c[h+y][w+x]=="." and dist[h+y][w+x]==-1:
                        que.put((h+y,w+x))
                        dist[h+y][w+x]=dist[h][w]+1
                        MAX=max(MAX,dist[h+y][w+x])
            ans=max(MAX,ans)
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0
for i in range(h):
   for j in range(w):
      if S[i][j]=="
         continue
      else:
         D=[[inf for _ in range(w)]for _ in range(h)]
         D[i][j]=0
         que=deque([(i,j)])
         while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
               if 0<=ni<h and 0<=nj<w and S[ni][nj]!="
                  if D[ni][nj]>D[si][sj]+1:
                     D[ni][nj]=D[si][sj]+1
                     que.append((ni,nj))
                     ans=max(ans,D[si][sj]+1)
print(ans)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            visited = [[0 for _ in range(w)] for _ in range(h)]
            visited[i][j] = 1
            que = deque([])
            que.append((i, j, 0))
            while que:
                (x, y, cnt) = que.popleft()
                for (nx, ny) in (x+1,y), (x-1, y), (x, y+1), (x, y-1):
                    if 0<=nx<h and 0<=ny<w:
                        if s[nx][ny] == "." and visited[nx][ny] == 0:
                            que.append((nx, ny, cnt+1))
                            visited[nx][ny] = 1
            ans = max(ans, cnt)
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0
for i in range(h):
   for j in range(w):
      if S[i][j]=="
         continue
      else:
         D=[[inf for _ in range(w)]for _ in range(h)]
         D[i][j]=0
         que=deque([(i,j)])
         while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
               if 0<=ni<h and 0<=nj<w and S[ni][nj]!="
                  if D[ni][nj]>D[si][sj]+1:
                     D[ni][nj]=D[si][sj]+1
                     que.append((ni,nj))
                     ans=max(ans,D[si][sj]+1)
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0
for i in range(h):
   for j in range(w):
      if S[i][j]=="
         continue
      else:
         D=[[inf for _ in range(w)]for _ in range(h)]
         D[i][j]=0
         que=deque([(i,j)])
         while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
               if 0<=ni<h and 0<=nj<w and S[ni][nj]!="
                  if D[ni][nj]>D[si][sj]+1:
                     D[ni][nj]=D[si][sj]+1
                     ans=max(ans,D[si][sj]+1)
                     que.append((ni,nj))
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0
for i in range(h):
    for j in range(w):
        if S[i][j]=="
            continue
        else:
            D=[[inf for _ in range(w)]for _ in range(h)]
            D[i][j]=0
            que=deque([(i,j)])
            while que:
                si,sj=que.popleft()
                for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                    if 0<=ni<h and 0<=nj<w and S[ni][nj]!="
                        if D[ni][nj]>D[si][sj]+1:
                            D[ni][nj]=D[si][sj]+1
                            ans=max(ans,D[si][sj]+1)
                            que.append((ni,nj))
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h )]
inf=float("inf")
ans=0
for i in range(h):
    for j in range(w):
        if S[i][j]=="
            continue
        else:
            D=[[inf for _ in range(w)]for _ in range(h)]
            D[i][j]=0
            que=deque([(i,j)])
            while que:
                si,sj=que.popleft()
                for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                    if 0<=ni<h and 0<=nj<w and S[ni][nj]!="
                        if D[ni][nj]>D[si][sj]+1:
                            D[ni][nj]=D[si][sj]+1
                            ans=max(ans,D[si][sj]+1)
                            que.append((ni,nj))
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0
for i in range(h):
    for j in range(w):
        if S[i][j]=="
            continue
        else:
            D=[[inf for _ in range(w)]for _ in range(h)]
            D[i][j]=0
            que=deque([(i,j)])
            while que:
                si,sj=que.popleft()
                for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                    if 0<=ni<h and 0<=nj<w and S[ni][nj]!="
                        if D[ni][nj]>D[si][sj]+1:
                            D[ni][nj]=D[si][sj]+1
                            ans=max(ans,D[si][sj]+1)
                            que.append((ni,nj))
print(ans)

Solution (Python):
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(S, start):
    H = len(S)
    W = len(S[0])
    stack = [start]
    closed = set()
    r = 0
    while stack:
        next_stack = []
        for s in stack:
            if s in closed:
                continue
            closed.add(s)
            for d in (-1, 1):
                for p in ((s[0] + d, s[1]), (s[0], s[1] + d)):
                    if p in closed:
                        continue
                    if p[0] < 0 or H <= p[0] or p[1] < 0 or W <= p[1]:
                        continue
                    if S[p[0]][p[1]] == "
                        continue
                    next_stack.append(p)
        stack = next_stack
        r += 1
    return r - 1


def main():
    H, W = read_values()
    S = [input() for _ in range(H)]

    res = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == "
                continue
            res = max(res, f(S, (h, w)))
    print(res)

        
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
S = [input() for _ in range(h)]
inf = float("inf")
ans = 0

for i in range(h):
  for j in range(w):
    if S[i][j] == "
      continue
    D = [[inf for _ in range(w)] for _ in range(h)]
    D[i][j] = 0
    que = deque([(i, j)])
    while que:
      si, sj = que.popleft()
      for ni, nj in [(si+1, sj), (si-1, sj), (si, sj+1), (si, sj-1)]:
        if 0 <= ni < h and 0 <= nj < w and S[ni][nj] != "
          if D[ni][nj] > D[si][sj]+1:
            D[ni][nj] = D[si][sj]+1
            ans = max(ans, D[si][sj]+1)
            que.append((ni, nj))
            
print(ans)

Solution (Python):
import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("
    temp.append("
    maps2.append(temp)
maps2.append(deque(["

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            maps[i][l] = "a"
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                    maps[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    maps[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    maps[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    maps[y][x - 1] = "a"
print(MAX)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
H = H + 2
W = W + 2
grid = '
for i 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):
from collections import deque

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


"""
s_idx = [-1,-1]
g_idx = [-1,-1]

for i in range(h):
    for j in range(w):
        if s[i][j] == 'S':
            s_idx[0] = i
            s_idx[1] = j
        if s[i][j] == 'G':
            g_idx[0] = i
            g_idx[1] = j
"""

tate = [0,0,1,-1]
yoko = [-1,1,0,0]

mat=[[10**18 for i in range(w*h)] for j in range(w*h)]

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

for i in range(w*h):
    for j in range(4):
        next_idx = i + w*tate[j] + yoko[j]
        if next_idx < 0 or next_idx >= w*h:
            continue
        if i % w == 0:
            if j == 0:
                continue
        if i % w == w - 1:
            if j == 1:
                continue
        if s[next_idx//w][next_idx%w] == '
            mat[i][next_idx] = 10**18
        else:
            mat[i][next_idx] = 1

for i in range(w*h):
    
    for x in range(w*h):
        for y in range(w*h):
            """
            if x == s_idx[0]*w+s_idx[1] and y == g_idx[0]*w+g_idx[1]:
                print(mat[x][y],mat[x][i] , mat[i][y],i)
            """
            mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])
    
ans = 0
tmp = []

for i in range(w*h):
    for j in range(w*h):
        """
        下記4行がないからWA生やした
        """
        if s[i//w][i%w] == '
            continue
        if s[j//w][j%w] == '
            continue
        ans = max(ans,mat[i][j])
        
        
            
print(ans)

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


"""
s_idx = [-1,-1]
g_idx = [-1,-1]

for i in range(h):
    for j in range(w):
        if s[i][j] == 'S':
            s_idx[0] = i
            s_idx[1] = j
        if s[i][j] == 'G':
            g_idx[0] = i
            g_idx[1] = j
"""

tate = [0,0,1,-1]
yoko = [-1,1,0,0]

mat=[[10**18 for i in range(w*h)] for j in range(w*h)]

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

for i in range(w*h):
    for j in range(4):
        next_idx = i + w*tate[j] + yoko[j]
        if next_idx < 0 or next_idx >= w*h:
            continue
        if i % w == 0:
            if j == 0:
                continue
        if i % w == w - 1:
            if j == 1:
                continue
        if s[next_idx//w][next_idx%w] == '
            mat[i][next_idx] = 10**18
        else:
            mat[i][next_idx] = 1

for i in range(w*h):
    
    for x in range(w*h):
        for y in range(w*h):
            """
            if x == s_idx[0]*w+s_idx[1] and y == g_idx[0]*w+g_idx[1]:
                print(mat[x][y],mat[x][i] , mat[i][y],i)
            """
            mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])
    
ans = 10**18
tmp = []

for i in range(w*h):
    for j in range(w*h):
        if s[i//w][i%w] == '
            continue
        if s[j//w][j%w] == '
            continue
        if ans > mat[i][j]:
            tmp.append(mat[i][j])
            
print(max(tmp))

Solution (Python):
from collections import deque
H, W = map(int, input().split())


if __name__ == '__main__':

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

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

    max_path = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] != '
                que = deque([[i, j]])
                dist = [[-1 for k in range(W)] for l in range(H)]
                dist[i][j] = 0
                while len(que) != 0:
                    h, w = que[0][0], que[0][1]
                    que.popleft()
                    for k in range(4):
                        if h + dy[k] < 0 or w + dx[k] < 0 or h + dy[k] >= H or w + dx[k] >= W:
                            continue
                        if maze[h + dy[k]][w + dx[k]] == '
                            continue
                        if dist[h + dy[k]][w + dx[k]] == -1:
                            dist[h + dy[k]][w + dx[k]] = dist[h][w] + 1
                            que.append([h + dy[k], w + dx[k]])

                max_dist = max(max(li) for li in dist)
                if max_dist > max_path:
                    max_path = max_dist

    print(max_path)

Solution (Python):
from collections import deque

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

s = ["
for i in range(h):
    si = "
    s.append(si)
s.append("
nb = [(-1,0),(1,0),(0,1),(0,-1)]
inf = 10000
def bfs(x_,y_):
    dist = [[inf for i in range(w+2)] for j in range(h+2)]
    Q = deque()
    dist[x_][y_] = 0
    Q.append((x_,y_))
    while Q:
        x,y = Q.popleft()
        for u,v in nb:
            if s[x+u][y+v]!="
                if dist[x+u][y+v]>dist[x][y]+1:
                    dist[x+u][y+v]=dist[x][y]+1
                    Q.append((x+u,y+v))
    res = -1
    for i in range(h+2):
        for j in range(w+2):
            if dist[i][j]<inf:
                res = max(res,dist[i][j])
    return res
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)