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

def getdistance(row,col,sw,h,w):
    maze = deque([[row,col,0]])
    marker = [[0]*w for _ in range(h)]
    marker[row][col] = 1
    while len(maze)!=0:
        r, c, d = maze.popleft()
        if r!=0:
            if sw[r-1][c]!="
                marker[r-1][c] = 1
                maze.append([r-1,c,d+1])
        if r!=h-1:
            if sw[r+1][c]!="
                marker[r+1][c] = 1
                maze.append([r+1,c,d+1])
        if c!=w-1:
            if sw[r][c+1]!="
                marker[r][c+1] = 1
                maze.append([r,c+1,d+1])
        if c!=0:
            if sw[r][c-1]!="
                marker[r][c-1] = 1
                maze.append([r,c-1,d+1])
    return d
h, w = map(int, input().split())
sw = [input() for _ in range(h)]
ans = 0
for row in range(h):
    for col in range(w):
        if sw[row][col]=="
            continue
        ans = max(ans,getdistance(row,col,sw,h,w))
print(ans)

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):
from collections import deque
H, W = map(int, input().split())
maze = [input() for i in range(H)]

def bfs(maze, sy, sx):
    visited = [[-1]*W for j in range(H)]
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        ans=0
        y, x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1 :
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
                    
    for l in range(H):
        for m in range(W):
            ans = max(ans,visited[l][m])
            
    return ans
        
ma=0
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == ".":
            if bfs(maze,sy,sx) is not None:
                ma = max(bfs(maze, sy, sx),ma)
print(ma)

Solution (Python):
from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '
                continue
            v = set()
            q = deque([(i, j, 0)])
            v.add((i, j))
            while q:
                ii, jj, cnt = q.popleft()
                ret = max(ret, cnt)
                
                if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                    v.add((ii + 1, jj))
                
                if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                    v.add((ii, jj + 1))
                
                if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                    v.add((ii - 1, jj))
                
                if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                    q.append((ii, jj - 1, cnt + 1))
                    v.add((ii, jj - 1))
    return ret


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '
                continue
            q = deque([(i, j, 0)])
            v = [[0] * w for _ in range(h)]
            v[i][j] = 1
            while q:
                ii, jj, cnt = q.popleft()
                ret = max(ret, cnt)
                
                if ii < h - 1 and g[ii + 1][jj] == '.' and v[ii + 1][jj] == 0:
                    v[ii + 1][jj] = 1
                    q.append((ii + 1, jj, cnt + 1))
                
                if jj < w - 1 and g[ii][jj + 1] == '.' and v[ii][jj + 1] == 0:
                    v[ii][jj + 1] = 1
                    q.append((ii, jj + 1, cnt + 1))
                
                if ii > 0 and g[ii - 1][jj] == '.' and v[ii - 1][jj] == 0:
                    v[ii - 1][jj] = 1
                    q.append((ii - 1, jj, cnt + 1))
                
                if jj > 0 and g[ii][jj - 1] == '.' and v[ii][jj - 1] == 0:
                    v[ii][jj - 1] = 1
                    q.append((ii, jj - 1, cnt + 1))
    return ret


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


def bfs(y, x):
    dist = [[-1] * w for _ in range(h)]
    dist[y][x] = 0
    que, frag = deque([(x, y)]), set([(x, y)])

    while que:
        qx, qy = que.popleft()
        near = [(-1, 0), (0, -1), (1, 0), (0, 1)]
        for i, j in near:
            i, j = qx + i, qy + j
            if (i, j) in frag:
                continue
            if 0 <= i < w and 0 <= j < h and s[j][i] == '.':
                dist[j][i] = dist[qy][qx] + 1
                que.append((i, j)), frag.add((i, j))
    return dist[qy][qx]


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

ans = 0
for i, si in enumerate(s):
    for j, sij in enumerate(si):
        if sij == '.':
            ans = max(ans, bfs(i, j))
print(ans)

Solution (Python):
from collections import deque


