Problem:
 Score : 400 points    Problem Statement Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i -th row from the top and the j -th column is a "wall" square if S_{ij} is # , and a "road" square if S_{ij} is . .  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.      Constraints  1 \leq H,W \leq 20  S_{ij} is . or # .  S contains at least two occurrences of . .  Any road square can be reached from any road square in zero or more moves.         Input Input is given from Standard Input in the following format:  H  W  S_{11} ... S_{1W}  :  S_{H1} ... S_{HW}       Output Print the maximum possible number of moves Aoki has to make.        Sample Input 1 3 3
...
...
...      Sample Output 1 4  If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.       Sample Input 2 3 5
...#.
.#.#.
.#...      Sample Output 2 10  If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.

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

def is_street(s, t):
    """
    道であること（壁ではないこと）を確認
    """
    return S[s][t] == '.'

def count(maze):
    """
    最大のコストを探索
    """
    r = -1
    for i in range(H):
        for j in range(W):
            r = max(r, maze[i][j])
    return r

def bfs(h, w):
    """
    h: スタート位置（高さ）
    w: スタート位置（横）
    """
    m = []  
    for i in range(H):
        s = [-1] * W
        m.append(s)
    m[h][w] = 0  

    q = [[h, w]]  
    while len(q) != 0:
        t, u = q.pop(0)
        cost = m[t][u]

        
        uh = t-1
        uw = u
        if uh >= 0 and m[uh][uw] == -1 and is_street(uh, uw):
            m[uh][uw] = cost + 1
            q.append([uh, uw])

        
        sh = t+1
        sw = u
        if sh < H and m[sh][sw] == -1 and is_street(sh, sw):
            m[sh][sw] = cost + 1
            q.append([sh, sw])

        
        lh = t
        lw = u-1
        if lw >= 0 and m[lh][lw] == -1 and is_street(lh, lw):
            m[lh][lw] = cost + 1
            q.append([lh, lw])


        rh = t
        rw = u+1
        if rw < W and m[rh][rw] == -1 and is_street(rh, rw):
            m[rh][rw] = cost + 1
            q.append([rh, rw])

    max_cost = count(m)
    return max_cost

ans = -1

for i in range(H):
    for j in range(W):
        if is_street(i, j):
            c = bfs(i, j)
            ans = max(ans, c)

print(ans)

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

def is_street(s, t):
    return S[s][t] == '.'

def count(maze):
    r = -1
    for i in range(H):
        for j in range(W):
            r = max(r, maze[i][j])
    return r

def bfs(h, w):
    m = []
    for i in range(H):
        s = [-1] * W
        m.append(s)
    m[h][w] = 0

    q = [[h, w]]
    while len(q) != 0:
        t, u = q.pop(0)
        cost = m[t][u]

        
        ue = [t-1, u]
        if ue[0] >= 0 and m[ue[0]][ue[1]] == -1 and is_street(ue[0], ue[1]):
            m[ue[0]][ue[1]] = cost + 1
            q.append(ue)

        shita = [t+1, u]
        if shita[0] < H and m[shita[0]][shita[1]] == -1 and is_street(shita[0], shita[1]) :
            m[shita[0]][shita[1]] = cost + 1
            q.append(shita)

        hidari = [t, u-1]
        if hidari[1] >= 0 and m[hidari[0]][hidari[1]] == -1 and is_street(hidari[0], hidari[1]):
            m[hidari[0]][hidari[1]] = cost + 1
            q.append(hidari)

        migi = [t, u+1]
        if migi[1] < W and m[migi[0]][migi[1]] == -1 and is_street(migi[0], migi[1]):
            m[migi[0]][migi[1]] = cost + 1
            q.append(migi)
    
    max_cost = count(m)
    return max_cost

ans = -1
for i in range(H):
    for j in range(W):
        if is_street(i, j):
            c = bfs(i, j)
            ans = max(ans, c)

print(ans)

Solution (Python):
from collections import deque

