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

Solution (Python):
from collections import deque
import numpy as np
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 = np.array([np.array([-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(visit.flatten()))
print(max(result))

Solution (Python):
from collections import deque

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


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



def bfs(x,y):
    seen = [[False for _ in range(w)] for _ in range(h)]
    dist = [[False for _ in range(w)] for _ in range(h)]
    
    if(maze[y][x] == "
        return [[0]]
    
    dist[y][x] = 0
    d = deque()
    d.append(x + w*y)
    
    while d:
        
        base = d.popleft()
        
        xx = base%w
        yy = base//w
        
        
        if(seen[yy][xx] == True):
            continue
        else:
            seen[yy][xx] = True
        
        for px,py in [(-1,0),(1,0),(0,-1),(0,1)]:
            
            if (0<= xx+px < w and 0<= yy+py < h):
                if(maze[yy+py][xx+px] == "." and seen[yy+py][xx+px] == False):
                    d.append(xx+px+(yy+py)*w)
                    dist[yy+py][xx+px] = dist[yy][xx] + 1
    
    return dist




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


print(ans)

Solution (Python):
from copy import deepcopy
H, W = map(int, input().split())
spots = []
dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
maze = []
for h in range(H):
  line = list(input())
  maze.append(line)
res = 0
for h in range(H):
  for w in range(W):
    if maze[h][w] == '.':
      newMaze = deepcopy(maze)
      newMaze[h][w] = '
      
      
      
      
      newSpots = [[h, w]]
      count = 0
      while True:
        spots = newSpots
        newSpots = []
        
        
        
        
        if 0 < len(spots):
          count += 1
        else:
          break
        for pos in spots:
          
          
          
          
          for d in dirs:
            x = d[1] + pos[1]
            y = d[0] + pos[0]
            if 0 <= x < W and 0 <= y < H and newMaze[y][x] == '.':
              newMaze[y][x] = '
              newSpots.append([y, x])
      if res < count:
        res = count
print(res-1)

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

maze = [list(input()) for _ in range(h)]
ans = 0

def bfs(sx, sy):
    INF = 1000000
    reached = [[INF for _ in range(w)] for _ in range(h)]
    reached[sx][sy] = 0
    d = deque()
    d.append([sx, sy])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while d:
        x, y = d.popleft()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if next_x < 0 or next_x > h - 1 or next_y < 0 or next_y > w - 1:
                continue
            if maze[next_x][next_y] == "
                continue
            if reached[next_x][next_y] != INF:
                continue
            d.append([next_x, next_y])
            reached[next_x][next_y] = reached[x][y] + 1
    gl = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == ".":
                gl = max(gl, reached[i][j])    
    return gl

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

Solution (Python):
import copy
h, w = map(int, input().split())
field = []

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

d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
ans = 0

for start_y in range(h):
    for start_x in range(w):
        if field[start_y][start_x] == "
            continue

        new_field = copy.deepcopy(field)
        next_pos = [(start_y, start_x)]
        cnt = 0
        new_field[start_y][start_x] = 0
        
        while True:
            next_pos_cand = []
            cnt += 1
            for y, x in next_pos:
                for dy, dx in d:
                    if 0 <= y + dy < h and 0 <= x + dx < w:
                        if new_field[y + dy][x + dx] == ".":
                            next_pos_cand.append((y + dy, x + dx))
                            new_field[y + dy][x + dx] = cnt
            next_pos = next_pos_cand

            if len(next_pos) == 0:
                ans = max(ans, cnt - 1)
                break

print(ans)

Solution (Python):
from collections import deque
from copy import deepcopy
 
def bfs(pos,map):
      while pos:
        x,y,depth=pos.popleft()
        if map[x][y]=="
            continue
        map[x][y]="
        if map[x-1][y]!="
          pos.append([x-1,y,depth+1])
        if map[x+1][y]!="
          pos.append([x+1,y,depth+1])
        if map[x][y+1]!="
          pos.append([x,y+1,depth+1])
        if map[x][y-1]!="
          pos.append([x,y-1,depth+1])
      return depth
H,W=map(int,input().split())
ans=0
fence=["
field=[fence]
for _ in range(H):
  L=list(input())
  field.append(["
field.append(fence)
for i in range(1,H+1):
  for j in range(1,W+1):
    if field[i][j]==".": 
      pos=deque([[i,j,0]])
      depth=bfs(pos,deepcopy(field))
      if ans<depth:
        ans=depth
print(ans)

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

def main():        
    h,w=map(int,input().split())
    s=[input() for _ in range(h)]

    def bfs(x,y):
        dist=[[-1]*w  for _ in range(h)]
        seen=[[False]*w for _ in range(h)]
        stk=[(x,y,0)]
        while stk:
            px,py,dst=stk.pop(0)
            if seen[px][py]:
                continue
            seen[px][py]=True
            
            if s[px][py]=='
                dist[px][py]=0
                continue
            
            for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
                if px+x<0 or px+x>=h or py+y<0 or py+y>=w:
                    continue
                else:
                    stk.append((px+x,py+y,dst+1))
            dist[px][py]=dst
        ans=0
    
        for i in range(h):
            ans=max(max(dist[i]),ans)
        return ans
    
    ans=0
    for i in range(h):
        for j in range(w):
            if s[i][j]=='
                continue
            ans=max(ans,bfs(i,j))
    print(ans)

if __name__ == '__main__':
    main()

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 sys import stdin
from collections import deque
H,W = [int(x) for x in stdin.readline().rstrip().split()]
grid = [input() for i in range(H)]

visited = [[False for i in range(W)] for i in range(H)]
visit_p = deque()
ans = 0

for h,i in enumerate(grid):
    for w, j in enumerate(i):
        if j != "
            visited[h][w] = True
            visit_p.append((h, w, 0))
        while visit_p:
            nh,nw,num = visit_p.popleft()
            
            for dh,dw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                if not (0 <= nh+dh < H) or not (0 <= nw+dw < W):
                    
                    continue

                if visited[nh+dh][nw+dw] or grid[nh+dh][nw+dw] == '
                    
                    continue

                visit_p.append((nh+dh,nw+dw,num+1))
                visited[nh+dh][nw+dw] = True
                ans = max(ans,num+1)
        visited = [[False for i in range(W)] for i in range(H)]
print(ans)

Solution (Python):
from sys import stdin
from collections import deque
H,W = [int(x) for x in stdin.readline().rstrip().split()]
grid = [input() for i in range(H)]

visited = [[False for i in range(W)] for i in range(H)]
visit_p = deque()
ans = 0

search_p = []
for h,i in enumerate(grid):
    for w, j in enumerate(i):
        if j != "
            search_p.append((h, w, 0))

for p in search_p:
    visited[p[0]][p[1]] = True
    visit_p.append(p)
    while visit_p:
        nh,nw,num = visit_p.popleft()

        for dh,dw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            if not (0 <= nh+dh < H) or not (0 <= nw+dw < W):
                
                continue

            if visited[nh+dh][nw+dw] or grid[nh+dh][nw+dw] == '
                
                continue

            visit_p.append((nh+dh,nw+dw,num+1))
            visited[nh+dh][nw+dw] = True
            ans = max(ans,num+1)
    visited = [[False for i in range(W)] for i in range(H)]
print(ans)

Solution (Python):
from collections import deque
 
H,W = map(int,input().split())
 
N = H*W
 
data = ["
for i in range(H):
  data.append("
data.append("
 
offsets = [(0,1),(0,-1),(1,0),(-1,0),]
 
tree = {}
for i in range(1,H+1):
  for j in range(1,W+1):
    if data[i][j] != ".":
      pass
    else:
      tree[(i,j)] = []
      for o in offsets:
        i_ = i+o[0]
        j_ = j+o[1]
        if data[i_][j_] == "." :
          tree[(i,j)].append((i_,j_))


nodes = list(tree.keys())
  
FARTHEST = 0



for start_node in nodes:
  d = [[9999999]*(W+2) for _ in range(H+2)]
  
  q = deque()
  q.append(start_node)
  d[start_node[0]][start_node[1]] = 0
  res = 0 

  
  while len(q) > 0:
    
      
      node = q.popleft()
      if node is not None:
          nd = d[node[0]][node[1]] + 1
          childs = tree[node]
          for child in childs:
            if nd < d[child[0]][child[1]]:
              d[child[0]][child[1]] = nd
              res = nd
              q.append(child)
 
      if FARTHEST < res:
        FARTHEST = res
      
print(FARTHEST)

Solution (Python):
from collections import deque

INF = float("inf")

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

N = H*W

data = ["
for i in range(H):
  data.append("
data.append("

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

nodes = []
for i in range(1,H+1):
  for j in range(1,W+1):
    if data[i][j] == ".":
      nodes.append((i,j))

FARTHEST = 0

for start_node in nodes:
  i = start_node[0]
  j = start_node[1]
  d = [[INF]*(W+2) for i in range(H+2)]
  d[i][j] = 0
  q = deque([(i,j)])
  res = 0
  while q:
    x,y = q.popleft()
    nd = d[x][y]+1
    for o in offsets:
      nx, ny = x+o[0], y+o[1]
      if data[nx][ny] == "
        continue
      if nd < d[nx][ny]:
        d[nx][ny] = nd
        q.append((nx,ny))
        res = nd
  if res > FARTHEST:
    FARTHEST = res

print(FARTHEST)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

H,W = map(int,readline().split())
H += 2; W += 2
grid = '
for _ in range(H-2):
    grid += '
grid += '


def bfs(start):
    inf = 10**9
    dist = [inf] * (H*W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1,1,W,-W):
            w = v + move
            if grid[w] == '
                continue
            if dist[w] > dv + 1:
                dist[w] = dv + 1
                q.append(w)
    return max(x for x in dist if x != inf)


print(max(bfs(v) for v in range(H*W) if grid[v] != '

Solution (Python):



from collections import deque

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(n):
  reach=deque([n])
  check=[-1 for _ in range(H*W)]
  check[n]=0
  while reach:
    v=reach.popleft()
    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 = ['
ans = 0

for y in range(1, H+1):
    for x in range(1, W+1):
        if s[y][x] == '
            continue
        visited = [[0]*(W+2) for _ in range(H+2)]
        visited[y][x] = 1
        max_s = 0
        dq = deque([(y, x, 0)])

        while dq:
            cy, cx, steps = dq.popleft()
            if steps > max_s:
                max_s = steps
            steps += 1

            for dy, dx in ((cy+1, cx), (cy-1, cx), (cy, cx+1), (cy, cx-1)):
                if s[dy][dx] == '
                    continue
                visited[dy][dx] = 1
                dq.append((dy, dx, steps))

        ans = max(ans, max_s)

print(ans)

Solution (Python):
import math 
import bisect
import heapq
from collections import deque

h,w=map(int,input().split())
M=[]
M=[input() for _ in range(h)]
 
def bfs(x,y):
    dist=[[-1]*w  for _ in range(h)]
    seen=[[False]*w for _ in range(h)]
    stk=[(x,y,0)]
    while stk:
        px,py,dst=stk.pop(0)
        if seen[px][py]:
            continue
        seen[px][py]=True
        
        if M[px][py]=='
            dist[px][py]=0
            continue
        
        for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
            if px+x<0 or px+x>=h or py+y<0 or py+y>=w:
                continue
            else:
                stk.append((px+x,py+y,dst+1))
        dist[px][py]=dst
    ans=0
 
    for i in range(h):
        ans=max(max(dist[i]),ans)
    return ans
ans = 0
for i in range(h):
    for j in range(w):
        if M[i][j]=='
            continue
        ans=max(bfs(i,j),ans)
print(ans)

Solution (Python):
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [[ord(i) for i in input()] for _ in range(h)]
wall = ord("


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = [[False] * w for _ in range(h)]
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    visited[s][t] = True
    while q1:
        i = q1.popleft()
        j = q2.popleft()
        r = depth[i][j] + 1
        if j != w - 1:
            if mass[i][j + 1] != wall and not visited[i][j + 1]:
                q1.append(i)
                q2.append(j+1)
                visited[i][j + 1] = True
                depth[i][j + 1] += r
        if j != 0:
            if mass[i][j - 1] != wall and not visited[i][j - 1]:
                q1.append(i)
                q2.append(j - 1)
                visited[i][j - 1] = True
                depth[i][j - 1] += r
        if i != 0:
            if mass[i - 1][j] != wall and not visited[i - 1][j]:
                q1.append(i-1)
                q2.append(j)
                visited[i - 1][j] = True
                depth[i - 1][j] += r
        if i != h - 1:
            if mass[i + 1][j] != wall and not visited[i + 1][j]:
                q1.append(i + 1)
                q2.append(j)
                visited[i + 1][j] = True
                depth[i + 1][j] += r
    return np.max(depth)


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

Solution (Python):
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [[ord(i) for i in input()] for _ in range(h)]
wall = ord("
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = [[False] * w for _ in range(h)]
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    visited[s][t] = True
    while q1:
        i = q1.popleft()
        j = q2.popleft()
        r = depth[i][j] + 1
        if j != w - 1:
            if mass[i][j + 1] != wall and not visited[i][j + 1]:
                q1.append(i)
                q2.append(j+1)
                visited[i][j + 1] = True
                depth[i][j + 1] += r
        if j != 0:
            if mass[i][j - 1] != wall and not visited[i][j - 1]:
                q1.append(i)
                q2.append(j - 1)
                visited[i][j - 1] = True
                depth[i][j - 1] += r
        if i != 0:
            if mass[i - 1][j] != wall and not visited[i - 1][j]:
                q1.append(i-1)
                q2.append(j)
                visited[i - 1][j] = True
                depth[i - 1][j] += r
        if i != h - 1:
            if mass[i + 1][j] != wall and not visited[i + 1][j]:
                q1.append(i + 1)
                q2.append(j)
                visited[i + 1][j] = True
                depth[i + 1][j] += r
    return np.max(depth)


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

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


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

def bfs(x,y):
    dist=[[-1]*w  for _ in range(h)]
    seen=[[False]*w for _ in range(h)]
    stk=[(x,y,0)]
    while stk:
        px,py,dst=stk.pop(0)
        if seen[px][py]:
            continue
        seen[px][py]=True
        
        if M[px][py]=='
            dist[px][py]=0
            continue
        
        for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
            if px+x<0 or px+x>=h or py+y<0 or py+y>=w:
                continue
            else:
                stk.append((px+x,py+y,dst+1))
        dist[px][py]=dst
    ans=0

    for i in range(h):
        ans=max(max(dist[i]),ans)
    return ans

ans=0
for i in range(h):
    for j in range(w):
        if M[i][j]=='
            continue
        ans=max(bfs(i,j),ans)

print(ans)

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


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

def bfs(x,y):
    dist=[[-1]*w  for _ in range(h)]
    seen=[[False]*w for _ in range(h)]
    stk=[(x,y,0)]
    while stk:
        px,py,dst=stk.pop()
        if seen[px][py]:
            continue
        seen[px][py]=True
        
        if M[px][py]=='
            dist[px][py]=0
            continue
        
        for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
            if px+x<0 or px+x>=h or py+y<0 or py+y>=w:
                continue
            else:
                stk.insert(0,(px+x,py+y,dst+1))
        dist[px][py]=dst
    ans=0

    for i in range(h):
        ans=max(max(dist[i]),ans)
    return ans

ans=0
for i in range(h):
    for j in range(w):
        if M[i][j]=='
            continue
        ans=max(bfs(i,j),ans)

print(ans)

Solution (Python):
H, W = [int(i) for i in input().split()]
S = [input() for _ in range(H)]
inf = 1000000
dist = [[-1]*(W*H) for _ in range(W*H)]

def bfs(s):
    seen = set()
    stk = [(s, 0)]
    while stk:
        pt, dst = stk.pop()
        ph, pw = pt//W, pt%W
        if(pt in seen):
            continue
        seen.add(pt)

        if(S[ph][pw]=='
            dist[s][pt] = 0
            continue

        for x,y in ((1,0), (-1,0), (0, 1), (0,-1)):
            if((not(0<=pw+x<W))or (not(0<=ph+y<H))):
                continue
            else:
                ns = (ph+y)*W + (pw+x)
                stk.insert(0, (ns, dst+1))
        dist[s][pt] = dst
        
ans = 0
for s in range(H*W):
    h, w = s//W, s%W
    if(S[h][w]=='
        continue
    bfs(s)
    
    ans = max(ans, max(dist[s]))

print(ans)

Solution (Python):
import copy
from collections import deque
h, w = map(int, input().split())
mapping = [0]*h
for i in range(h):
  mapping[i] = input()

  
already = [[False]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    if mapping[i][j] == "
      already[i][j] = True


ans = 0

for i in range(h):
  for j in range(w):
    if already[i][j]:
      continue
    
    yet = copy.deepcopy(already)
    yet[i][j] = True
    not_yet = deque([])
    
    depth = [[0]*w for i in range(h)]
    
    if i != 0 and not yet[i-1][j]:
        not_yet.append([i-1, j])
        depth[i-1][j] = 1
        yet[i-1][j] = True
    if i != h-1 and not yet[i+1][j]:
        not_yet.append([i+1, j])
        depth[i+1][j] = 1
        yet[i+1][j] = True
    if j != 0 and not yet[i][j-1]:
        not_yet.append([i, j-1])
        depth[i][j-1] = 1
        yet[i][j-1] = True
    if j != w-1 and not yet[i][j+1]:
        not_yet.append([i, j+1])
        depth[i][j+1] = 1
        yet[i][j+1] = True
    
    while len(not_yet) > 0:
        key = not_yet.popleft()
        a, b = key[0], key[1]
        
        if a != 0 and not yet[a-1][b]:
            not_yet.append([a-1, b])
            yet[a-1][b] = True
            depth[a-1][b] = depth[a][b]+1
            
        if a != h-1 and not yet[a+1][b]:
            not_yet.append([a+1, b])
            yet[a+1][b] = True
            depth[a+1][b] = depth[a][b]+1
            
        if b != 0 and not yet[a][b-1]:
            not_yet.append([a, b-1])
            yet[a][b-1] = True
            depth[a][b-1] = depth[a][b]+1
            
        if b != w-1 and not yet[a][b+1]:
            not_yet.append([a, b+1])
            yet[a][b+1] = True
            depth[a][b+1] = depth[a][b]+1
            
    for x in range(h):
        for y in range(w):
            if ans < depth[x][y]:
                ans = depth[x][y]
print(ans)

Solution (Python):
from collections import deque

def bfs(Sy,Sx):

    dis=[[-1]*W for i in range(H)]
    dis[Sy][Sx]=0
    q=deque()
    q.append([Sy,Sx])
    nun=0

    
    while(len(q)!=0):
        y=q[0][0]
        x=q[0][1]
        q.popleft()
        
        
        for dy,dx in ([0, 1], [1, 0], [0, -1], [-1, 0]):
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if field[ny][nx]=="
                continue
            if dis[ny][nx]!=-1:
                continue
            dis[ny][nx]=dis[y][x]+1
            nun=max(nun,dis[ny][nx])
            q.append([ny,nx])
    return nun
  

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


ans=-1
for y in range(H):
    for x in range(W):
        if field[y][x]=="
            continue
        ans=max(ans,bfs(y,x))
print(ans)

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

def max_distance(board, H, W, x, y):
    check = [[False] * W for i in range(H)]
    ans = 0
    q = deque()
    q.append((x, y, 0))
    check[y][x] = True
    while len(q) > 0:
        x, y, cost = q.popleft()
        ans = max(ans, cost)
        for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if 0 <= nx and nx < W and 0 <= ny and ny < H:
                if not check[ny][nx] and board[ny][nx] == ".":
                    q.append((nx, ny, cost + 1))
                    check[ny][nx] = True
    return ans

    

def main():
    H, W = map(int, input().split())
    board = [input().strip() for i in range(H)]

    ans = 0
    for y in range(H):
        for x in range(W):
            if board[y][x] == ".":
                tmp = max_distance(board, H, W, x, y)
                
                ans = max(ans, tmp)
    print(ans)

if __name__ == "__main__":
    main()

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

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

ans = 0
for i in range(H):
  for j in range(W):

    if S[i][j]=='
      continue
    
    
    
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0

    
    q = deque([[i, j]])

    
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for h, w in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
        
        
        if (h<0) or (h>H-1) or (w<0) or (w>W-1):
          continue
        
        if S[h][w]=='
          continue

        
        c = b+1

        
        if c>=A[h][w]:
          continue

        A[h][w]=c
        
        q.append([h,w])
      
    A = np.array(A)

    
    
    ans = max(ans, max(A[A<10**5]))
    
print(ans)

Solution (Python):
h,w = map(int,input().split())
ls = [input() for _ in range(h)]
from collections import deque
a = 0
for i in range(h):
  for j in range(w):
    if ls[i][j]=='
    d = [[-1]*w for _ in range(h)]
    d[i][j] = 0
    q = deque([(i,j)])
    while q:
      x,y = q.popleft()
      for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
        nx,ny = x+dx,y+dy
        if not (0<=nx<h and 0<=ny<w): continue
        if ls[nx][ny]=='.' and d[nx][ny]==-1:
          d[nx][ny] = d[x][y]+1
          q.append((nx,ny))
    a = max(a,max(max(j for j in i) for i in d))
print(a)

Solution (Python):
from collections import deque

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

INF = int(1e10 + 7)
d = [[INF] * w for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]





def bfs(x, y):
    d = [[INF] * w for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([(x, y)])
    d[x][y] = 0

    while len(que) != 0:
        val = que.popleft()

        for i in range(4):
            nx = val[0] + dx[i]
            ny = (val[1] + dy[i])
            if (0 <= nx < h and 0 <= ny < w and maze[nx][ny] != '
                que.append((nx, ny))
                d[nx][ny] = d[val[0]][val[1]] + 1
    maxval = 0
    for i in range(h):
        for j in range(w):
            if d[i][j] > maxval and d[i][j] != INF:
                maxval = d[i][j]
    return maxval

maxans = 0
cnt = []
for i in range(h):
    for j in range(w):
        if maze[i][j] != '
            if bfs(i, j) > maxans:
                maxans = bfs(i, j)
print(maxans)

Solution (Python):
from collections import deque
def bfs(sy,sx):
    d = [[-float("inf")] * (2+w) for i in range(h+2)]

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

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

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

            if maze[nx][ny] != "
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    ans = 0
    for i in range(2+w):
        for j in range(h+2):
            ans = max(ans,d[j][i])
    return ans
h,w = map(int, input().split())
maze = [["
ans = 0
for x in range(1,w+1):
    for y in range(1,h+1):
        if maze[y][x] == ".":
            ans = max(bfs(y,x),ans)
print(ans)

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

S = ["
for i in range(H):
    S.append("
S.append("

H += 2
W += 2

max_dist = 0
for sy,sx in product(range(1,H),range(1,W)):
    dist = [[H*W+1]*W for i in range(H)]
    if S[sy][sx] == "
        continue
    dq = deque([(sy,sx)])
    dist[sy][sx] = 0
    while dq:
        py,px = dq.popleft()
        for ny, nx in [(py+1,px),(py-1,px),(py,px+1),(py,px-1)]:
            if S[ny][nx] == "
                continue
            if dist[ny][nx] > dist[py][px] + 1:
                dist[ny][nx] = dist[py][px] + 1
                max_dist = max(max_dist, dist[ny][nx])
                dq.append((ny,nx))
    
    

print(max_dist)

Solution (Python):
import queue

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


def srch(h,w):
    ans = 0
    cnt = [[-1 for _ in range(W)] for _ in range(H)]
    que = queue.Queue()
    li1 = [1,0,-1,0]
    li2 = [0,1,0,-1]
    ans = 0
    res = 0

    que.put([h,w,0])
    cnt[h][w]=0

    while not(que.empty()):
        plc = que.get()
        y = plc[0]
        x = plc[1]
        ans = plc[2]

        for i in range(4):
            ny,nx = y+li1[i], x+li2[i]
            
            if ny>=0 and ny<H and nx>=0 and nx<W and cnt[ny][nx]==-1 and S[ny][nx]==".":
                cnt[ny][nx]= ans+1
                que.put([ny,nx,ans+1])
                res = ans +1
    
    
    
    
    
            

    return res


ans = 0

for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            ans = max(ans,srch(h,w))

print(ans)

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

def cango(now,h,w):
    ans = []
    if now[0]>0:
        ans.append( (now[0]-1,now[1]) )
    if now[0]<h-1:
        ans.append( (now[0]+1,now[1]) )
    if now[1]>0:
        ans.append( (now[0],now[1]-1) )
    if now[1]<w-1:
        ans.append( (now[0],now[1]+1) )
    return ans

from collections import deque

ans=0
for hh in range(h):
    for ww in range(w):
        if s[hh][ww]==".":
            start = (hh,ww)
            q = deque( [] )
            q.append( ((-1,-1),start,0) )
            visit = [[0]*w for _ in range(h)]
            visit[hh][ww]=1
            while q:
                old,now,dist = q.popleft()

                if ans<dist:
                    ans=dist
                for new in cango(now,h,w):
                    if s[new[0]][new[1]]=="." and visit[new[0]][new[1]]==0:
                        q.append( (now,new,dist+1) )
                        visit[new[0]][new[1]] = 1
print(ans )