def bfs(y, x):
    dist = [[-1] * w for _ in range(h)]
    dist[y][x] = 0
    que, frag = deque([(x, y)]), set([(x, y)])

    while que:
        qx, qy = que.popleft()
        near = [(qx - 1, qy), (qx, qy - 1), (qx + 1, qy), (qx, qy + 1)]
        for i, j in near:
            if (i, j) in frag:
                continue
            if 0 <= i < w and 0 <= j < h and s[j][i] == '.':
                dist[j][i] = dist[qy][qx] + 1
                que.append((i, j)), frag.add((i, j))
    return dist[qy][qx]


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

ans = 0
for i, si in enumerate(s):
    for j, sij in enumerate(si):
        if sij == '.':
            ans = max(ans, bfs(i, j))
print(ans)

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

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

ans = 0
for x in range(H):
    for y in range(W):
        
        if maze[x][y] == "
            continue

        distance = [[-1]*W for _ in range(H)]
        distance[x][y] = 0
        
        stack = deque([[x,y]])

        while stack:
            h,w = stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h, new_w = h+i, w+j
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue
                elif maze[new_h][new_w] != "
                    distance[new_h][new_w] = distance[h][w]+1
                    stack.append([new_h, new_w])

        ans = max(ans, np.max(distance))

print(ans)

Solution (Python):

import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
def input(): return sys.stdin.readline()[:-1] 


import string

from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
MOD = int(1e9)+7
INF = float('inf')


def solve():
    n, m = [int(x) for x in input().split()]
    a = []
    starts = []
    for i in range(n):
        a.append(input())
        for j in range(m):
            if a[i][j] == '.':
                starts.append((i, j))

    def bfs(v):
        q = deque([(v, 0)])
        mx = 0
        mv = v
        w = defaultdict(int)
        w[v] = 1
        while q:
            v, d = q.popleft()
            if d > mx:
                mv = v
                mx = d
            i, j = v
            for x, y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                if 0 <= i + x < n and 0 <= j + y < m and not w[(i+x,j+y)] and a[i+x][j+y] == '.':
                    w[(i+x,j+y)] = 1
                    q.append(((i+x, j+y), d + 1))
            

        return mx, mv

    ans = 0
    for start in starts:
        _, start = bfs(start)
        cur, start = bfs(start)

        ans = max(ans, cur)
    print(ans)


    

t = 1

for case in range(1,t+1):
    ans = solve()


"""
1
4
-1 1 1 -1

"""

Solution (Python):
from collections import deque

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

dis = [[0, 1], [0, -1], [1, 0], [-1, 0]]
answer = 0
for h in range(H):
  for w in range(W):
    if mazes[h][w] == '
      continue
    else:
      last = 0
      arrived = [[0 for _ in range(W)] for __ in range(H)]
      routes = deque([[h, w]])
      arrived[h][w] = 1
      while(len(routes) > 0):
        hy, wx = routes.pop()
        move = arrived[hy][wx]
        last = move
        for y, x in dis:
          if 0 <= hy+y < H and 0 <= wx+x < W and mazes[hy+y][wx+x] == '.' and arrived[hy+y][wx+x] == 0:
            routes.appendleft([hy+y, wx+x])
            arrived[hy+y][wx+x] = move + 1
      answer = max(answer, last-1)
print(answer)

Solution (Python):

"""
Created on Tue Sep  8 18:25:14 2020

@author: liang
"""

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

field = [input() for i in range(H)]

def Init():
    return [[-1]*W for _ in range(H)]

ans = -1

