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

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

dxy = [(0,1),(1,0),(0,-1),(-1,0)]
from collections import deque
ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '
        dist = [[0]*W for i in range(H)]
        visited = [[0]*W for i in range(H)]
        visited[y][x] = 1
        q = deque([(x,y)])
        while q:
            x,y = q.popleft()
            for dx,dy in dxy:
                nx,ny = x+dx,y+dy
                if not 0 <= nx < W: continue
                if not 0 <= ny < H: continue
                if visited[ny][nx]: continue
                if S[ny][nx] == '
                visited[ny][nx] = 1
                dist[ny][nx] = dist[y][x] + 1
                q.append((nx,ny))


        for i in range(H):
            ans = max(ans, max(dist[i]))
        
print(ans)

Solution (Python):
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= nx < W: continue
                if not 0 <= ny < H: continue
                if visited[ny][nx]: continue
                if S[ny][nx] == '
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True

        """
        for i in range(H):
            ans = max(ans, max(dist[i]))
        """
        ans = max(ans, max(max(row) for row in dist))

            

print(ans)

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

dxy = [(0,1),(1,0),(0,-1),(-1,0)]
from collections import deque
ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '
        dist = [[0]*W for i in range(H)]
        visited = [[0]*W for i in range(H)]
        visited[y][x] = 1
        q = deque([(x,y)])
        while q:
            x,y = q.popleft()
            for dx,dy in dxy:
                nx,ny = x+dx,y+dy
                if not 0 <= nx < W: continue
                if not 0 <= ny < H: continue
                if visited[ny][nx]: continue
                if S[ny][nx] == '
                visited[ny][nx] = 1
                dist[ny][nx] = dist[y][x] + 1
                q.append((nx,ny))


        for i in range(H):
            ans = max(ans, max(dist[i]))
        
print(ans)

Solution (Python):
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or visited[ny][nx] == True or S[ny][nx] == "
                    continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True


        ans = max(ans, max(max(row) for row in dist))

            

print(ans)

Solution (Python):
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or visited[ny][nx] == True or S[ny][nx] == "
                    continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True



        ans = max(ans, max(max(row) for row in dist))

            

print(ans)