H, W = (int(x) for x in input().split())
C = [list(input()) for i in range(H)]
walk = [[1,0],[0,1],[-1,0],[0,-1]]
que = deque()
ans = -1
for sx in range(W):
    for sy in range(H):
        if C[sy][sx] == "
            continue
        dist = [[-1 for _ in range(W)] for _ in range(H)]
        
        que.append((sy,sx))
        dist[sy][sx] = 0
        while que:
            y,x = que.popleft()
            for tmp in walk:
                nx = x + tmp[0]
                ny = y + tmp[1]
                if 0 <= nx < W and 0 <= ny < H and C[ny][nx] == ".":
                    if dist[ny][nx] == -1:
                        dist[ny][nx] = dist[y][x] + 1
                        que.append((ny,nx))
        for tmp in dist:
            t = max(tmp)
            ans = max(ans,t)
print(ans)

Solution (Python):
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect
import itertools
import heapq


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(H, W, inputs):
    d_map = inputs
    best_step_num = None
    for i in range(H):
        for j in range(W):
            process_map = [[False for _ in range(W)] for _ in range(H)]
            bfs_queue = collections.deque([[i, j, 0]])
            last_step_num = None

            while len(bfs_queue) > 0:
                [y, x, step_num] = bfs_queue.pop()
                if y >= H or x >= W or y < 0 or x < 0 or d_map[y][x] == '
                    continue
                process_map[y][x] = True
                last_step_num = step_num

                bfs_queue.appendleft((y+1, x, step_num+1))
                bfs_queue.appendleft((y-1, x, step_num+1))
                bfs_queue.appendleft((y, x+1, step_num+1))
                bfs_queue.appendleft((y, x-1, step_num+1))

            if last_step_num is not None and (best_step_num is None or last_step_num > best_step_num):
                best_step_num = last_step_num
    return best_step_num


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [H, W] = string_to_int(input())
    ret = solve(H, W, inputs(H))
    print(ret)

Solution (Python):
from collections import deque

def BFS(x,y):
    dist = 1
    visited = deque()
    visited.append((x,y))
    destination = deque()
    search = [(1,0),(-1,0),(0,1),(0,-1)]
    for (dx,dy) in search:
        if maze[y+dy][x+dx] == ".":
            destination.append((x+dx,y+dy))
    same_dist = len(destination)
    moved = 0
    x = destination[0][0]
    y = destination[0][1]
    while destination:
        visited.append((x,y))
        destination.popleft()
        for (dx,dy) in search:
            if maze[y+dy][x+dx] == ".":
                if (x+dx,y+dy) not in destination and (x+dx,y+dy) not in visited:
                    destination.append((x+dx,y+dy))
        if len(destination) >= 1:
            x = destination[0][0]
            y = destination[0][1]
            moved += 1
            if moved == same_dist:
                dist += 1
                moved = 0
                same_dist = len(destination)
    return dist