from collections import deque
q = deque()
adj = ((1,0), (-1,0), (0,1), (0,-1))
def BFS(y,x):
    def isValid(t):
        if t[0] < 0 or t[0] >= H or t[1] < 0 or t[1] >= W or field[t[0]][t[1]] == "
            return False
        return True
    d = Init()
    if field[y][x] == '
        return -1
    d[y][x] = 0
    q.append((y,x))
    res = 0
    while q:
        cur = q.popleft()
        for a in adj:
            nex = (cur[0]+a[0], cur[1]+a[1])
            if isValid(nex) and (d[nex[0]][nex[1]]== -1 or d[nex[0]][nex[1]] > d[cur[0]][cur[1]]+1):
                d[nex[0]][nex[1]] = d[cur[0]][cur[1]]+1
                
                
                res = max(res, d[nex[0]][nex[1]])
                q.append(nex)
    return res

for i in range(H):
    for j in range(W):
        tmp = BFS(i,j)
        if tmp > ans:
            ans = tmp
print(ans)

Solution (Python):

"""
Created on Tue Sep  8 18:25:14 2020

@author: liang
"""

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

field = [input() for i in range(H)]

def Init():
    return [[-1]*W for _ in range(H)]

ans = -1

from collections import deque
q = deque()
adj = ((1,0), (-1,0), (0,1), (0,-1))
def BFS(y,x):
    def isValid(t):
        if t[0] < 0 or t[0] >= H or t[1] < 0 or t[1] >= W or field[t[0]][t[1]] == "
            return False
        return True
    d = Init()
    if field[y][x] == '
        return -1
    d[y][x] = 0
    q.append((y,x))
    res = 0
    while q:
        cur = q.popleft()
        for a in adj:
            nex = (cur[0]+a[0], cur[1]+a[1])
            if isValid(nex) and (d[nex[0]][nex[1]]== -1 or d[nex[0]][nex[1]] > d[cur[0]][cur[1]]+1):
                d[nex[0]][nex[1]] = d[cur[0]][cur[1]]+1
                if res < d[nex[0]][nex[1]]:
                    res = d[nex[0]][nex[1]]
                q.append(nex)
    return res

for i in range(H):
    for j in range(W):
        tmp = BFS(i,j)
        if tmp > ans:
            ans = tmp
print(ans)

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

    from collections import deque

    h, w = map(int, readline().split())
    s = [readline().rstrip().decode('utf-8') for _ in range(h)]

    l = []
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                l.append((i, j))
    dire = ((0, 1), (0, -1), (1, 0), (-1, 0))
    q = deque()
    ans = 0
    for hh, ww in l:
        q.appendleft((hh, ww, 0))
        c = [[0]*w for _ in range(h)]
        while q:
            ha, wa, ca = q.pop()
            if c[ha][wa] == 0:
                c[ha][wa] = 1
                ans = max(ans, ca)
                for dh, dw in dire:
                    hdh, wdw = ha+dh, wa+dw
                    if 0 <= hdh < h and 0 <= wdw < w:
                        if s[hdh][wdw] == '.' and c[hdh][wdw] == 0:
                            q.appendleft((hdh, wdw, ca+1))
    print(ans)