Solution (Python):
from collections import deque
import math
import copy
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
def bfs(maze,h,w,sx,sy):
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                maze[y][x]=float('inf')

    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0 <= y+i < H and 0<=x+j<W:
                nexty,nextx=y+i,x+j
                dist=maze[nexty][nextx]
                if dist!='
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    m = 0                   
    for l in maze:
      li = [i for i in l if i != '
      if len(li) > 0:
        m = max(m,max(li))
    return m
max_dist = -1  
for si in range(H):
  for sj in range(W):
    if maze[si][sj] == '
      continue
    copymaze = copy.deepcopy(maze)
    res = bfs(copymaze,H,W,sj,si)
    max_dist = max(max_dist,res)
print(max_dist)

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


'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


def bfs(h, w, m, start):

    import queue
    d = [[0 for i in range(w)]for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    flg = False

    a = queue.Queue()
    a.put(start)
    
    while not a.empty():
        hh, ww = map(int, a.get())
        for i in range(4):
            nx, ny = ww+dx[i], hh+dy[i]
            if 0 <= ny < h and 0 <= nx < w and m[ny][nx] != "
                a.put([ny, nx])
                d[ny][nx] = d[hh][ww]+1
    
    return d[hh][ww]



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

ans=[]
for i in range(h):
    for j in range(w):
        if m[i][j]!="
            start=[i,j]
            ans.append(bfs(h,w,m,start))
            

print(max(ans))

Solution (Python):
from collections import deque
h , w = map(int,input().split())
ma = [["
for i in range(h):
    kar = ["
    kar.extend(list(input()))
    kar.append("
    ma.append(kar)
ma.append(["
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if ma[i][j] == "
            continue
        elif ma[i][j] ==".":
            p = [[-1 for g in range(w+2)] for f in range(h+2)]
            p[i][j] = 0
            q = deque()
            q.append([i,j])
            while q:
                y,x = q.popleft()
                if ma[y+1][x] == "." and p[y+1][x] == -1:
                    p[y+1][x] = p[y][x] + 1
                    q.append([y+1,x])
                if ma[y-1][x] == "." and p[y-1][x] == -1:
                    p[y-1][x] = p[y][x] + 1
                    q.append([y-1,x])
                if ma[y][x+1] == "." and p[y][x+1] == -1:
                    p[y][x+1] = p[y][x] + 1
                    q.append([y,x+1])
                if ma[y][x-1] == "." and p[y][x-1] == -1:
                    p[y][x-1] = p[y][x] + 1
                    q.append([y,x-1])
            for l in range(1,h+1):
                ans = max(ans,max(p[l]))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(3000)

import numpy as np

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

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

from collections import deque

def bfs(i,j,dist):
    lis = [[i-1,j],[i,j-1],[i+1,j],[i,j+1]]
    for place in lis:
        if place[0]<0 or place[0]>=h or place[1]<0 or place[1]>=w:
            continue
        if seen[place[0]][place[1]] != -1 or s[place[0]][place[1]]=="
            continue
        seen[place[0]][place[1]] = dist+1
        que.append([place[0],place[1],dist+1])
    if len(que):
        new = que.popleft()
        bfs(new[0],new[1],new[2])
    else:
        return


mx = 0
for i in range(h):
    for  j in range(w):
        if s[i][j]=="
            continue
        seen = [[-1 for _ in range(w)]for _ in range(h)]
        que = deque()
        seen[i][j] = 0
        bfs(i,j,0)
        ast = np.array(seen)
        tmp = np.amax(ast)
        mx = max(mx,tmp)
        
            
print(mx)

Solution (Python):
import sys
sys.setrecursionlimit(3000)

import numpy as np

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

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

from collections import deque

def bfs(i,j,dist):
    seen[i][j] = dist
    lis = [[i-1,j],[i,j-1],[i+1,j],[i,j+1]]
    for place in lis:
        if place[0]<0 or place[0]>=h or place[1]<0 or place[1]>=w:
            continue
        if seen[place[0]][place[1]] != -1 or s[place[0]][place[1]]=="
            continue
        if [place[0],place[1],dist+1] in que:
            continue
        que.append([place[0],place[1],dist+1])
    if len(que):
        new = que.popleft()
        bfs(new[0],new[1],new[2])
    else:
        return


mx = 0
for i in range(h):
    for  j in range(w):
        if s[i][j]=="
            continue
        seen = [[-1 for _ in range(w)]for _ in range(h)]
        que = deque()
        bfs(i,j,0)
        ast = np.array(seen)
        tmp = np.amax(ast)
        mx = max(mx,tmp)
        
            
print(mx)

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

res = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(h):
	for j in range(w):
		if s[i][j] == "
			continue
		queue = deque([[i,j]])
		visited = [[-1 for ii in range(w)] for jj in range(h)]
		visited[i][j] = 0
		while queue:
			l,m = queue.popleft()
			for k in range(4):
				x = l + dx[k]
				y = m + dy[k]
				if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] != -1 or s[x][y] == "
					continue
				visited[x][y] = visited[l][m] + 1
				queue.append([x,y])
		for ii in range(h):
			for jj in range(w):
				res = max(res,visited[ii][jj])
print (res)

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

res = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(h):
	for j in range(w):
		if s[i][j] == "
			continue
		queue = deque([[i,j]])
		visited = [[0 for ii in range(w)] for jj in range(h)]
		visited[i][j] = 1
		while queue:
			l,m = queue.popleft()
			for k in range(4):
				x = l + dx[k]
				y = m + dy[k]
				if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] != 0 or s[x][y] == "
					continue
				visited[x][y] = visited[l][m] + 1
				queue.append([x,y])
		for ii in range(h):
			for jj in range(w):
				res = max(res,visited[ii][jj])
print (res-1)

Solution (Python):
from collections import deque

def bfs(maze, y, x, h, w):
  queue = deque([[y, x]])
  visited = list([-1] * w for i in range(h))
  visited[y][x] = 0
  num = 0

  while queue:
    a, b = queue.popleft()
    for i, j in ([0, 1], [0, -1], [1, 0], [-1, 0]):
       new_y, new_x = a + i, b + j
       if(new_y >= 0 and new_x >= 0 and new_y < h and new_x < w):
        if(maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1):
          visited[new_y][new_x] = visited[a][b] + 1
          num = max(num, visited[new_y][new_x])
          queue.append([new_y, new_x])
  return num
  
if __name__ == '__main__':
  y, x = map(int, input().split())
  maze = list(input() for i in range(y))
  num = -1
  for i in range(y):
    for j in range(x):
      if(maze[i][j] == '.'):
        num = max(num, bfs(maze, i, j, y, x))

  print(num)

Solution (Python):
from collections import deque

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

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0

        if maze[i][j] == "
            continue
        visited = [[False] * w for _ in range(h)]
        plan = deque()
        step = 1
        plan.appendleft((i, j, step))
        visited[i][j] = True
        while plan:
            y, x, step = plan.pop()
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "
                    continue
                visited[next_y][next_x] = True
                if step > largest_step:
                    largest_step = step
                plan.appendleft((next_y, next_x, step + 1))
        if largest_step > max_step:
            max_step = largest_step

print(max_step)

Solution (Python):
from collections import deque

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

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0

        if maze[i][j] == "
            continue
        visited = [[False] * w for _ in range(h)]
        plan = deque()
        step = 1
        plan.appendleft((i, j, step))
        visited[i][j] = True
        while plan:
            y, x, step = plan.pop()
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "
                    continue
                visited[next_y][next_x] = True
                if step > largest_step:
                    largest_step = step
                plan.appendleft((next_y, next_x, step + 1))
        if largest_step > max_step:
            max_step = largest_step

print(max_step)

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

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

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0

        if maze[i][j] == "
            continue
        visited = [[False] * w for _ in range(h)]
        distance = [[-1] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        distance[i][j] = step
        visited[i][j] = True
        while plan:
            y, x, step = plan.pop()

            
            
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "
                    continue
                distance[next_y][next_x] = distance[y][x] + 1
                visited[next_y][next_x] = True
                plan.appendleft((next_y, next_x, step + 1))

        
        
        max_step = max(max_step, np.max(np.array(distance)))

print(max_step)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
meiro=[]
for i in range(h):
	tmp=input()
	meiro.append([tmp[i] for i in range(w)])



def bfs(sh,sw,meiro):
	que=deque([[sh,sw]])
	dist=[[-1 for _ in range(w)] for _ in range(h)]
	dist[sh][sw]=0

	while True:
		if que == deque([]):
			tmpmax=0
			for di in dist:
				tmptmpmax=max(di)
				if tmptmpmax>tmpmax:
					tmpmax=tmptmpmax
			return tmpmax
		
		
		check=que.popleft()
		hnow=check[0]
		wnow=check[1]
		
		dnow=dist[hnow][wnow]
		
		hnext=hnow-1
		wnext=wnow
		if 0 < hnow:
			if dist[hnext][wnext]==-1 and meiro[hnext][wnext] == ".":
				que.append([hnext,wnext])
				dist[hnext][wnext]=dnow+1
		
		hnext=hnow+1
		wnext=wnow
		if h-1 > hnow:
			if dist[hnext][wnext]==-1 and meiro[hnext][wnext] == ".":
				que.append([hnext,wnext])
				dist[hnext][wnext]=dnow+1
		
		hnext=hnow
		wnext=wnow-1
		if 0 < wnow:
			if dist[hnext][wnext]==-1 and meiro[hnext][wnext] == ".":
				que.append([hnext,wnext])
				dist[hnext][wnext]=dnow+1
		
		hnext=hnow
		wnext=wnow+1
		if w-1 > wnow:
			if dist[hnext][wnext]==-1 and meiro[hnext][wnext] == ".":
				que.append([hnext,wnext])
				dist[hnext][wnext]=dnow+1

roadlist=[]
for i in range(h):
	for j in range(w):
		if meiro[i][j] == ".":
			roadlist.append([i,j])

amax=0
for start in roadlist:
	tmp=bfs(start[0],start[1],meiro)
	if tmp > amax:
		amax = tmp

print(amax)

Solution (Python):
import numpy as np
from collections import deque
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))

def bfs(sy, sx):
  dist = [[-1]*W for _ in range(H)]
  dist[sy][sx] = 0
  q = deque([[sy, sx]])

  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      ny = y + dy
      nx = x + dx
      if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1 and S[ny][nx] == '.':
        dist[ny][nx] = dist[y][x] + 1
        q.append([ny, nx])

  return dist

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

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

    from collections import deque

    dist = [0]*(H*W)
    for s in range(H*W):
        search_list = deque([s])
        visited_set = set([])
        d = [0] * (H*W)
        while search_list:
            now = search_list.popleft()
            visited_set.add(now)
            h = now // W
            w = now % W
            if S[h][w] == '
                continue
            for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                new_h = h+i
                new_w = w+j
                new_s = new_h * W + new_w
                if new_h in [-1, H] or new_w in [-1, W]:
                    continue
                elif new_s in search_list:
                    continue
                elif new_s in visited_set:
                    continue
                elif S[new_h][new_w] == '
                    continue
                else:
                    d[new_s] = d[now]+1
                    search_list.append(new_s)
        dist[s] = max(d)
    print(max(dist))


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

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

    from collections import deque

    dist = [0]*(H*W)
    for s in range(H*W):
        search_list = deque([s])
        visited_set = set([])
        d = [0] * (H*W)
        while search_list:
            now = search_list.popleft()
            visited_set.add(now)
            h = now // W
            w = now % W
            if S[h][w] == '
                continue
            for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                new_h = h+i
                new_w = w+j
                new_s = new_h * W + new_w
                if new_h in [-1, H] or new_w in [-1, W]:
                    continue
                elif new_s in search_list:
                    continue
                elif new_s in visited_set:
                    continue
                elif S[new_h][new_w] == '
                    continue
                else:
                    d[new_s] = d[now]+1
                    search_list.append(new_s)
        dist[s] = max(d)
    print(max(dist))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import numpy as np
INF = float("inf")










cmd = [[-1,0],[1,0],[0,1],[0,-1]]
h,w = map(int,input().split())
Map = [["
for _ in range(h):
    s = ["
    Map.append(s)
Map.append(["
MAX = 0
for sx in range(1,w+1):
    for sy in range(1,h+1):
        p = 0
        if Map[sy][sx] == "
            continue
        q = deque([[sx,sy]])
        visidat = [[0]*(w+2) for _ in range(h+2)]
        while len(q) != 0:
            x,y = q.popleft()
            for cx,cy in cmd:
                newx = x + cx
                newy = y + cy
                if Map[newy][newx] == "
                    continue
                else: 
                    if visidat[newy][newx] == 0:
                        visidat[newy][newx] += visidat[y][x] + 1
                        if p < visidat[newy][newx]:
                            p = visidat[newy][newx]
                        q.append([newx,newy])
        MAX = max(MAX,p)
print(MAX)

Solution (Python):
from  collections import deque
H,W=list(map(int,input().split()))
S=[list(input()) for i in range(H)]
dxdy=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
for w in range(W):
    for h in range(H):
        if S[h][w]!='
            temp=0
            stack=deque([[h,w]])
            visited=[[-1 for i in range(W)]for j in range(H)]
            visited[h][w]=0
            while stack:
                x,y=stack.popleft()
                for i in dxdy:
                    nx,ny=x+i[0],y+i[1]
                    if 0<=nx<H and 0<=ny<W and S[nx][ny]!='
                        stack.append([nx,ny])
                        visited[nx][ny]=visited[x][y]+1
            temp=max([j for i in visited for j in i])
            ans=max(ans,temp)
print(ans)

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

def abc151_d():
    H, W = map(int, readline().strip().split())
    
    grid = [['
    for ln in read().split():
        grid.append(['
    else:
        grid.append(['

    
    from collections import deque
    def bfs_max_dist(sx, sy):
        dist = [[-1] * (W+2) for _ in range(H+2)]
        dist[sx][sy] = 0
        que = deque([(sx, sy)])
        dmax = 0
        while que:
            r, c = que.popleft()
            for i, j in ((r-1, c), (r, c-1), (r, c+1), (r+1, c)):
                if grid[i][j] == '
                if dist[i][j] != -1: continue
                dist[i][j] = dist[r][c] + 1
                que.append((i, j))
                dmax = max(dist[r][c] + 1, ans)
        return dmax

    
    ans = 0
    for r in range(1, H+1):
        for c in range(1, W+1):
            if grid[r][c] == '
            ans = max(bfs_max_dist(r, c), ans)
    print(ans)

abc151_d()

Solution (Python):
import queue
h, w = map(int,input().split())
way = ["" for i in range(h+1)]
way[h] = "
for i in range(h):
    way[i] = str(input())+"
G = [[[] for j in range(w)] for i in range(h)]
road = []
for i in range(h):
    for j in range(w):
        if way[i][j] == "
            continue
        else:
            road.append([i,j])
        if way[i+1][j] == ".":
            G[i][j].append([i+1,j])
        if way[i-1][j] == ".":
            G[i][j].append([i-1,j])
        if way[i][j+1] == ".":
            G[i][j].append([i,j+1])
        if way[i][j-1] == ".":
            G[i][j].append([i,j-1])
M = 0

for i in road:
    q = queue.Queue()
    q.put(i)
    t = [[-1 for k in range(w+1)] for j in range(h+1)]
    t[i[0]][i[1]] = 0
    while not q.empty():
        j = q.get()
        for l in G[j[0]][j[1]]:
            if t[l[0]][l[1]] == -1:
                t[l[0]][l[1]] = t[j[0]][j[1]] + 1
                q.put(l)
    for k in t:
        if M < max(k):
            M = max(k)

print(M)

Solution (Python):
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    from collections import deque
    import copy
    h,w=L()
    grid=[S() for i in range(h)]
    dist=[[-1]*w for i in range(h)]
    start=deque()
    for i in range(h):
        for j in range(w):
            if grid[i][j]=='.':
                start.append((i,j))
                
                
                dist[i][j]=-2
                
    def bfs(start,dist):
        ans=0
        d=0
        search=deque()
        
        while start:
            
            
            
            sty,stx=start.popleft()
            search.append((sty,stx))
            new_dist=copy.deepcopy(dist)
            new_dist[sty][stx]=0
            while search:
                tmph,tmpw=search.popleft()
                
                
                
                d=new_dist[tmph][tmpw]
                
                for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
                    new_h=tmph+dy
                    new_w=tmpw+dx
                    if new_h<0 or h<=new_h or new_w<0 or w<=new_w: continue
                    if new_dist[new_h][new_w]==-2:
                        new_dist[new_h][new_w]=d+1
                        search.append((new_h,new_w))
                        ans=max(ans,d+1)
                
                
                
                
        return ans
                
    print(bfs(start,dist)) 
    
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import copy
import sys
sys.setrecursionlimit(1000)
a,b=map(int,input().split())
maze=[list(input()) for i in range(a)]
ans=0
for i in range(a):
  for j in range(b):
    l=copy.deepcopy(maze)
    if l[i][j]!="
      l[i][j]=0
      q=deque([[i,j]])
      while q:
        h,w=q.popleft()
        if 0<=h-1<a and 0<=w<b:
          if l[h-1][w]==".":
            l[h-1][w]=l[h][w]+1
            q.append([h-1,w])
        if 0<=h+1<a and 0<=w<b:
          if l[h+1][w]==".":
            l[h+1][w]=l[h][w]+1
            q.append([h+1,w])
        if 0<=h<a and 0<=w-1<b:
          if l[h][w-1]==".":
            l[h][w-1]=l[h][w]+1
            q.append([h,w-1])
        if 0<=h<a and 0<=w+1<b:
          if l[h][w+1]==".":
            l[h][w+1]=l[h][w]+1
            q.append([h,w+1])
      s=0
      for x in l:
        for y in x:
          if type(y)==int:
            if y>s:
              s=y
      if ans<s:
        ans=s
print(ans)

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

INF = 1001001001
di = [-1,0,1,0]
dj = [0,-1,0,1]
ans = 0

def update(i, j, x):
    if dist[i][j] != INF: return
    dist[i][j] = x
    que.put([i,j])

import queue


for si in range(h):
    for sj in range(w):
        if s[si][sj] == '
        dist = [[INF]*w for i in range(h)]
        que = queue.Queue()
        update(si, sj, 0)
        while que.qsize():
            p = que.get()
            i = p[0]; j = p[1]
            for drc in range(4):
                ni = i+di[drc]; nj = j+dj[drc]
                if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                if s[ni][nj] == '
                update(ni, nj, dist[i][j]+1)
        
        for i in range(h):
            for j in range(w):
                if dist[i][j] == INF: continue
                ans = max(ans, dist[i][j])

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def bfs(start):
    que=deque([start])
    D=[-1]*(h*w)
    D[start]=0
    while que:
        x=que.popleft()
        for next_x in (x+1,x-1,x+w,x-w):
            if maze[next_x]=='.' and D[next_x]==-1:
                D[next_x]=D[x]+1
                que.append(next_x)
    return max(D)

def main():
    global h,w,maze
    h,w=map(int,input().split())
    h+=2
    w+=2
    maze="
    for _ in range(h-2):
        maze+="
    maze+="
    print(max(bfs(i) for i,c in enumerate(maze) if c=='.'))


if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def bfs(start):
    que=deque([start])
    D=[-1]*(h*w)
    D[start]=0
    while que:
        x=que.popleft()
        for next_x in (x+1,x-1,x+w,x-w):
            if maze[next_x]=='.' and D[next_x]==-1:
                D[next_x]=D[x]+1
                que.append(next_x)
    return max(D)

def main():
    global h,w,maze
    h,w=map(int,input().split())
    h+=2
    w+=2
    maze="
    for _ in range(h-2):
        maze+="
    maze+="
    print(max(bfs(i) for i,c in enumerate(maze) if c=='.'))


if __name__=='__main__':
    main()

Solution (Python):
from collections import deque

def bfs(meiro, start_x, start_y):
    visited = []
    for i in range(len(meiro)):
        visited.append([])
        for j in range(len(meiro[i])):
            visited[i].append(0)

    stack = deque()
    stack.append([start_x, start_y])
    visited[start_x][start_y] = 0
    max_distance = 0
    while len(stack) != 0:
        x, y = map(int, stack.popleft())
        distance = visited[x][y]
        for items in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
            x_n = x + items[0]
            y_n = y + items[1]
            if x_n < 0 or x_n >= H or y_n < 0 or y_n >= W or (start_x == x_n and start_y == y_n) or visited[x_n][y_n] != 0 or meiro[x_n][y_n] == "
                continue
            stack.append([x_n, y_n])
            visited[x_n][y_n] = distance+1
            if max_distance < distance+1:
                max_distance = distance+1
    return max_distance

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

max_dist = 0
for h in range(H):
    for w in range(W):
        if meiro[h][w] == ".":
            dis = bfs(meiro, h, w)
            if max_dist < dis:
                max_dist = dis
print(max_dist)