H,W = map(int,input().split())
maze = [list("
ans = 0

for y in range(1,H+1):
    for x in range(1,W+1):
        if maze[y][x] == ".":
            ans = max(ans,BFS(x,y))

print(ans)

Solution (Python):
from collections import deque
import copy


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


def bfs(maze, start):
    q = deque()
    q.append((start, 0))

    max_depth = 0

    while len(q) > 0:
        p, depth = q.popleft()

        if p[0] < 0 or H <= p[0]:
            continue
        if p[1] < 0 or W <= p[1]:
            continue
        if maze[p[0]][p[1]] == "
            continue

        maze[p[0]][p[1]] = "
        max_depth = depth

        next_pos = [
            (p[0]-1, p[1]),
            (p[0]+1, p[1]),
            (p[0], p[1]-1),
            (p[0], p[1]+1),
        ]

        for pos in next_pos:
            q.append((pos, depth+1))

    return max_depth


depth = 0
for h in range(H):
    for w in range(W):
        maze = copy.deepcopy(S)
        depth = max(depth, bfs(maze, (h, w)))

print(depth)

Solution (Python):
from collections import deque

def bfs(loc):
    global tem_ans
    d = [[float('inf')] * w for i in range(h)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    que = deque([])
    que.append(loc)
    d[loc[0]][loc[1]] = 0
    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and d[nx][ny] == float('inf'):
                d[nx][ny] = d[p[0]][p[1]] + 1
                que.append([nx,ny])
                if tem_ans < d[nx][ny]:
                    tem_ans = d[nx][ny]
    return tem_ans

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

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


ans = 0
tem_ans = 0

loc = []
for i in range(h):
    for j in range(w):
        if maze[i][j] != '
            loc = [i,j]
        else:
            continue
        ans = max(ans,bfs(loc))

print(ans)

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



H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
que = deque()
ans  = -1
for sx in range(W):
    for sy in range(H): 
        if C[sy][sx] == "
            continue
        
        dist = [[-1 for _ in range(W)] for _ in range(H)]
        
        que.append((sy,sx))
        dist[sy][sx] = 0
        while que:
            y,x = que.popleft()
            for temp in go:
                gx,gy = temp
                nx = x + gx
                ny = y + gy
                if 0<= nx < W and 0<= ny < H and C[ny][nx] != "
                    if dist[ny][nx] == -1: 
                        dist[ny][nx] = dist[y][x] + 1
                        que.append( (ny,nx))
        for temp in dist:
            cand = max(temp)
            ans = max(ans,cand)
print(ans)

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

def bfs(que):
  d = 0
  while que:
    y,x = que.popleft()
    d = dist[y][x]
    for dy, dx in ((0,1),(1,0),(0,-1),(-1, 0)):
      next_y = y + dy
      next_x = x + dx
      if(0 <= next_y and next_y < h and 0 <= next_x and next_x < w and maze[next_y][next_x] != "
        que.append((next_y,next_x))
        dist[next_y][next_x] = d + 1
  return d

ans = -1
for i in range(h):
  for j in range(w):
    que = deque()
    dist = [ [-1]*w for _ in range(h) ]
    if(maze[i][j] != "
      dist[i][j] = 0
      que.append((i, j))
      ans = max([ans, bfs(que)])
print(ans)

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

Solution (Python):

dr = [0, -1, 0, 1]
dc = [1, 0, -1, 0]

def get_child(M, i, j, h, w, vis):
    child = []
    for k in range(4):
        x = i + dr[k]
        y = j + dc[k]
        if 0<= x< h and 0 <= y < w and (x, y) not in vis and M[x][y]!='
            child.append((x, y))

    return child

def bfs(M, i, j, h, w):
    vis = {(i, j): True}
    li = [(i, j, 0)]
    mx = 0
    while li:
        tp = li.pop(0)
        mx = max(mx, tp[2])
        ch = get_child(M, tp[0], tp[1], h, w, vis)
        vis.update( {}.fromkeys(ch, True) )
        
        ch = [(t[0], t[1], tp[2]+1) for t in ch]
        li.extend(ch)

    return mx
        
        
def solve(M, h, w):
    ans = 0
    for r in range(h):
        for c in range(w):
            if M[r][c]=='.':
                
                depth = bfs(M, r, c, h, w)
                ans = max(ans, depth)
    print(ans)
h, w = map(int, input().split())
Mat = []
for row in range(h):
    Mat.append(input())


solve(Mat, h, w)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)

import itertools
import queue

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


def check(x,y):
    return not(x<0 or x>H-1 or y<0 or y>W-1 or S[x][y] == "


def bfs(start):
    
    dists = [[-1 for _ in range(W)] for _ in range(H)]

    
    if not check(*start): return dists
    
    q = queue.Queue()    
    
    q.put(start)
    dists[start[0]][start[1]] = 0
    
    
    while not q.empty():
        here = q.get()
        x = here[0]
        y = here[1]

        
        dist = dists[x][y]
        
        
        if check(*here):
            
            for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
                
                if check(x+dx,y+dy) and dists[x+dx][y+dy] == -1:
                    q.put((x+dx,y+dy))
                    dists[x+dx][y+dy] = dist + 1

    return dists

ans = []
for start in itertools.product(range(H),range(W)):

    dists = bfs(start)
    ans.append(max([max(_) for _ in dists]))

print(max(ans))

Solution (Python):
from collections import deque

h, w = map(int, input().split())
s = []
for i in range(h):
    l = list(input())
    s.append(l)

q = deque()
dh = [1, 0, -1, 0]
dw = [0, 1, 0, -1]
max = 0
for i in range(h):
    for j in range(w):
        dist = [[-1 for m in range(w)] for n in range(h)]
        dist[i][j] = 0
        if s[i][j] == "
            continue
        
        q.append((i, j))
        while q:
            sh, sw = q.popleft()
            for k in range(4):
                ah = sh + dh[k]
                aw = sw + dw[k]
                
                if 0<=ah<h and 0<=aw<w:
                    if s[ah][aw] == "
                        continue

                    if dist[ah][aw] == -1:
                        q.append((ah, aw))
                        dist[ah][aw] = dist[sh][sw] + 1

                        if dist[ah][aw] > max:
                            max = dist[ah][aw]

print(max)

Solution (Python):
from  queue import Queue
r,c  = map(int,input().split() )

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

meiro = []
for i in range(r):
    meiro.append(list(input()) ) 


def kyori(x, y):
    global r
    global c
    global meiro
    global dx
    global dy
    global INF

    if (meiro[y][x] =="
        return 0

    k = [[INF for j in range (r) ] for i in range(c)]
    
    q = Queue()
    
    q.put( (x,y) )

    k[x][y] = 0
    
    mk = 0
    while True:
        if q.empty():
            break

        p = q.get()
        for i in range(4):
            nx = dx[i] + p[0]
            ny = dy[i] + p[1]
            
            if (nx < 0 or nx >= c  or
                ny < 0 or ny >= r   ):
                
                continue
            if (k[nx][ny] != INF or 
                meiro[ny][nx] == "
                
                continue
            q.put((nx, ny))
            k[nx][ny] = k[p[0]][p[1]] + 1
            mk = k[nx][ny]
            
            
    return mk

mkList = []
for y in range(r):
    for x in range(c):
        mkList.append(kyori(x, y))
        

print(max(mkList))

Solution (Python):
from collections import deque
def bfs(loc):
  global ans
  d=[[float('inf')]*w for i in range(h)]
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  que=deque([])
  que.append(loc)
  d[loc[0]][loc[1]]=0
  while que:
    p=que.popleft()
    for i in range(4):
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
      if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and d[nx][ny]==float('inf'):
        d[nx][ny]=d[p[0]][p[1]]+1
        que.append([nx,ny])
        if ans<d[nx][ny]:ans=d[nx][ny]
  return ans

h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
a=0
ans=0
loc=[]
for i in range(h):
  for j in range(w):
    if maze[i][j]!='
      loc=[i,j]
    else:continue
    a=max(a,bfs(loc))
print(a)

Solution (Python):

from collections import deque

def bfs(loc):
    global tem_ans
    d=[[float('inf')]*w for i in range(h)]

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

    que=deque([])
    que.append(loc)
    d[loc[0]][loc[1]]=0

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

            
            if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and d[nx][ny]==float('inf'):
                
                d[nx][ny]=d[p[0]][p[1]]+1
                que.append([nx,ny])

                if tem_ans<d[nx][ny]:
                    tem_ans=d[nx][ny]
    return tem_ans



h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
ans=0
tem_ans=0

loc=[]
for i in range(h):
    for j in range(w):
        
        if maze[i][j]!='
            loc=[i,j]
        else:
            continue
        ans=max(ans,bfs(loc))

print(ans)

Solution (Python):


import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy


def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z


def bfs(SS, x, y, H, W):
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" 
    for i in range(4): 
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      
      
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" 
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      
  return mlength



HW = str(input()).split()
H = int(HW[0])
W = int(HW[1])
S = [[0 for i in range(W)] for j in range(H)]

mlength = 0


for i in range(H):
  temp = str(input())
  for j in range(W):
    S[i][j]=temp[j]


for i in range(H):
  for j in range(W):
    if(S[i][j] != "
      TS = copy.deepcopy(S)
      mlength = max(mlength, bfs(TS, i, j, H, W))

print(mlength);

Solution (Python):
from collections import deque
import numpy as np

h,w = map(int,input().split())
geo = np.zeros((h,w),dtype=np.bool)
for i in range(h):
    geo[i] = [x=='.' for x in input()]
geo_i = np.ones((h,w),dtype=np.int) * -1 - (~geo)
    
res = 0

def one_step(igeo,deq,pos,h,w):
    n = igeo[pos]
    for gp in [(0,1),(0,-1),(1,0),(-1,0)]:
        cpos = pos[0]+gp[0], pos[1]+gp[1]
        if h>cpos[0]>=0 and w>cpos[1]>=0:
            if igeo[cpos] == -1:
                igeo[cpos] = n+1
                deq.append(cpos)
    return

for ih in range(h):
    for iw in range(w):
        if geo[ih,iw]:
            igeo = geo_i.copy()
            igeo[ih,iw] = 0
            deq = deque()
            deq.append((ih,iw))
            while len(deq)>0:
                pos = deq.popleft()
                one_step(igeo,deq,pos,h,w)
            res = max(res, igeo.max())
print(res)

Solution (Python):
from collections import deque

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

def bfs(sx, sy):
    ds = [[1,0], [-1,0], [0,1], [0,-1]]
    distance = [[-1 for _ in range(h)] for _ in range(w)]
    q = deque([[sx, sy]])
    distance[sx][sy] = 0

    while q:
        x, y = q.popleft()
        
        for dx, dy in ds:
            nx, ny = x+dx, y+dy
            if (nx >= 0) and (nx <= w-1) and (ny >= 0) and (ny <= h-1):
                
                if maze[ny][nx] != '
                    q.append([nx, ny])
                    distance[nx][ny] = distance[x][y] + 1
    return max(map(max, distance))

count = 0
for s_x in range(w):
    for s_y in range(h):
        if maze[s_y][s_x] == '.':
            count = max(count, bfs(s_x, s_y))

print(count)

Solution (Python):
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.state = 0
        self.cost = -1

    def __str__(self):
        return str(self.cost)

    def __repr__(self):
        return str(self.cost)


def show(points):
    for row in points:
        print(*row)


def maxp(points):
    mp = 0
    for row in points:
        for cell in row:
            mp = max(cell.cost, mp)
    return mp


h, w = map(int, input().split())
s = ["
ans = 0


for sy in range(h):
    for sx in range(w):
        p = [[Point(x, y) for x in range(w)] for y in range(h)]
        next_search = [(sx, sy)]
        p[sy][sx].cost = 0
        while next_search:
            x, y = next_search.pop(0)
            t = p[y][x]
            if t.state == -1:
                continue
            t.state = -1
            if s[y + 1][x + 1] == "
                continue
            if s[y + 1][x] == ".":
                u = p[y][x - 1]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x - 1, y))
            if s[y + 1][x + 2] == ".":
                u = p[y][x + 1]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x + 1, y))
            if s[y][x + 1] == ".":
                u = p[y - 1][x]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x, y - 1))
            if s[y + 2][x + 1] == ".":
                u = p[y + 1][x]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x, y + 1))
        ans = max(maxp(p), ans)
print(ans)

Solution (Python):
import copy
from collections import deque


def shori(d, r, max_distance):
    si, sj = d.popleft()
    next_kouho = [
        {'x': si + 1, 'y': sj},
        {'x': si - 1, 'y': sj},
        {'x': si, 'y': sj + 1},
        {'x': si, 'y': sj - 1}
    ]
    for nk in next_kouho:
        if (0 <= nk['x'] < h) and (0 <= nk['y'] < w) and (r[nk['x']][nk['y']] == '.'):
            r[nk['x']][nk['y']] = r[si][sj] + 1
            if max_distance < r[si][sj] + 1:
                max_distance = r[si][sj] + 1
            d.append((nk['x'], nk['y']))
    return d, r, max_distance


if __name__ == '__main__':
    h, w = list(map(int, input().split(" ")))
    s = []
    r = []
    for i in range(h):
        s.append(list(input()))

    d = deque()
    max_distance = 0
    
    for si in range(h):
        for sj in range(w):
            r = copy.deepcopy(s)
            if r[si][sj] == '.':
                r[si][sj] = 0
                d.append((si, sj))

                while True:
                    if len(d) == 0:
                        break
                    else:
                        d, r, max_distance = shori(d, r, max_distance)

    print(max_distance)

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

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


def bfs(i, j):
    if s[i][j] == '
        return -1
    q = deque([(i, j)])
    visited = [[-1 for _ in range(w)] for __ in range(h)]
    visited[i][j] = 0
    while q:
        v = q.popleft()
        for d in delta:
            vd1, vd2 = v[0]+d[0], v[1]+d[1]
            if 0 <= vd1 < h and 0 <= vd2 < w:
                if s[vd1][vd2] != '
                    visited[vd1][vd2] = visited[v[0]][v[1]] + 1
                    q.append((vd1, vd2))
    return max(map(max, visited))


ans = 0

for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))