main()

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

    from collections import deque

    h, w = map(int, readline().split())
    s = ['

    l = []
    for i in range(h+2):
        for j in range(w+2):
            if s[i][j] == '.':
                l.append((i, j))
    dire = ((0, 1), (0, -1), (1, 0), (-1, 0))
    q = deque()
    ans = 0
    for hh, ww in l:
        q.appendleft((hh, ww, 0))
        c = [[0]*(w+2) for _ in range(h+2)]
        while q:
            ha, wa, ca = q.pop()
            if c[ha][wa] == 0:
                c[ha][wa] = 1
                ans = max(ans, ca)
                for dh, dw in dire:
                    hdh, wdw = ha+dh, wa+dw
                    if s[hdh][wdw] == '.' and c[hdh][wdw] == 0:
                        q.appendleft((hdh, wdw, ca+1))
    print(ans)

main()

Solution (Python):
def main():
	H, W = [int(x) for x in input().split(" ")]
	S = []
	S.append(["X"] * (W + 2))
	h = 0
	w = 0
	for i in range(H):
		row = list(input())
		S.append(["X"] + row + ["X"])
		if not h and not w and row.count(".") > 0:
			h = i + 1
			w = row.index(".") + 1
	S.append(["X"] * (W + 2))

	ans = []
	for i in range(H):
		for j in range(W):
			ans.append(BFS(S, i + 1, j + 1, H + 2, W + 2))
	print(max(ans))

def BFS(M, i, j, H, W):
	if M[i][j] != ".":
		return 0
	to_visit = [{"row": i, "col": j, "step": 0}]
	checked = [[0] * W for x in range(H)]
	checked[i][j] = 1
	z = [[0] * W for x in range(H)]
	while len(to_visit):
		visiting = to_visit.pop(0)
		r0 = visiting["row"]
		c0 = visiting["col"]
		s0 = visiting["step"]
		z[r0][c0] = s0
		for d in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
			r = r0 + d[0]
			c = c0 + d[1]
			s = s0 + 1
			if checked[r][c] == 0 and M[r][c] == ".":
				to_visit.append({"row": r, "col": c, "step": s})
				checked[r][c] = 1
	a = 0
	for i in range(len(z)):
		for j in range(len(z[i])):
			if a < z[i][j]:
				a = z[i][j]
	return a

main()

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    H,W = i_map()
    dy_dx=[[1,0],[0,1],[-1,0],[0,-1]]
    rc=[input() for i in range(H)]
    ans = 0

    for sy in range(H):
        for sx in range(W):
            if rc[sy][sx] == "
                continue
            dist=[[-1 for _ in range(W)] for _ in range(H)]
            dist[sy][sx] = 0
            d=deque()
            d.append([sx,sy])
            while d:
                nx, ny = d.popleft()
                for dy,dx in dy_dx:
                    y,x = ny+dy,nx+dx
                    if 0<=y<H and 0<=x<W and rc[y][x] != "
                        dist[y][x] = dist[ny][nx] + 1
                        d.append([x,y])
            ans = max(ans, max(list(itertools.chain.from_iterable(dist))))
    print(ans)


if __name__=="__main__":
    main()

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

maze = [[9]*(w+2)]
for i in range(h):
  s = input()
  tmp = [9]
  for j in s:
    if j == "
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+2))


def bfs(start):
  maze2 = copy.deepcopy(maze)
  
  pos = [start]
  max_depth = 0
  maze2[start[0]][start[1]] = 2
  while len(pos):
    x, y, depth = pos.pop(0)
    max_depth = max(depth, max_depth)
    
    if maze2[x-1][y] < 2:
      pos.append([x-1,y,depth + 1])
      maze2[x-1][y] = 2
    if maze2[x+1][y] < 2:
      pos.append([x+1,y,depth + 1])
      maze2[x+1][y] = 2
    if maze2[x][y-1] < 2:
      pos.append([x,y-1,depth +1])
      maze2[x][y-1] = 2
    if maze2[x][y+1] < 2:
      pos.append([x,y+1,depth +1])
      maze2[x][y+1] = 2
  return max_depth

ans = 0
for i in range(h):
  for j in range(w):
      start = [i+1,j+1,0]
      maze2 = maze
      if maze[i+1][j+1] != 9:
        
        ans = max(ans,bfs(start))
print(ans)

Solution (Python):
from collections import deque

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

sl = []
flag = False
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            sl.append([i, j])

q = deque()
dire = [(0, 1), (0, -1), (1, 0), (-1, 0)]
ans = 0
for sh, sw in sl:
    c = [[0]*w for _ in range(h)]
    q.append((sh, sw, 0))
    while q:
        ph, pw, k = q.pop()
        if c[ph][pw] == 0:
            ans = max(ans, k)
            c[ph][pw] = 1
            for dh, dw in dire:
                hdh, wdw = ph+dh, pw+dw
                if 0 <= hdh < h and 0 <= wdw < w and c[hdh][wdw] == 0:
                    if s[hdh][wdw] == '.':
                        q.appendleft((hdh, wdw, k+1))

print(ans)

Solution (Python):
from collections import deque

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

