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())
maze = [input() for _ in range(h)]
from collections import deque
D = [(0,1),(1,0),(-1,0),(0,-1)]
ans = 0
for i in range(h):
  for j in range(w):
    if maze[i][j]=='
      continue
    queue  = deque([(i,j,0)])
    checked = [[0 for _ in range(w)] for _ in range(h)]
    checked[i][j] = 1
    while queue:
      j,k,d = queue.popleft()
      for dx,dy in D:
        x,y = j+dx,k+dy
        if not(0<=x<h) or not(0<=y<w):
          continue
        if maze[x][y] == '
          continue
        if checked[x][y]:
          continue
        checked[x][y] = d+1
        queue.append((x,y,d+1))
    for j in range(h):
      for k in range(w):
        if checked:
          ans = max(ans,checked[j][k])

print(ans)

Solution (Python):
from collections import deque

def bfs(maze, visited, sy, sx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  
  va = 0
  while queue:
    y,x = queue.popleft()
    
    if visited[y][x] > va :
      va = visited[y][x]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        
        visited[new_y][new_x] = visited[y][x] + 1
        queue.append([new_y, new_x])
  return va

h,w = map(int,input().split())
wall = ''
for i in range(w+2):
  wall += '
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('
maze .append(wall)

ans = []
for sy in range(1,h+1) :
  for sx in range(1,w+1):
    if maze[sy][sx] == '
      continue
    visited = [[-1]*(w+2) for _ in range(h+2)]
    ans.append(bfs(maze, visited, sy, sx))

print(max(ans))

Solution (Python):
from collections import deque

def bfs(maze, visited, sy, sx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  
  va = 0
  while queue:
    y,x = queue.popleft()
    
    if visited[y][x] > va :
      va = visited[y][x]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        
        visited[new_y][new_x] = visited[y][x] + 1
        queue.append([new_y, new_x])
  return va

h,w = map(int,input().split())
wall = ''
for i in range(w+2):
  wall += '
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('
maze .append(wall)

ans = []
for sy in range(1,h+1) :
  for sx in range(1+w+1):
    if maze[sy][sx] == '
      continue
    visited = [[-1]*(w+2) for _ in range(h+2)]
    ans.append(bfs(maze, visited, sy, sx))

print(max(ans))

Solution (Python):
from collections import deque

def bfs(maze, visited, sy, sx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  va = 0
  while queue:
    y,x = queue.popleft()
    if visited[y][x] > va :
      va = visited[y][x]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        visited[new_y][new_x] = visited[y][x] + 1
        queue.append([new_y, new_x])
  return va

h,w = map(int,input().split())
wall = ''
for i in range(w+2):
  wall += '
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('
maze .append(wall)

ans = []
for sy in range(1,h+1) :
  for sx in range(1+w+1):
    if maze[sy][sx] == '
      continue
    visited = [[-1]*(w+2) for _ in range(h+2)]
    ans.append(bfs(maze, visited, sy, sx))

print(max(ans))

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
G = [[0]*(H*W) for _ in range(H*W)]
edge = []
S = [list(input()) for i in range(H)]
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] != "
        if h > 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w > 1 and S[h][w-1] == "." :
            j = h*W + w-1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1

def bfs(s) :
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for i in range(H*W) :
            if G[now][i] == 1 :
                if dist[i] != -1 :
                    continue
                else :
                    dist[i] = dist[now] + 1
                    q.append(i)
    return max(dist)

ans = 0
for i in range(H*W) :
    if S[i//W][i%W] != "
        dist = [-1 for _ in range(H*W)]
        ans = max(ans, bfs(i))

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]==".":
                  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):
from collections import deque
import copy

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



t_tmp = []
for i in range(h):
    tmp = []
    for j in range(w):
        tmp.append(s[i][j])
    t_tmp.append(tmp)

minmax = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            continue
        
        
        q = deque([(i,j,0)])

        
        t = copy.deepcopy(t_tmp)
        
        t[i][j] = '
        while q:
            x,y,c = q.popleft()
            for dx, dy in [(1,0),(0,1),(-1,0),(0,-1)]:
                
                nx, ny = x+dx, y+dy
                if 0<=nx<h and 0<=ny<w and t[nx][ny] == '.':
                    t[nx][ny] = '
                    q.append((nx,ny,c+1))

        
        minmax = max(minmax,c)

print(minmax)

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w = na()
m = nsn(h)

dist = [[inf] * (h * w) for _ in range(h * w)]
dx, dy = [0, 1, -1, 0], [1, 0, 0, -1]
for i in range(h):
    for j in range(w):
        for k in range(4):
            ni, nj = i + dy[k], j + dx[k]
            if ni >= 0 and ni < h and nj >= 0 and nj < w and m[ni][nj] != '
                dist[i * w + j][ni * w + nj] = 1
        dist[i * w + j][i * w + j] = 0

def floyd_warshall(n, dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

floyd_warshall(h * w, dist)

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

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]!='
                  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
                                          ans=max(ans,dp[si][sj]+1)
                                          que.append((ni,nj))
print(ans)

Solution (Python):
from collections import deque
INF = 5000
vx = [-1,0,1,0]
vy = [0,-1,0,1]

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

d = [-1] * (H*W)
xy = lambda x,y: x + y*W

ds = []
for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == '
        q = deque([(sx,sy)])
        tmpd = d.copy()
        tmpd[xy(sx,sy)] = 0
        while(q):
            x,y = q.popleft()
            for i in range(4):
                nx = x + vx[i]
                ny = y + vy[i]
                if 0 <= nx and nx < W and 0 <= ny and ny < H and S[ny][nx] != '
                    q.append((nx,ny))
                    tmpd[xy(nx,ny)] = tmpd[xy(x,y)] + 1
        ds.append(max(tmpd))
print(max(ds))

Solution (Python):
from collections import deque
H,W = map(int,input().split())
S = list()
for i in range(H):
    S.append(list(input()))
mx = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            continue
        q = deque([(i,j,0)])
        T = [[S[k][l] for l in range(W)] for k in range(H)]
        T[i][j] = "
        while q:
            x,y,c = q.popleft()
            for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
                nx,ny = x+dx,y+dy
                if 0 <= nx < H and 0 <= ny < W and T[nx][ny] == ".":
                    T[nx][ny] = "
                    q.append((nx,ny,c+1))
        mx = max(mx,c)
print(mx)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
INF = 1000000
def bfs(sx, sy):
    reached = [[INF for _ in range(w)] for _ in range(h)]
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    d = deque()
    d.append([sx, sy])
    reached[sx][sy] = 0
    while d:
        x, y = d.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > h - 1 or ny < 0 or ny > w - 1 or maze[nx][ny] =="
                continue
            d.append([nx, ny])
            reached[nx][ny] = reached[x][y] + 1
    
    gl = 0
    for i in range(h):
        for j in range(w):
            if reached[i][j] != INF:
                gl = max(gl, reached[i][j])
    return gl

ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] != "
            ans = max(ans, bfs(i, j))
print(ans)

Solution (Python):
from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

def bfs(sy,sx):
    res = [[-1]*(w) for i in range(h)]
    res[sy][sx] = 0
    q = deque()
    q.append([sy,sx])
    dis = 0
    while q:
        z = q.popleft()
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            ny = z[0] + dy
            nx = z[1] + dx
            if 0<=ny<h and 0<=nx<w and m[ny][nx]=="." and res[ny][nx]==-1:
                q.append([ny,nx])
                res[ny][nx] = res[z[0]][z[1]] + 1
                dis = res[ny][nx]
    return dis

ans = -1
for i in range(h):
    for j in range(w):
        if m[i][j] == ".":
            ret = bfs(i,j)
            if ret > ans:
                ans = ret
print(ans)

Solution (Python):
from collections import deque
from scipy.sparse.csgraph import floyd_warshall

def solve():
  h,w = (int(i) for i in input().split())
  maze = ["
  for i in range(h):
    maze.append("
  maze.append("

  dist = [(1,0),(0,1),(-1,0),(0,-1)]
  d = [[0]*500 for _ in range(500)]
  for y in range(1,h+1):
    for x in range(1,w+1):
      if maze[y][x] == ".":
        for dy,dx in dist:
          if maze[y+dy][x+dx] == ".":
            oldy = x + w*y
            inty = x+dx + w*(y+dy)
            d[inty][oldy] = 1
            d[oldy][inty] = 1
  ans = 0
  d = floyd_warshall(d)
  for i in range(500):
    for j in range(500):
      if d[i][j] < 10**15:
              ans = max(d[i][j],ans)
  print(int(ans))




solve()

Solution (Python):
import queue


def get_longest(s_tmx, i, j, h, w):
    q = queue.Queue()
    q.put((i, j))
    dist_mtx = [[-1] * w for a in range(h)]
    dist_mtx[i][j] = 0
    while not q.empty():
        pnt = q.get()
        y = pnt[0]
        x = pnt[1]
        if x - 1 >= 0 and dist_mtx[y][x-1] == -1 and s_mtx[y][x-1] == 1:
            dist_mtx[y][x-1] = dist_mtx[y][x] + 1
            q.put((y, x-1))
        if y - 1 >= 0 and dist_mtx[y-1][x] == -1 and s_mtx[y-1][x] == 1:
            dist_mtx[y-1][x] = dist_mtx[y][x] + 1
            q.put((y-1, x))
        if x < w - 1 and dist_mtx[y][x+1] == -1 and s_mtx[y][x+1] == 1:
            dist_mtx[y][x+1] = dist_mtx[y][x] + 1
            q.put((y, x+1))
        if y < h - 1 and dist_mtx[y+1][x] == -1 and s_mtx[y+1][x] == 1:
            dist_mtx[y+1][x] = dist_mtx[y][x] + 1
            q.put((y+1, x))
    ret = 0
    for item in dist_mtx:
        for item_item in item:
            if item_item > ret:
                ret = item_item
    return ret


h, w = map(int, input().split())
s_mtx = []

for i in range(h):
    s_list = [0] * w
    tmp = input()
    for j in range(len(tmp)):
        if tmp[j] == ".":
            s_list[j] = 1
        else:
            s_list[j] = 0
    s_mtx.append(s_list)

ret = 0

for i in range(h):
    for j in range(w):
        if s_mtx[i][j] == 1:
            tmp = get_longest(s_mtx, i, j, h, w)
            if tmp > ret:
                ret = tmp

print(ret)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

h,w = mi()
meiro = []
meiro.append("
for i in range(h):
    lis = "
    meiro.append(lis)

meiro.append("

inf = 10 **4
aa = [1,0,-1,0]
ab = [0,1,0,-1]
ans = 0

from collections import deque
for i in range(1,h+1):
    for k in range(1,w+1):
        if meiro[i][k] == "
            continue
        dp = [[inf]*(w+2) for _ in range(h+2)]
        dp[i][k] = 0
        que = deque()
        que.append((i,k,0))
        while que:
            hh, ww,num = que.popleft()
            for l in range(4):
                hnext = hh + aa[l]
                wnext = ww + ab[l]
                if meiro[hnext][wnext] != "
                    dp[hnext][wnext] = num+1
                    que.append((hnext,wnext,num+1))
        ans = max(ans,num)
print(ans)

Solution (Python):
from collections import deque


def dfs(field, s):
    MOVE = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    q = deque([(0, s)])
    dist = [[-1] * w for _ in range(h)]

    d, i, j = -1, -1, -1
    while q:
        d, (i, j) = q.popleft()
        if dist[i][j] != -1:
            continue
        dist[i][j] = d
        for di, dj in MOVE:
            ni, nj = i + di, j + dj
            if not 0 <= ni < h or not 0 <= nj < w:
                continue
            if field[ni][nj] == '
                continue
            if dist[ni][nj] != -1:  
                continue
            q.append((d + 1, (ni, nj)))
    return d, i, j


h, w = map(int, input().split())
field = [input() for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            d, i, j = dfs(field, (i, j))
            ans = max(ans, d)
print(ans)

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

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




def bfs(maze, visited, sy, sx):

    visited[sy][sx] = 0
    
    
    queue = deque([[sy, sx]])

    while queue:
        y, x = queue.popleft()
        for dy, dx in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            ny, nx = y + dy, x + dx
            if 0 <= ny < H and 0 <= nx < W and \
                    maze[ny][nx] == "." and visited[ny][nx] == -1:
                visited[ny][nx] = visited[y][x] + 1
                queue.append([ny, nx])

    return np.amax(visited)

ans = -1
for i in range(H):
    for j in range(W):
        sy, sx = i, j
        
        visited = [[-1] * W for _ in range(H)]
        if maze[sy][sx] == '.':
            ans = max(ans, bfs(maze, visited, sy, sx))

print(ans)

Solution (Python):




import numpy as np
from collections import Counter, deque


def resolve():
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    def bfs(maze, visited, sy, sx):
        queue = deque([[sy, sx]])

        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            for dy, dx in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y + dy, x + dx
                if 0<=ny<H and 0<=nx<W and \
                        maze[ny][nx] == "." and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append([ny, nx])
        return np.amax(visited)

    ans=-1
    for i in range(H):
        for j in range(W):
            visited = [[-1] * W for _ in range(H)]

            sy,sx=i,j
            if maze[sy][sx]=='.':
                ans = max(ans,bfs(maze, visited, sy, sx))


    print(ans)
resolve()

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

maze = [['
for i in range(H):
    maze.append(list('
maze.append(['
ans = 0

for ii in range(1,H+1):
    for jj in range(1,W+1):
        if maze[ii][jj]=='
        temp = deque()
        temp.append([ii,jj])
        mazenum = [[0]*(W+2) for _ in range(H+2)]
        mazenum[ii][jj] = 0
        visited = [[False]*(W+2) for _ in range(H+2)]
        visited[ii][jj] = True


        while temp:
            p = temp.popleft()
            m = mazenum[p[0]][p[1]]
            for i, j in [[p[0]-1,p[1]], [p[0]+1, p[1]], [p[0],p[1]-1],[p[0],p[1]+1]]:
                if maze[i][j]=='.':
                    if not visited[i][j]:
                        temp.append([i, j])
                        mazenum[i][j] = m + 1
                        visited[i][j]= True        
        ans = max(ans, max(max(x) for x in mazenum))

print(ans)

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

from collections import deque

def bfs(sy, sx):
    q = deque([[sy, sx]])
    visited = [[-1]*W for _ in range(H)]
    visited[sy][sx] = 0
    while q:
        y, x = q.popleft()
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+i, x+j
            if not 0 <= new_y < H or not 0 <= new_x < W:
                continue
            if S[new_y][new_x] ==  "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x]+1
                q.append([new_y, new_x])
    return max(max(l) for l in visited)

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

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '
                continue
            dist = [[-1] * W for _ in range(H)]
            dist[h][w] = 0
            Q = deque([(h,w)])
            while Q:
                y, x = Q.popleft()
                for i in range(4):
                    nh = y + dh[i]
                    nw = x + dw[i]
                    if 0 <= nh < H and 0 <= nw < W and dist[nh][nw] == -1 and S[nh][nw] == '.':
                        dist[nh][nw] = dist[y][x] + 1
                        Q.append((nh,nw))
            for i in range(H):
                ans = max(ans, max(dist[i]))
                
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
import queue
 
H, W = map(int,input().split())
MAP = []
INF = 10 ** 8
x = 0
y = 1
dx = [1,0,-1,0]
dy = [0,1,0,-1]
 
 
for _ in range(H):
    MAP.append(list(input()))
 
def bfs(S):
    que = queue.Queue()
    d = [[INF for i in range(W)] for j in range(H)]
    que.put(S)
    d[S[x]][S[y]] = 0
    
    while not que.empty():
        p = que.get()
        for i in range(4):
            nx = p[x] + dx[i]
            ny = p[y] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] != "
                que.put([nx,ny])
                d[nx][ny] = d[p[x]][p[y]] + 1
    
    MAX = -1
    for i in range(H):
        for j in range(W):
            if d[i][j] != INF and MAX < d[i][j]:
                MAX = d[i][j]
    return MAX

ans = -1

for i in range(H):
    for j in range(W):
        if MAP[i][j] != "
            tmp = bfs([i,j])
            if ans < tmp:
                ans = tmp

print(ans)

Solution (Python):


import queue

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

def bfs(h, w):
    q = queue.Queue()
    q.put((h, w, 0))
    f = [[False] * W for _ in range(H)]
    f[h][w] = True
    max_d = 0
    while q.qsize() > 0:
        h, w, d = q.get()
        max_d = max(max_d, d)
        for dh, dw in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            if h + dh >= 0 and h + dh < H and w + dw >= 0 and w + dw < W:
                if f[h+dh][w+dw] == False and m[h+dh][w+dw] == '.':
                    q.put((h+dh, w+dw, d+1))
                    f[h+dh][w+dw] = True
    return max_d    

max_d = 0
for h in range(H):
    for w in range(W):
        if m[h][w] == '.':
            max_d = max(max_d, bfs(h, w))
        
print(max_d)

Solution (Python):
import copy
import collections
import sys


def input():
    return sys.stdin.readline()[:-1]


def bfs(sx, sy):
    
    
    que = collections.deque()
    que.append([sx, sy])
    d = [[inf]*W for _ in range(H)]
    d[sx][sy] = 0
    s = copy.copy(field)
    while (len(que) > 0):
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W and s[nx][ny] != "
                que.append([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d  


inf = -1
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
d = [[inf]*W for _ in range(H)]

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

cand = []
memo = []

for h1 in range(H):
    for w1 in range(W):
        if field[h1][w1] == '
            continue
        cand.append([h1, w1])
for c in cand:
    res = bfs(*c)
    memo.append(max(sum(res, [])))
print(max(memo))

Solution (Python):

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

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

ans = 0
for sx in range(h):
    for sy in range(w):
        if s[sx][sy] == "
            continue

        q = Queue()
        q.put((sx, sy))
        dist = [[10 ** 9] * w for _ in range(h)]
        dist[sx][sy] = 0
        while not q.empty():
            cx, cy = q.get()
            for k in range(4):
                tx = cx + dx[k]
                ty = cy + dy[k]
                if not (0 <= tx < h and 0 <= ty < w and s[tx][ty] == "."):
                    continue
                if dist[tx][ty] > dist[cx][cy] + 1:
                    dist[tx][ty] = dist[cx][cy] + 1
                    q.put((tx, ty))

        for tx in range(h):
            for ty in range(w):
                if s[tx][ty] == ".":
                    ans = max(ans, dist[tx][ty])

print(ans)

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

M = [str(input()) for _ in range(h)]
M = ['
M = ['

from collections import deque
ans = 0
for sy in range(1, h+1):
    for sx in range(1, w+1):
        if M[sy][sx] == '
            continue
        q = deque()
        q.append((sy, sx))
        visit = [[-1]*(w+2) for _ in range(h+2)]
        visit[sy][sx] = 0
        while q:
            y, x = q.popleft()
            for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
                ny, nx = y+dy, x+dx
                if visit[ny][nx] == -1 and M[ny][nx] != '
                    visit[ny][nx] = visit[y][x]+1
                    q.append((ny, nx))
        ans = max(ans, max(max(row) for row in visit))
print(ans)

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

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

def max_distance(i,j):
    not_visit = [[-1]*W for i in range(H)]
    not_visit[i][j] = 0
    stack = [(i,j)]

    while stack != []:
        y,x = stack.pop(0)
        for i in range(4):
            if 0<= x+dx[i] <W and 0<= y+dy[i] <H and S[y+dy[i]][x+dx[i]] != "
                not_visit[y+dy[i]][x+dx[i]] =  not_visit[y][x] + 1
                stack.append((y+dy[i],x+dx[i]))
    
    return not_visit[y][x]

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "
            ans = max(ans,max_distance(i,j))

print(ans)

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

def bfs(sx, sy):
    reached = [[INF for _ in range(w)] for _ in range(h)]
    reached[sx][sy] = 0
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    d = deque()
    d.append([sx, sy])

    while d:
        x, y = d.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx > h - 1 or ny < 0 or ny > w - 1 or  maze[nx][ny] == "
                continue
            d.append([nx, ny])
            reached[nx][ny] = reached[x][y] + 1
    gl = 0
    for i in range(h):
        for j in range(w):
            if reached[i][j] != INF:
                gl = max(gl, reached[i][j])
    return gl
ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] != "
            ans = max(ans, bfs(i, j))

print(ans)

Solution (Python):
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = ''.join(['
S[-1] = ''.join(['
for i in range(1,H+1):
  S[i] = '

maxd = 0
import queue
dy = [1,0,-1,0]
dx = [0,1,0,-1]
for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]=='.':
      visited = [[False]*(W+2) for _ in range(H+2)]
      q = queue.Queue()
      visited[h][w] = True
      q.put([h,w,0])
      while not q.empty():
        a,b,c = q.get()
        
        for i in range(4):
          y,x = a+dy[i], b+dx[i]
          if S[y][x]=='.' and visited[y][x]==False:
            q.put([y,x,c+1])
            visited[y][x]=True
      maxd = max(maxd,c)
print(maxd)

Solution (Python):
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]
 
edge=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
  for w in range(W):
    if maze[h][w]=='
      numcount+=1
      n+=1
      continue
    if h>0 and maze[h-1][w]=='.':
      edge[n].add(n-W)
    if h<H-1 and maze[h+1][w]=='.':
      edge[n].add(n+W)
    if w>0 and maze[h][w-1]=='.':
      edge[n].add(n-1)
    if w<W-1 and maze[h][w+1]=='.':
      edge[n].add(n+1)
    n+=1

def dfs(start):
  reach=[start]
  distance=[-1 for _ in range(H*W)]
  distance[n]=0
  while reach:
    _from=reach.pop(0)
    for _to in edge[_from]:
      if not(_to in reach) and distance[_to]==-1:
        reach.append(_to)
        distance[_to]=distance[_from]+1
  return(max(distance))
 
n=0
ans=set()
for h in range(H):
  for w in range(W):
    if maze[h][w]=='.':
      ans.add(dfs(n))
    n+=1
print(max(ans))

Solution (Python):
from collections import deque
 
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]
 
edge=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
  for w in range(W):
    if maze[h][w]=='
      numcount+=1
      n+=1
      continue
    if h>0 and maze[h-1][w]=='.':
      edge[n].add(n-W)
    if h<H-1 and maze[h+1][w]=='.':
      edge[n].add(n+W)
    if w>0 and maze[h][w-1]=='.':
      edge[n].add(n-1)
    if w<W-1 and maze[h][w+1]=='.':
      edge[n].add(n+1)
    n+=1

def dfs(start):
  reach=deque([start])
  distance=[-1 for _ in range(H*W)]
  distance[n]=0
  while reach:
    _from=reach.popleft()
    for _to in edge[_from]:
      if not(_to in reach) and distance[_to]==-1:
        reach.append(_to)
        distance[_to]=distance[_from]+1
  return(max(distance))
 
n=0
ans=set()
for h in range(H):
  for w in range(W):
    if maze[h][w]=='.':
      ans.add(dfs(n))
    n+=1
print(max(ans))

Solution (Python):
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]

point=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
  for w in range(W):
    if maze[h][w]=='
      numcount+=1
      n+=1
      continue
    if h>0 and maze[h-1][w]=='.':
      point[n].add(n-W)
    if h<H-1 and maze[h+1][w]=='.':
      point[n].add(n+W)
    if w>0 and maze[h][w-1]=='.':
      point[n].add(n-1)
    if w<W-1 and maze[h][w+1]=='.':
      point[n].add(n+1)
    n+=1

def dfs(num):
  reach=[num]
  check=[-1 for _ in range(H*W)]
  check[num]=0
  while reach:
    v=reach.pop(0)
    for e in point[v]:
      if not(e in reach) and check[e]==-1:
        reach.append(e)
        check[e]=check[v]+1
  return(max(check))

n=0
ans=set()
for h in range(H):
  for w in range(W):
    if maze[h][w]=='.':
      ans.add(dfs(n))
    n+=1
print(max(ans))

Solution (Python):
from collections import deque
h, w = map(int,input().split())
s = [input() for _ in range(h)]
result = []
for xx in range(h):
    for yy in range(w):
        if s[xx][yy]==".":
            visit = [[-1 for _ in range(w)] for __ in range(h)]
            visit[xx][yy] = 0

            q = deque([[xx,yy]])
            while q:
                x, y = q.popleft()
                for i in [-1, 1]:
                    if 0 <= x+i and x+i < h:
                        if s[x+i][y] != "
                            visit[x+i][y] = visit[x][y]+1
                            q.append([x+i, y])
                    if 0 <= y+i and y+i < w:
                        if s[x][y+i] != "
                            visit[x][y+i] = visit[x][y]+1
                            q.append([x, y+i])
            result.append(max([max(i) for i in visit]))
print(max(result))