print(ans)

Solution (Python):
dr = [0, -1, 0, 1]
dc = [1, 0, -1, 0]

def get_child(M, i, j, h, w, vis):
    child = []
    for k in range(4):
        x = i + dr[k]
        y = j + dc[k]
        if 0<= x< h and 0 <= y < w and (x, y) not in vis and M[x][y]!='
            child.append((x, y))

    return child

def bfs(M, i, j, h, w):
    vis = {(i, j): True}
    li = [(i, j, 0)]
    mx = 0
    while li:
        tp = li.pop(0)
        mx = max(mx, tp[2])
        ch = get_child(M, tp[0], tp[1], h, w, vis)
        vis.update( {}.fromkeys(ch, True) )
        
        ch = [(t[0], t[1], tp[2]+1) for t in ch]
        li.extend(ch)

    return mx
        
        
def solve(M, h, w):
    ans = 0
    for r in range(h):
        for c in range(w):
            if M[r][c]=='.':
                
                depth = bfs(M, r, c, h, w)
                ans = max(ans, depth)
    print(ans)
h, w = map(int, input().split())
Mat = []
for row in range(h):
    Mat.append(input())


solve(Mat, h, w)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
maze=[str(input()) for _ in range(h)]
dist=[[-1]*w for _ in range(h)]
ans=[]
for i in range(h):
    for j in range(w):
        if maze[i][j]==".":
            dist=[[-1]*w for _ in range(h)]
            dist[i][j]=0
            que=deque([(j,i)])
            while len(que):
                x,y=que.popleft()
                for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
                    nx,ny=x+dx,y+dy
                    if min(nx,ny)>=0 and nx<=w-1 and ny<=h-1:
                        if maze[ny][nx]=='.' and dist[ny][nx]<0:
                            dist[ny][nx]=dist[y][x]+1
                            que.append([nx,ny])
        m=0
        for k in range(h):
          for l in range(w):
            m=max(m,dist[k][l])
        ans.append(m)