sl = []
flag = False
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            sl.append([i, j])

q = deque()
dire = [(0, 1), (0, -1), (1, 0), (-1, 0)]
ans = 0
for sh, sw in sl:
    c = [[0]*w for _ in range(h)]
    q.append((sh, sw, 0))
    while q:
        ph, pw, k = q.pop()
        if c[ph][pw] == 0:
            ans = max(ans, k)
            c[ph][pw] = 1
            for dh, dw in dire:
                hdh, wdw = ph+dh, pw+dw
                if 0 <= hdh < h and 0 <= wdw < w and c[hdh][wdw] == 0:
                    if s[hdh][wdw] == '.':
                        q.appendleft((hdh, wdw, k+1))

print(ans)

Solution (Python):
from collections import deque

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

ans = 0

for startx in range(w):
    for starty in range(h):
        if grid[starty][startx] == "
            continue

        dist = [[10000]*w for _ in range(h)]
        dist[starty][startx] = 0
        maxDist = 0

        q = deque([(startx, starty)])

        while q:
            curx, cury = q.popleft()

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

            for xo, yo in adj:
                x, y = curx + xo, cury + yo

                if x < 0 or x >= w or y < 0 or y >= h:
                    continue
                if grid[y][x] == "
                    continue

                newDist = dist[cury][curx] + 1
                if newDist < dist[y][x]:
                    dist[y][x] = newDist
                    q.append((x, y))

                    maxDist = max(maxDist, newDist)

        ans = max(ans, maxDist)

print(ans)

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

def bfs(start):
    already = {}
    queue = []
    counter = 0
    queue.append((start[0], start[1], 0))
    already[start] = True
    max_depth = 0
    while counter < len(queue):
        y, x, depth = queue[counter]
        if depth > max_depth:
            max_depth = depth
        for move in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            new_y = y + move[0]
            new_x = x + move[1]
            if new_y >= 0 \
            and new_y < H \
            and new_x >= 0 \
            and new_x < W \
            and S[new_y][new_x] == '.' \
            and (new_y, new_x) not in already:
                already[(new_y, new_x)] = True
                queue.append((new_y, new_x, depth+1))
        counter += 1
    return max_depth

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue
        depth = bfs((i, j))
        if answer < depth:
            answer = depth
print(answer)

Solution (Python):




import sys
from io import StringIO
import unittest
import copy
from collections import deque

def yn(b):
    print("Yes" if b==1 else "No")
    return

def sagasu(h,w,mp,sh,sw):
    d = deque()
    x=sw
    y=sh
    d.append([y,x,0])
    while len(d)>0:
        y,x,cnt=d.popleft()
        if mp[y][x]==-2 or mp[y][x] > cnt:
            mp[y][x]=cnt
            nxt=[[y-1,x],[y+1,x],[y,x-1],[y,x+1]]
            for nx in nxt:
                y2=nx[0]
                x2=nx[1]
                if y2 < 0:
                    continue
                if y2 >= h:
                    continue
                if x2 < 0:
                    continue
                if x2 >= w:
                    continue
                if mp[y2][x2] == -2 or mp[y2][x2] > cnt:
                    d.append([y2,x2,cnt+1])
    ret=-1
    for y in range(h):
        for x in range(w):
            ret=max(ret,mp[y][x])
    return ret
def resolve():
    readline=sys.stdin.readline

    h,w=map(int, readline().rstrip().split())

    mp=[[0 for i in range(w)] for j in range(h)]
    for y in range(h):
        ss=readline().rstrip()
        for x in range(w):
            if ss[x]=="
                mp[y][x]=-1 
            else:
                mp[y][x]=-2 
    ans=0
    for y in range(h):
        for x in range(w):
            if mp[y][x]==-2:
                mp2=copy.deepcopy(mp)
                n=sagasu(h,w,mp2,y,x)
                ans=max(ans,n)
    print(ans)
    
    
    
    
    

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

Solution (Python):
import queue
import numpy as np

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


