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):

"""
@author: H_Hoshigi
"""
def main():
    H, W = map(int, input().split())
    S_lsit = [input() for i in range(H)]

    INF = 401

    node_list = []
    for i in range(H):
        node_list += [(i, j) for j in range(W)]

    dist_table = [[INF for j in range(H*W)] for i in range(H*W)]
    for i in range(H*W):
        dist_table[i][i] = 0
    

    path_list = [[] for i in range(H*W)]
    for k in range(H*W):
        node = node_list[k]
        i, j = node[0], node[1]
        if i >= 1 and S_lsit[i-1][j] == ".":
            path_list[k].append((i-1)*W + j)
        if i <= H-2 and S_lsit[i+1][j] == ".":
            path_list[k].append((i+1)*W + j)
        if j >= 1 and S_lsit[i][j-1] == ".":
            path_list[k].append(i*W + j-1)
        if j <= W-2 and S_lsit[i][j+1] == ".":
            path_list[k].append(i*W + j+1)
        for next_node in path_list[k]:
            dist_table[k][next_node] = 1
    

    for k in range(H*W):
        for i in range(H*W):
            for j in range(H*W):
                dist_table[i][j] = min(
                    dist_table[i][j],
                    dist_table[i][k] + dist_table[k][j]
                )
    

    max_dist = 0
    for i in range(H*W):
        if S_lsit[i//W][i%W] == ".":
            for j in range(H*W):
                if S_lsit[j//W][j%W] == ".":
                    max_dist = max(max_dist, dist_table[i][j])
    print(max_dist)

if __name__ == "__main__":
    main()

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

queue = []
visited = [] 
visited = [[0 for i in range(w)] for i in range(h)]
ans = 0

for i in range(h):
    for j in range(w):
        if C[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

            while len(queue) > 0:
                now = queue.pop(0)
                for k in range(4):
                    y = now[0]+dy_dx[k][0]
                    x = now[1]+dy_dx[k][1]
                    if 0 <= y < h and 0 <= x < w:
                        if C[y][x] != '
                            visited[y][x] = visited[now[0]][now[1]]+1 
                            queue.append([y,x])
                    
        for l in range(h):
            for m in range(w):
                ans = max(ans,visited[l][m])
            
        queue = []
        visited = [[0 for i in range(w)] for i in range(h)]              
        
print(ans-1)

Solution (Python):
import sys
from collections import deque

def main():
    h, w = map(int, input().split())
    maze = [input() for i in range(h)]
    
    visited = [[-1]*w for j in range(h)]
    start_yx = []
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                sy = i
                sx = j
                start_yx .append([sy, sx])

    
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    ans = 0
    for sy, sx in start_yx :
        visited = [[-1]*w for j in range(h)]
        q = deque([[sy, sx]])
        visited[sy][sx] = 0 
        while q:
            y, x = q.popleft()
            ans = max(ans, visited[y][x])
            for i, j in mv:
                if (0 <= y + i < h) and (0 <= x + j < w):  
                    ny = y+i
                    nx = x+j
                    if visited[ny][nx] != -1:
                        continue
                    if maze[ny][nx] == '.':
                        visited[ny][nx] = visited[y][x] + 1 
                        q.append([ny, nx])
                else:
                    continue
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    field = "
    field += "
    field += "

    INF = 10**9
    cost = [INF]*len(field)
    move = [-1, 1, -(W+2), W+2]
    def bfs(s, g):
        q = deque()
        dequeue = q.popleft
        enqueue = q.append
        cost[s] = 0
        enqueue(s)

        while q:
            now = dequeue()
            now_cost = cost[now]
            for dx in move:
                nv = now + dx
                if nv == g:
                    cost[g] = now_cost + 1
                    return
                if field[nv] == "
                    continue
                else:
                    cost[nv] = now_cost + 1
                    q.append(nv)
    
    ans = 0
    for si in range(H):
        for sj in range(W):
            for gi in range(H):
                for gj in range(W):
                    start = (si+1)*(W+2)+sj+1
                    goal = (gi+1)*(W+2)+gj+1
                    if field[start] == "
                        continue
                    cost = [INF] * len(field)
                    bfs(start, goal)
                    ans = max(ans, cost[goal])
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

H,W = map(int,input().split())
S = [input().rstrip() for _ in range(H)]
ans = 0
for hi in range(H):
    for wi in range(W):
        flag = 0
        if S[hi][wi] =='.':
            flag = 1
            tmp = [hi,wi]
    
            cost = [[-1]*W for _ in range(H)]
            q = collections.deque([tmp])
            cost[tmp[0]][tmp[1]] = 0
            while q:
                now = q.popleft()
                if 0<= now[0]+1 < H:
                    if cost[now[0]+1][now[1]] == -1 and S[now[0]+1][now[1]] =='.':
                        cost[now[0]+1][now[1]] = cost[now[0]][now[1]] +1
                        q.append([now[0]+1,now[1]])

                if 0<= now[0]-1 < H:
                    if cost[now[0]-1][now[1]] == -1 and S[now[0]-1][now[1]] =='.':
                        cost[now[0]-1][now[1]] = cost[now[0]][now[1]] +1
                        q.append([now[0]-1,now[1]])

                if 0<=now[1]+1 < W:
                    if cost[now[0]][now[1]+1] == -1 and S[now[0]][now[1]+1] =='.':
                        cost[now[0]][now[1]+1] = cost[now[0]][now[1]] +1
                        q.append([now[0],now[1]+1])

                if 0<=now[1]-1 < W:
                    if cost[now[0]][now[1]-1] == -1 and S[now[0]][now[1]-1] =='.':
                        cost[now[0]][now[1]-1] = cost[now[0]][now[1]] +1
                        q.append([now[0],now[1]-1])

            ans = max(ans,cost[now[0]][now[1]])

            cost = [[-1]*W for _ in range(H)]
            q = collections.deque([tmp])
            cost[now[0]][now[1]] = 0
            while q:
                now = q.popleft()
                if 0<= now[0]+1 < H:
                    if cost[now[0]+1][now[1]] == -1 and S[now[0]+1][now[1]] =='.':
                        cost[now[0]+1][now[1]] = cost[now[0]][now[1]] +1
                        q.append([now[0]+1,now[1]])

                if 0<= now[0]-1 < H:
                    if cost[now[0]-1][now[1]] == -1 and S[now[0]-1][now[1]] =='.':
                        cost[now[0]-1][now[1]] = cost[now[0]][now[1]] +1
                        q.append([now[0]-1,now[1]])

                if 0<=now[1]+1 < W:
                    if cost[now[0]][now[1]+1] == -1 and S[now[0]][now[1]+1] =='.':
                        cost[now[0]][now[1]+1] = cost[now[0]][now[1]] +1
                        q.append([now[0],now[1]+1])

                if 0<=now[1]-1 < W:
                    if cost[now[0]][now[1]-1] == -1 and S[now[0]][now[1]-1] =='.':
                        cost[now[0]][now[1]-1] = cost[now[0]][now[1]] +1
                        q.append([now[0],now[1]-1])
            
    if flag == 1:
        ans = max(ans,cost[now[0]][now[1]])
        
print(ans)

Solution (Python):
h,w = list(map(int,input().split()))
h += 2
w += 2
grid = '
for _ in range(h-2):
    grid += '
grid += '

from collections import deque
ans = 0
for i in range(len(grid)):
    INF = 10**9
    dist = [INF]*(h*w)
    if grid[i]=='
        continue
    dist[i] = 0
    q = deque([i])
    while q:
        v = q.popleft()
        dv = dist[v]
        for m in (-1,1,w,-w):
            move = v + m
            if grid[move]=='
                continue
            dmove = dv + 1
            if dmove >= dist[move]:
                continue
            dist[move] = dmove
            q.append(move)
    
    ans = max(ans, max([dist[i] if dist[i]!=INF else 0 for i in range(len(dist))]))
    
    
print(ans)

Solution (Python):
from collections import deque

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

dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
           
def bfs(sx, sy):
    q = deque([])
    d = [[-1 for _ in range(W)] for _ in range(H)]
    q.append([sx, sy])
    d[sx][sy] = 0
    
    while(q):
        pop = q.popleft()
        x, y = pop[0], pop[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < H and ny >= 0 and ny < W:
                if s[nx][ny] != "
                    q.append([nx, ny])
                    d[nx][ny] = d[x][y] + 1
    return d

def max_dim2(d):
    ret = 0
    for i in range(len(d)):
        for j in d[i]:
            ret = max(ret, j)
    return ret

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

Solution (Python):



def main():
    from collections import deque

    dd = 0, 1, 0, -1

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

    def dist(sr, sc):
        if G[sr][sc] == '
            return -1

        memo = [[-1] * W for _ in range(H)]

        dq = deque()
        dq.append((sr, sc, 0))
        memo[sr][sc] = 0
        while dq:
            r, c, d = dq.popleft()
            nd = d + 1
            for i in range(4):
                nr = r + dd[i]
                nc = c + dd[i ^ 1]
                if not (0 <= nr < H and 0 <= nc < W):
                    continue
                if ~memo[nr][nc]:
                    continue
                if G[nr][nc] == '
                    continue
                dq.append((nr, nc, nd))
                memo[nr][nc] = nd

        return d

    ans = 0
    for sr in range(H):
        for sc in range(W):
            ans = max(ans, dist(sr, sc))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

s = []

for i in range(h):
    s.append(list(input()))


def bfs(x, y):
    if s[y][x] == '
        return 0

    queue = deque()
    queue.appendleft([x, y])
    visited = dict()
    visited[(x, y)] = 0

    while queue:
        nx, ny = queue.pop()
        cur = visited[(nx, ny)]

        if nx - 1 >= 0 and (nx - 1, ny) not in visited:
            if s[ny][nx - 1] == '.':
                visited[(nx - 1, ny)] = cur + 1
                queue.appendleft((nx - 1, ny))

        if nx + 1 < w and (nx + 1, ny) not in visited:
            if s[ny][nx + 1] == '.':
                visited[(nx + 1, ny)] = cur + 1
                queue.appendleft((nx + 1, ny))

        if ny - 1 >= 0 and (nx, ny - 1) not in visited:
            if s[ny - 1][nx] == '.':
                visited[(nx, ny - 1)] = cur + 1
                queue.appendleft((nx, ny - 1))

        if ny + 1 < h and (nx, ny + 1) not in visited:
            if s[ny + 1][nx] == '.':
                visited[(nx, ny + 1)] = cur + 1
                queue.appendleft((nx, ny + 1))

    return max(visited.values())


result = 0
for i in range(h):
    for j in range(w):
        r = bfs(j, i)
        result = max(result, r)

print(result)

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    is_visited[start[0]][start[1]] = 1

    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '
        return
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (is_visited[next_h][next_w] == 1) or \
           M[next_h][next_w] == '
           
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        is_visited[next_h][next_w] = 1

        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

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

  print(max_)


if(__name__ == '__main__'):
  main()

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '
        return
      
      is_visited[now_h][now_w] = float('inf')
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '
           
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

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

  print(max_)


if(__name__ == '__main__'):
  main()

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '
        return
      is_visited[now_h][now_w] = 1
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '
           
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

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

  print(max_)


if(__name__ == '__main__'):
  main()

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '
        return
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '
          continue

        
        
        
        
        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

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

  print(max_)


if(__name__ == '__main__'):
  main()

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '
        return
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '
          continue

        temp = dist[now_h][now_w] + 1
        dist[next_h][next_w] = temp
        if max_ < temp:
          max_ = temp
        q.append((next_h, next_w))
    return max_

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

  print(max_)


if(__name__ == '__main__'):
  main()

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '
          continue

        temp = dist[now_h][now_w] + 1
        dist[next_h][next_w] = temp
        if max_ < temp:
          max_ = temp
        q.append((next_h, next_w))
    return max_

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

  print(max_)


if(__name__ == '__main__'):
  main()

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

def bfs(s):
    que = deque([s])
    m = [[-1]*w for _ in range(h)]
    sh, sw = s
    m[sh][sw] = 0
    ret = 0
    while que:
        now_h, now_w = que.popleft()
        for dh, dw in [(1,0), (-1,0), (0,-1), (0,1)]:
            nh = now_h + dh
            nw = now_w + dw
            if not (0<=nh<h and 0<=nw<w) or m[nh][nw] != -1 or hw[nh][nw] == '
                continue
            m[nh][nw] = m[now_h][now_w] + 1
            que.append((nh,nw))
            ret = max(ret, m[now_h][now_w] + 1)
    return ret

ans = 0
for y in range(h):
    for x in range(w):
        if hw[y][x] == '
            continue
        s = (y, x)
        ans = max(bfs(s), ans)

print(ans)

Solution (Python):
from collections import deque

def BFS(s):
  q = deque()
  q.append(s)
  dist = [[10**10]*(W+2) for _ in range(H+2)]
  dist[s[0]][s[1]] = 0
  d = ((0,1),(0,-1),(1,0),(-1,0))
  far = []
  
  while len(q)>0:
    i,j = q.popleft()
    for di,dj in d:
      if field[i+di][j+dj] == "." and dist[i+di][j+dj] == 10**10:
        q.append([i+di,j+dj])
        dist[i+di][j+dj] = dist[i][j]+1
    res = dist[i][j]
  
  return res



H,W = map(int,input().split())
field = ["
field += ["
field += ["
res = 0

for i in range(H+2):
  for j in range(W+2):
    if field[i][j] == ".":
      s = [i,j]
      res = max(res,BFS(s))
      
print(res)

Solution (Python):
import sys
from copy import deepcopy
from itertools import combinations_with_replacement, product
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    ans = 0
    for H, W in product(range(h), range(w)):
        if s[H][W] == '
            continue
        s2 = deepcopy(s)
        s2[H][W] = 0
        d = deque()
        d.append([H, W])
        while d:
            Hn,Wn = d.popleft()
            for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                if ((0 <= Hn+i < h) and (0 <= Wn+j < w)):
                    
                    if s2[Hn+i][Wn+j] != '.':
                        continue
                    s2[Hn+i][Wn+j] = s2[Hn][Wn] + 1
                    d.append([Hn+i, Wn+j])
                    if ans < s2[Hn+i][Wn+j]:
                        ans = s2[Hn+i][Wn+j]
        del s2

    print(ans)


if __name__ == '__main__':
    main()

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

queue = []
visited = []
visited = [[0 for _ in range(W)] for _ in range(H)]
ans = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            while len(queue) > 0:
                now_y, now_x = map(int,queue.pop(0))
                for next_x, next_y in [(1,0),(0,1),(-1,0),(0,-1)]:
                    y = now_y + next_y
                    x = now_x + next_x
                    if 0 <= y < H and 0 <= x < W:
                        if maze[y][x] != '
                            visited[y][x] = visited[now_y][now_x] + 1
                            queue.append([y,x])

        for l in range(H):
            for m in range(W):
                ans = max(ans,visited[l][m])

        queue = []
        visited = [[0 for _ in range(W)] for _ in range(H)]



print(ans-1)

Solution (Python):
from collections import deque
INFTY = 10**3
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
cmax = 0
for x in range(H):
    for y in range(W):
        if S[x][y]==".":
            A = [[INFTY for _ in range(W)] for _ in range(H)]
            hist = {(i,j):0 for i in range(H) for j in range(W)}
            que = deque([(x,y,0)])
            A[x][y] = 0
            hist[(x,y)] = 1
            while que:
                i,j,d = que.popleft()
                if j+1<W and S[i][j+1]=="." and hist[(i,j+1)]==0:
                    A[i][j+1]=d+1
                    hist[(i,j+1)]=1
                    que.append((i,j+1,d+1))
                if i-1>=0 and S[i-1][j]=="." and hist[(i-1,j)]==0:
                    A[i-1][j]=d+1
                    hist[(i-1,j)]=1
                    que.append((i-1,j,d+1))
                if j-1>=0 and S[i][j-1]=="." and hist[(i,j-1)]==0:
                    A[i][j-1]=d+1
                    hist[(i,j-1)]=1
                    que.append((i,j-1,d+1))
                if i+1<H and S[i+1][j]=="." and hist[(i+1,j)]==0:
                    A[i+1][j]=d+1
                    hist[(i+1,j)]=1
                    que.append((i+1,j,d+1))
            cnt=0
            for i in range(H):
                for j in range(W):
                    if S[i][j]==".":
                        cnt = max(cnt,A[i][j])
            cmax = max(cmax,cnt)
print(cmax)

Solution (Python):
from collections import deque
def bfs(y,x):
  q=deque([(y,x)])
  visited[y][x]=0
  while q:
    cy,cx=q.popleft()
    for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
      ny,nx=cy+dy,cx+dx
      if 0<=ny<h and 0<=nx<w and visited[ny][nx]==-1:
        if s[ny][nx]=="
        visited[ny][nx]=visited[cy][cx]+1
        q.append((ny,nx))
  res=0
  for i in range(h):
    for j in range(w):
      if s[i][j]!="
        res=max(res,visited[i][j])
  return res

h,w=map(int,input().split())
s=[input() for _ in range(h)]
ans=0
for i in range(h):
  for j in range(w):
    if s[i][j]=="
    sh=i
    sw=j
    visited=[[-1]*w for _ in range(h)]
    ans=max(ans,bfs(sh,sw))
print(ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
XY = [(-1, 0), (1, 0), (0, 1), (0, -1)]

t_max = 0
for i in range(H):
    for j in range(W):
        step = [[0]*W for _ in range(H)]
        visited = [[False]*W for _ in range(H)]
        queue = deque([(i, j)])
        while queue:
            x, y = queue.popleft()
            if maze[x][y] == "
                continue
            if visited[x][y]:
                continue
            for dx, dy in XY:
                nx = x + dx
                ny = y + dy
                if 0 <= nx <= H-1 and 0 <= ny <= W-1:
                    step[nx][ny] = step[x][y] + 1
                    queue.append((nx, ny))
                    t_max = max(t_max, step[nx][ny])
            visited[x][y] = True

print(t_max-1)

Solution (Python):
h,w=map(int,input().split())
s=[]
import heapq
INF=10**9
def Dijkstra(graph, start):
  dist=[INF]*len(graph)
  parent=[INF]*len(graph)
  queue=[(0, start)]
  while queue:
    path_len, v=heapq.heappop(queue)
    if dist[v]==INF: 
      dist[v]=path_len
      for w in graph[v]:
        if dist[w[0]]==INF:
          parent[w[0]]=v
          heapq.heappush(queue, (dist[v]+w[1], w[0]))         
  return (dist,parent)
for i in range(h):
  a=input()
  s.append(a)
graph=[]
ans=0
for i in range(h):
  for j in range(w):
    graph.append([])
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      if i>0 and s[i-1][j]=='.':
        graph[i*w+j].append([(i-1)*w+j,1])
      if i<h-1 and s[i+1][j]=='.':
        graph[i*w+j].append([(i+1)*w+j,1])
      if j>0 and s[i][j-1]=='.':
        graph[i*w+j].append([i*w+j-1,1])
      if j<w-1 and s[i][j+1]=='.':
        graph[i*w+j].append([i*w+j+1,1])
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      a,b=Dijkstra(graph,i*w+j)
      for k in range(h):
        for l in range(w):
          if a[k*w+l]!=INF:
            ans=max(ans,a[k*w+l])
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
from collections import deque
query = [list(input()) for _ in range(H)]
dirc = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def bfs(start):
    Q = deque([start])
    checked = [[0]*W for _ in range(H)]
    checked[start[0]][start[1]] = 1
    dist = [[0]*W for _ in range(H)]
    ret = 0
    while Q:
        y, x = Q.popleft()
        ret = max(ret, dist[y][x])
        for dy, dx in dirc:
            ny, nx = y+dy, x+dx
            if ny>=H or ny<0 or nx>=W or nx<0: continue
            if query[ny][nx]=='
            if checked[ny][nx]: continue
            checked[ny][nx] = 1
            dist[ny][nx] = dist[y][x]+1
            Q.append((ny, nx))
    return ret

ans = 0
for h in range(H):
    for w in range(W):
        if query[h][w]=='
        ans = max(ans, bfs((h, w)))

print(ans)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
INF = 10**5
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='
            continue
        q = deque([(i, j)])
        dist = [[INF]*w for _ in range(h)]
        dist[i][j] = 0
        while q:
            y, x = q.popleft()
            for dx, dy in dxdy:
                if not (0<=x+dx<w and 0<=y+dy<h):
                    continue
                if s[y+dy][x+dx]=='
                    continue
                dist[y+dy][x+dx] = dist[y][x] + 1
                q.append((y+dy, x+dx))
        for row in dist:
            for ele in row:
                if ele==INF:
                    continue
                ans = max(ans, ele)
print(ans)

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

dp = [[10**6]*(H*W) for _ in range(H*W)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            continue
        p = W*i+j
        if i > 0 and S[i-1][j] == ".":
            dp[p][p-W] = 1
            dp[p-W][p] = 1
        if i < H-1 and S[i+1][j] == ".":
            dp[p][p+W] = 1
            dp[p+W][p] = 1
        if j > 0 and S[i][j-1] == ".":
            dp[p][p-1] = 1
            dp[p-1][p] = 1
        if j < W-1 and S[i][j+1] == ".":
            dp[p][p+1] = 1
            dp[p+1][p] = 1

for i in range(H*W):
    dp[i][i] = 0
for k in range(H*W):
    for i in range(H*W):
        for j in range(H*W):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

ans = 0
for i in range(H*W):
    for j in range(H*W):
        if dp[i][j] == 10**6:
            continue
        ans = max(ans, dp[i][j])
            
print(ans)

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

def bfs(sy, sx):
    mx=0
    q=Queue()
    dist=[[-1]*W for _ in range(H)]
    q.put((sy,sx))
    dist[sy][sx]=0
    while not q.empty():
        y, x=q.get()
        y_nxt=[y+1, y-1, y, y]
        x_nxt=[x, x, x+1, x-1]
        for Y,X in zip(y_nxt, x_nxt):
            if not (0 <= Y < H) or not (0 <= X < W) or S[Y][X]=="
                continue
            if dist[Y][X]==-1:
                dist[Y][X]=dist[y][x]+1
                q.put((Y, X))
                mx=max(mx, dist[Y][X])
    return mx

mx=0
for y in range(H):
    for x in range(W):
        if S[y][x]=="
            continue
        else:
            mx=max(bfs(y,x),mx)

print(mx)