print(max(ans))

Solution (Python):
import numpy as np
from collections import deque

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

maze = []
for h in range(H):
  s = input()
  maze.append(s)

def BFS(i,j):
  place = np.zeros((H,W))
  dist = 0
  queue = deque()
  queue.append((i,j,0))
  while queue:
    i,j,d = queue.popleft()
    if not place[i][j]:
      dist = max(dist,d)
      place[i][j] = 1
      for di,dj in [(1,0),(-1,0),(0,1),(0,-1)]:
        if (0 <= i+di and i+di < H and 0 <= j+dj and j+dj < W):
          if maze[i+di][j+dj] == '.' and place[i+di][j+dj] == 0:
            queue.append((i+di,j+dj,d+1))
  return dist

ans = 0
for h in range(H):
  for w in range(W):
    if maze[h][w] == '.':
      ans = max(ans,BFS(h,w))

print(ans)

Solution (Python):
h,w =map(int, input().split())
a =['
ans=0
for ii in range(h):
    for jj in range(w):
        if a[ii+1][jj+1]=='
            continue
        count=1
        n=[(ii+1,jj+1)]
        route={n[0]:0}
        p=[[1,0],[0,1],[-1,0],[0,-1]]
        while count != 1000:
            route2 = route.copy()
            n2=[]
            for i in n:
                for j in p:
                    np=(i[0]+j[0],i[1]+j[1])
                    if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                        n2.append(np)
                        route[np]=count
            n=n2
            count+=1
            if route == route2:
                break
        ans=max(ans,max(route.values()))
        
print(ans)

Solution (Python):

import numpy as np
from collections import deque

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


def bfs(x,y):
    visited = np.zeros((H,W))
    dist = 0
    queue = deque()
    queue.append((x,y,0))
    while(queue):
        x,y,d = queue.popleft()
        if not visited[x][y]:
            dist = max(dist, d)
            visited[x][y] = 1
            for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
                if (0 <= x+dx and x+dx < H and 0 <= y+dy and y+dy < W):
                    if maze[x+dx][y+dy] == '.' and visited[x+dx][y+dy] == 0:
                        queue.append((x+dx, y+dy, d+1))
    return dist

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

print (ans)

Solution (Python):

def solve_maze(sx, sy, maze):
    distance = [[None for _ in range(w)] for _ in range(h)]
    queue = [(sx, sy)]
    distance[sy][sx] = 0
    max_distance = 0

    while queue:
        x, y = queue.pop()

        for i in range(4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            try:
                if (0 <= nx <= w and 0 <= ny <= h and maze[ny][nx] == "." and distance[ny][nx] is None):
                    queue.insert(0, (nx, ny))
                    dis = distance[y][x] + 1
                    distance[ny][nx] = dis
                    max_distance = max(max_distance, dis)
            except IndexError:
                pass

    return max_distance
    

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

result = 0
for j in range(h):
    for k in range(w):
        if maze[j][k] == ".":
            result = max(result, solve_maze(k, j, maze))

print(result)

Solution (Python):

import numpy as np
iH, iW = map(int, input().split())
naAll = np.zeros((iH+2, iW+2), dtype=int) - 1

iID0 = 0
for iH0 in range(iH):
  s = input()
  for i, s0 in enumerate(s):
    if s0 == ".":
      naAll[iH0+1, i+1] = iID0
      iID0 += 1
lMaze = [[] for _ in range(iID0)]

for iH0 in range(iH):
  for iW0 in range(iW):
    if naAll[iH0+1, iW0+1] >= 0:
      iID = naAll[iH0 + 1, iW0 + 1]
      if naAll[iH0 + 2, iW0 + 1] >= 0:
        lMaze[iID].append(naAll[iH0 + 2, iW0 + 1])
      if naAll[iH0 + 1, iW0 + 2] >= 0:
        lMaze[iID].append(naAll[iH0 + 1, iW0 + 2])
      if naAll[iH0    , iW0 + 1] >= 0:
        lMaze[iID].append(naAll[iH0    , iW0 + 1])
      if naAll[iH0 + 1, iW0    ] >= 0:
        lMaze[iID].append(naAll[iH0 + 1, iW0    ])
      
      
      
      
      
      
lMax = []
for iID in range(iID0):
  lState = [0]*iID0
  lState[iID] = 1
  lMazeNow = [lMaze[iID]]
  iPre        = 1
  iTime       = 0
  while iPre < iID0:
    lMazeNow0 = []
    for lMazeNext in lMazeNow :
      for iIDnext in lMazeNext:
        if lState[iIDnext] == 0:
          lState[iIDnext] = 1
          iPre += 1
          lMazeNow0.append(lMaze[iIDnext])
    lMazeNow = lMazeNow0
    iTime += 1
    
  lMax.append(iTime)
print(max(lMax))

Solution (Python):
from collections import deque

d=[(1,0),(0,1),(-1,0),(0,-1)]
H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dist = [[-1]*W for _ in range(H)]
def BFS(i,j):
    q = deque()
    dist = [[-1]*W for _ in range(H)]
    if M[i][j] == '.':

        
        Ma = 0
        q.append((i, j))
        dist[i][j] = 0
        while q:
            cx,cy = q.popleft()
            for nx,ny in d:
                x ,y= cx+nx,cy+ny
                if 0<= x < H and 0<= y < W and M[x][y] == "." and dist[x][y]==-1:
                    dist[x][y]=dist[cx][cy]+1
                    Ma = max(Ma,dist[x][y])
                    q.append((x,y))
        return Ma
    return 0
for i in range(H):
    for j in range(W):
        Max_list.append(BFS(i,j))

print(max(Max_list))