def solveMaze(s):
    q = queue.Queue()
    q.put([s[0],s[1],0])
    times = [[999999999 for j in range(W)] for i in range(H)]
    tmpAns = 0
    times[s[0]][s[1]] = 0
    while not q.empty():
        now = q.get()
        tmpAns = max(tmpAns, now[2])
        for i in range(4):
            nextH = now[0] + int(dir4[i][0])
            nextW = now[1] + int(dir4[i][1])
            nextTime = now[2] + 1

            if nextH < 0 or nextH >= H or nextW < 0 or nextW >=W or maze[nextH][nextW] == "
                continue
            else:
                times[nextH][nextW] = nextTime
                q.put([nextH, nextW, nextTime])

    return tmpAns


ans = 0

for sH in range(H):
    for sW in range(W):
        if maze[sH][sW] == ".":
            ans = max(ans, solveMaze([sH, sW]))

print(ans)

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

inf=1000000000
field=[]
for i in range(H):
  row=list(input())
  for j in range(len(row)):
    if row[j]=='
    else:row[j]=inf
  field.append(row)
ans=inf

def isIn(x,y):
  if x<0 or x>=W:return False
  if y<0 or y>=H:return False
  return True
vector=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
for i in range(H):
  for j in range(W):
    if field[i][j]==-1:continue
    l=deque([[j,i]])
    f=copy.deepcopy(field)
    f[i][j]=0
    tmp=0
    
    while l:
      x,y=l.popleft()
      
      
      for v in vector:
        if not isIn(x+v[1],y+v[0]):continue
        if f[y+v[0]][x+v[1]]<=tmp:continue
        f[y+v[0]][x+v[1]]=f[y][x]+1
        l.append([x+v[1],y+v[0]])
        tmp=max(f[y+v[0]][x+v[1]],tmp)
    ans=max(ans,tmp)
print(ans)

Solution (Python):
import collections
q=collections.deque()
h,w=map(int,input().split())
S=[]
for _ in range(h):
    s=input()
    S.append(s)
went=[[0]*w for _ in range(h)]
l=[]
def walk(x,y):
    if x<=h-2:
        if S[x+1][y]=='.' and (x+1,y)!=(ih,iw) and went[x+1][y]==0 or went[x+1][y]>went[x][y]+1:
            went[x+1][y]=went[x][y]+1
            q.append((x+1,y))
    if y<=w-2:
        if S[x][y+1]=='.' and (x,y+1)!=(ih,iw) and went[x][y+1]==0 or went[x][y+1]>went[x][y]+1:
            went[x][y+1]=went[x][y]+1
            q.append((x,y+1))
    if y>=1:
        if S[x][y-1]=='.' and (x,y-1)!=(ih,iw) and went[x][y-1]==0 or went[x][y-1]>went[x][y]+1:
            went[x][y-1]=went[x][y]+1
            q.append((x,y-1))
    if x>=1:
        if S[x-1][y]=='.' and (x-1,y)!=(ih,iw) and went[x-1][y]==0 or went[x-1][y]>went[x][y]+1:
            went[x-1][y]=went[x][y]+1
            q.append((x-1,y))
        
for ih in range(h):
    for iw in range(w):
        if S[ih][iw]=='.':
            went=[[0]*w for _ in range(h)]
            q.append((ih,iw))
            while q:
                (a,b)=q.pop()
                walk(a,b)
            
            ll=[]
            for i in range(h):
                ll.append(max(went[i]))
            l.append(max(ll))
            
print(max(l))

Solution (Python):
H, W = map(int, input().split())

S = [["
for i in range(H):
    s = input()
    for j in range(W):
        S[i + 1][j + 1] = s[j]


g = H * W

d = [[float("INF")] * g for i in range(g)]
for i in range(g):
    d[i][i] = 0

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if S[i][j] == ".":
            p = (i - 1)*W + (j - 1)
            if S[i][j+1] == ".":
                d[p][p + 1] = 1
            if S[i][j-1] == ".":
                d[p][p - 1] = 1
            if S[i+1][j] == ".":
                d[p][p + W] = 1
            if S[i-1][j] == ".":
                d[p][p - W] = 1

for k in range(g):
    for i in range(g):
        for j in range(g):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0

for i in range(g):
    for j in range(g):
        if d[i][j] != float("INF"):
            ans = max(ans, d[i][j])

print(ans)

Solution (Python):
from collections import deque
import copy

H,W=map(int,input().split())
S=[[x for x in input()] for _ in range(H)]
start_list=[]
length=[[-1]*W for _ in range(H)]
ans=0

for i in range(H):
  for j in range(W):
    if S[i][j]=='.':
      start_list.append((i,j))

for start in start_list:
  h,w=start
  d=deque([(h,w)])
  T=copy.deepcopy(S)
  L=copy.deepcopy(length)
  L[h][w]=0
  T[h][w]='
  while d:
    h,w=d.popleft()
    
    if h-1>=0 and T[h-1][w]=='.':
      d.append((h-1,w))
      L[h-1][w]=L[h][w]+1
      T[h-1][w]='
      ans=max(ans,L[h-1][w])
      
    if h+1<=H-1 and T[h+1][w]=='.':
      d.append((h+1,w))
      L[h+1][w]=L[h][w]+1
      T[h+1][w]='
      ans=max(ans,L[h+1][w])
      
    if w-1>=0 and T[h][w-1]=='.':
      d.append((h,w-1))
      L[h][w-1]=L[h][w]+1
      T[h][w-1]='
      ans=max(ans,L[h][w-1])
      
    if w+1<=W-1 and T[h][w+1]=='.':
      d.append((h,w+1))
      L[h][w+1]=L[h][w]+1
      T[h][w+1]='
      ans=max(ans,L[h][w+1])

print(ans)

Solution (Python):
h,w=map(int,input().split())
m=[]
for i in range(h):
  m.append(list(map(lambda x:int(x=="
m+=[[1 for i in range(w+2)]]*2
mx=0
d=[(1,0),(-1,0),(0,1),(0,-1)]
for x in range(h):
  for y in range(w):
        if m[x][y]:
          continue
        s=[(x,y)]
        c=-1
        v=[[0 for i in range(w)] for i in range(h)]
        v[x][y]=1
        while s:
          ns=[]
          for i in s:
            for j in d:
              if m[i[0]+j[0]][i[1]+j[1]] or v[i[0]+j[0]][i[1]+j[1]]:
                continue
              v[i[0]+j[0]][i[1]+j[1]]=1
              ns.append((i[0]+j[0],i[1]+j[1]))
          s=ns
          c+=1
        mx=max(mx,c)
print(mx)

Solution (Python):
from copy import deepcopy  

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

def now(n,s):
    t = []
    for i in queue:
        j = n[0] + i[0]
        k = n[1] + i[1]
        if 0 <= j < H and 0 <= k < W:
            if s[j][k] == ".":
                t.append([j,k])
                s[j][k] = "
    return [t,s]
        

def bfs(trust, a, s):
    t = []
    for i in trust:
        tt, s = now(i,s)
        t += tt
    if len(t) == 0:
        return a
    else:
        a = a + 1
        return bfs(t, a, s)


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

Solution (Python):
from queue import deque

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

for h in range(H):
  for w in range(W):
    if S[h][w] == ".":
      D = [[-1] * W for _ in range(H)]
      D[h][w] = 0
      Q = deque()
      Q.append((h, w))
      
      while Q:
        y, x = Q.popleft()

        for i, j in (1, 0), (-1, 0), (0, 1), (0, -1):
          y2, x2 = y + i, x + j

          if 0 <= y2 < H and 0 <= x2 < W and S[y2][x2] == "." and D[y2][x2] == -1:
            Q.append((y2, x2))
            D[y2][x2] = D[y][x] + 1

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

print(ans)