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

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

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            continue

        q = [(0, (i, j))]
        mins = [[h * w for _ in range(w)] for _ in range(h)]
        visited = [[0 for _ in range(w)] for _ in range(h)]
        while len(q) > 0:
            c, (x, y) = heapq.heappop(q)
            ans = max(ans, c)
            if visited[x][y]:
                continue
            visited[x][y] = True
            for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                if nx < 0 or nx >= h or ny < 0 or ny >= w or s[nx][ny] == '
                    continue
                if visited[nx][ny]:
                    continue
                if mins[nx][ny] > c + 1:
                    mins[nx][ny] = c + 1
                    heapq.heappush(q, (c + 1, (nx, ny)))

print(ans)

Solution (Python):

def main():
    from collections import deque
    import numpy as np

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

    move = ((0, 1), (0, -1), (1, 0), (-1, 0))
    seen = [[False] * W for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if S[sh][sw] == '
                continue
            seen[sh][sw] = True
            queue = deque([(sh, sw)])
            
            distance = np.full((H, W), -1, dtype=np.int16)
            distance[sh, sw] = 0
            while queue:
                h, w = queue.popleft()
                for dh, dw in move:
                    nh = h + dh
                    nw = w + dw
                    if (1
                            and 0 <= nh < H
                            and 0 <= nw < W
                            and S[nh][nw] == '.'
                            and distance[nh][nw] == -1):
                        distance[nh][nw] = distance[h][w] + 1
                        queue.append((nh, nw))
            ans = max(ans, distance.max())
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
h, w = map(int,input().split())
maze = [[i for i in input()] for _ in range(h)] 
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def bfs(i, j):
  dist = [[-1] * w for _ in range(h)]
  d = deque()
  d.append((i, j))
  dist[i][j] = 0
  ret = 0
  while d:
    x, y = d.popleft()
    for m in move:
      i = x + m[0]
      j = y + m[1]
      if i >=0 and i < h and j >= 0 and j < w:
        if maze[i][j] == "
          continue
        if dist[i][j] != -1:
          continue
        dist[i][j] = dist[x][y] + 1
        d.append((i, j))
  for i in range(h):
    for j in range(w):
      if ret < dist[i][j]:
        ret = dist[i][j]
  return ret

ans = 0
for i in range(h):
  for j in range(w):
    if maze[i][j] == "
      continue
    d = bfs(i, j)
    if ans < d:
      ans = d

print(ans)

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

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

Solution (Python):
from copy import deepcopy
from collections import deque
h,w = map(int,input().split())
s = [['
for i in range(h):
    x = input()
    for j in range(w):
        s[i+1][j+1] = x[j]
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] != '
            maze = deepcopy(s)
            maze[i][j] = 0
            queue = deque([[i,j]])
            while queue:
                x,y = queue.popleft()
                for a,b in([0,-1],[0,1],[1,0],[-1,0]):
                    nh,nw = x+a,y+b
                    if maze[nh][nw] == '.':
                        maze[nh][nw] = maze[x][y] + 1
                        queue.append([nh,nw])
            l = 0
            for x in range(1,h+1):
                for y in range(1,w+1):
                    if maze[x][y] != '
                        l = max(l,maze[x][y])
            ans = max(ans,l)
print(ans)

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

def bfs(h, w):
    checked = [[False for i in range(W)] for j in range(H)]
    q = [(h, w, 0)] if s[h][w] == '.' else []
    checked[h][w] = True
    g_n = 0
    while q:
        h_, w_, n = q.pop(0)
        g_n = max(n, g_n)
        for i, j in zip([0,0,-1,1],[-1,1,0,0]):
            if (0 <= h_+i < H) and (0 <= w_+j < W):
                if checked[h_+i][w_+j]: continue
                checked[h_+i][w_+j] = True
                if s[h_+i][w_+j] == '.': q.append((h_+i, w_+j, n+1))
    return g_n

n = 0
for i in range(H):
    for j in range(W):
        n = max(n, bfs(i,j))

print(n)

Solution (Python):
from collections import *
from copy import *
H,W = map(int,input().split())
S = [(W+2)*["
D = [[1,0],[-1,0],[0,1],[0,-1]]
ans = 0
P = deque([])
Q = deque([])
 
for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]==".":
      P+=[[h,w]]
 
while P:
  T = deepcopy(S)
  sx,sy = P.popleft()
  T[sx][sy] = 0
  Q = deque([[sx,sy]])
  while Q:
    x,y = Q.popleft()
    for dx,dy in D:
      if T[x+dx][y+dy]==".":
        T[x+dx][y+dy] = T[x][y]+1
        Q+=[[x+dx,y+dy]]
        ans = max(ans,T[x+dx][y+dy])
 
print(ans)

Solution (Python):
from collections import *
from copy import *
H,W = map(int,input().split())
S = [(W+2)*["
D = [[1,0],[-1,0],[0,1],[0,-1]]
ans = 0
P = deque([])
Q = deque([])
 
for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]==".":
      P+=[[h,w]]
 
while P:
  T = deepcopy(S)
  sx,sy = P.popleft()
  T[sx][sy] = 0
  Q = deque([[sx,sy]])
  while Q:
    x,y = Q.popleft()
    for dx,dy in D:
      if T[x+dx][y+dy]==".":
        T[x+dx][y+dy] = T[x][y]+1
        Q+=[[x+dx,y+dy]]
        ans = max(ans,T[x+dx][y+dy])
 
print(ans)

Solution (Python):

h,w = map(int,input().split())
l = [['
for i in range(h):
    l.append(['
l.append(['

def id(x,y):
    return x*w+y

INF = 1<<29
dp = [[INF]*500 for _ in range(500)]
for i in range(500):
    dp[i][i] = 0


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

for i in range(1,h+1):
    for j in range(1,w+1):
        if l[i][j]=='
            continue
        for dir in directions:
            ni = i+dir[0]
            nj = j+dir[1]
            if l[ni][nj] == '
                continue
            dp[id(i-1,j-1)][id(ni-1,nj-1)] = 1
            dp[id(ni-1,nj-1)][id(i-1,j-1)] = 1

for k in range(h*w):
    for i in range(h*w):
        for j in range(h*w):
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])

ans = 0
for si in range(h):
    for sj in range(w):
        if l[si+1][sj+1] == '
            continue
        for gi in range(h):
            for gj in range(w):
                if l[gi+1][gj+1] == '
                    continue
                ans = max(ans,dp[id(si,sj)][id(gi,gj)])
print(ans)

Solution (Python):
h,w = [int(i) for i in input().split()]
a = [[False for i in range(w)] for j in range(h)]


for i in range(h):
	v = input()
	for j in range(w):
		if v[j]=='.':
			a[i][j]=True
		else:
			a[i][j]=False

res = 0
ok = [[False for i in range(w)] for j in range(h)]
def bfs(x, y, d):
	q = []
	q.append((x,y,d))
	
	global res
	global ok

	while not len(q)==0:
		x, y, d = q[0]
		q.pop(0)

		if a[x][y] and not ok[x][y]:
			res = max(res, d)
			ok[x][y]=True

			if x-1>=0:
				q.append((x-1,y,d+1))
			if y-1>=0:
				q.append((x,y-1,d+1))
			if x+1<h:
				q.append((x+1,y, d+1))
			if y+1<w:
				q.append((x,y+1, d+1))


for i in range(h):
	for j in range(w):
		ok = [[False for i in range(w)] for j in range(h)]
		bfs(i,j,0)

print(res)

Solution (Python):
from collections import deque
import copy

h,w = map(int,input().split())
l = [['
for i in range(h):
    l.append(['
l.append(['

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

for i in range(1,h+1):
    for j in range(1,w+1):
        visited = copy.deepcopy(l)
        if visited[i][j]=='.':
            visited[i][j] = 0
            que = deque([(i,j)])
            while que:
                v = que.popleft()
                for dir in directions:
                    nv = (v[0]+dir[0],v[1]+dir[1])
                    if visited[nv[0]][nv[1]] == '.':
                        times = visited[v[0]][v[1]]+1
                        visited[nv[0]][nv[1]] = times
                        que.append(nv)
                        ans = max(times,ans)
            

print(ans)

Solution (Python):
from copy import deepcopy
from collections import deque
from itertools import product
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid]) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def longest_path(grid, root):
    def restore_path(prev, p):
        A = deque()
        while p:
            A.appendleft(p)
            p = prev[p]
        return list(A)
    
    x, y = root
    prev = {root:None}
    grid[y, x] = '!'
    queue = deque([root])
    while queue:
        x, y = queue.popleft()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'sg.':
                prev[nx, ny] = x, y
                queue.append((nx, ny))
                grid[ny, nx] = '!'
    return restore_path(prev, (x, y))

h, w = map(int, input().split())
grid = Grid([input() for s in range(h)])
ans = 0
for y, x in product(range(h), range(w)):
    if grid[y, x] == '.':
        path = longest_path(deepcopy(grid), (x, y))
        ans = max(ans, len(path)-1)
print(ans)

Solution (Python):
from copy import deepcopy
from collections import deque
from itertools import product
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid]) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def longest_path(grid, root):
    def restore_route(prev, p):
        A = deque()
        while p:
            A.appendleft(p)
            p = prev[p]
        return list(A)
    
    x, y = root
    prev = {root:None}
    grid[y, x] = '!'
    queue = deque([root])
    while queue:
        x, y = queue.popleft()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'sg.':
                prev[nx, ny] = x, y
                queue.append((nx, ny))
                grid[ny, nx] = '!'
    return restore_route(prev, (x, y))

h, w = map(int, input().split())
grid = Grid([input() for s in range(h)])
ans = 0
for y, x in product(range(h), range(w)):
    if grid[y, x] == '.':
        path = longest_path(deepcopy(grid), (x, y))
        ans = max(ans, len(path)-1)
print(ans)

Solution (Python):
import math , sys

H,W = list(map( int, input().split() ))
maze = []
for i in range(H):
    maze.append(input())
if H==1:
    print(W-1)
    sys.exit()
if W ==1:
    print(H-1)
    sys.exit()

di = [(-1,0),(1,0),(0,1),(0,-1)]
"""
def sol(s,g):
    h = s[0] ; w = s[1]
    gh, gw = g
    d = [[math.inf for _ in range(W)] for _ in range(H)]
    cand = []
    dis = 0
    while True:
        for each in di:
            dh , dw = each
            if h + dh>=0 and h + dh<H and w + dw>=0 and w + dw<W and maze[h+dh][w+dw]=="." and d[h+dh][w+dw]>dis+1:
                cand.append((h+dh, w+dw))
                d[h+dh][w+dw] = dis +1
        if len(cand)==0:
            break
        h , w =cand.pop(0)
        dis = d[h][w]
    return d[g[0]][g[1]]
"""
ans = 0
for h in range(H):
    for w in range(W):
        if maze[h][w]=="
            continue
        d = [[math.inf for _ in range(W)] for _ in range(H)]
        cand = []
        dis = 0
        while True:
            for each in di:
                dh , dw = each
                if h + dh>=0 and h + dh<H and w + dw>=0 and w + dw<W and maze[h+dh][w+dw]=="." and d[h+dh][w+dw]>dis+1:
                    cand.append((h+dh, w+dw))
                    d[h+dh][w+dw] = dis +1
                    ans = max(ans, dis+1)
            
            if len(cand)==0:
                break
            h , w =cand.pop(0)
            dis = d[h][w]

print(ans)

Solution (Python):
from collections import deque

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

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [ [99999999]*w for _ in range(h) ]
            
            dq = deque()
            y=i
            x=j
            d=0
            dist[y][x]=0
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dist[y+m[1]][x+m[0]]=d+1
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            
print(ans)

Solution (Python):


from collections import deque

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


def bfs(sx, sy):
    result = 0
    count = [[-1] * W for i in range(H)]
    count[sx][sy] = 0
    d = deque()
    d.append((sx, sy))
    while d:
        x, y = d.popleft()
        result = count[x][y]
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            tx, ty = x + i, y + j
            if (
                not (0 <= tx < H)
                or not (0 <= ty < W)
                or maze[tx][ty] == "
                or count[tx][ty] != -1
            ):
                continue
            else:
                count[tx][ty] = count[x][y] + 1
                d.append((tx, ty))
    return result


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

Solution (Python):

from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)





def LI(): return list(map(int, sys.stdin.buffer.readline().split()))




def I(): return int(sys.stdin.buffer.readline())





def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()




def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')







def IR(n): return [I() for i in range(n)]







def LIR(n): return [LI() for i in range(n)]







def SR(n): return [S() for i in range(n)]







def LSR(n): return [LS() for i in range(n)]







def SRL(n): return [list(S()) for i in range(n)]


h, w = LI()
s = SRL(h)
ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == "
            continue
        v = [[-1] * w for _ in range(h)]
        q = deque()
        q.append((i, j))
        v[i][j] = 1
        goal = tuple()
        while q:
            r, c = q.popleft()
            for x, y in ((1, 0), (-1, 0), (0, -1), (0, 1)):
                if r + x < 0 or r + x > h - 1 or c + y < 0 or c + y > w - 1 or s[r + x][c + y] == "
                    continue
                v[r + x][c + y] = v[r][c] + 1
                q.append((r + x, c + y))
        ans.append(max(chain.from_iterable(v)) - 1)
print(max(ans))

Solution (Python):
import math
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    H, W = read_ints()
    last_S = ''
    INF = 10**9+1
    dist = [
        [INF for _ in range(H*W)] for _ in range(H*W)
    ]
    for i in range(H*W):
        dist[i][i] = 0
    for i in range(H):
        S = input().strip()
        for j in range(W):
            if S[j] == '
                continue
            top = (i-1)*W+j
            left = i*W+j-1
            current = i*W+j
            if j > 0 and S[j-1] == '.':
                dist[left][current] = dist[current][left] = 1
            if i > 0 and last_S[j] == '.':
                dist[top][current] = dist[current][top] = 1
        last_S = S
    for k in range(H*W):
        for i in range(H*W):
            for j in range(H*W):
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
    return max(cell for row in dist for cell in row if cell != INF)


if __name__ == '__main__':
    print(solve())

Solution (Python):
from collections import deque
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]==".":
            cnt=[[-1]*w for _ in range(h)]
            cnt[i][j]=0
            queue=deque()
            queue.append([i,j])
            for k in range(100*h*w):
                if len(queue)==0:
                    break
                num=queue.popleft()
                num1=num[0]
                num2=num[1]
                if num1!=0:
                    if s[num1-1][num2]=="." and cnt[num1-1][num2]==-1:
                        cnt[num1-1][num2]=cnt[num1][num2]+1
                        queue.append([num1-1,num2])
                if num2!=0:
                    if s[num1][num2-1]=="." and cnt[num1][num2-1]==-1:
                        cnt[num1][num2-1]=cnt[num1][num2]+1
                        queue.append([num1,num2-1])
                if num1!=h-1:
                    if s[num1+1][num2]=="." and cnt[num1+1][num2]==-1:
                        cnt[num1+1][num2]=cnt[num1][num2]+1
                        queue.append([num1+1,num2])
                if num2!=w-1:
                    if s[num1][num2+1]=="." and cnt[num1][num2+1]==-1:
                        cnt[num1][num2+1]=cnt[num1][num2]+1
                        queue.append([num1,num2+1])
            cnt2=0
            for k in range(h):
                cnt2=max(cnt2,max(cnt[k]))
            ans=max(ans,cnt2)
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 *
from copy import *
H,W = map(int,input().split())
S = [(W+2)*["
D = [[1,0],[-1,0],[0,1],[0,-1]]
ans = 0
P = deque([])
Q = deque([])

for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]==".":
      P+=[[h,w]]

while P:
  T = deepcopy(S)
  sx,sy = P.popleft()
  T[sx][sy] = 0
  Q = deque([[sx,sy]])
  while Q:
    x,y = Q.popleft()
    for dx,dy in D:
      if T[x+dx][y+dy]==".":
        T[x+dx][y+dy] = T[x][y]+1
        Q+=[[x+dx,y+dy]]
        ans = max(ans,T[x+dx][y+dy])

print(ans)

Solution (Python):
from collections import deque


def main():
    row, col = map(int, input().split())
    S = [list(input()) for _ in range(row)]
    ans = 0

    for r in range(row):
        for c in range(col):
            if S[r][c] == "
                continue
            q = deque()
            q.append((r, c))
            dist = [[-1 for _ in range(col)] for _ in range(row)]
            dist[r][c] = 0

            while q:
                r, c = q.popleft()
                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    nr, nc = r + dr, c + dc
                    if not(0 <= nr < row and 0 <= nc < col):
                        continue
                    if S[nr][nc] == "
                        continue
                    if dist[nr][nc] != -1:
                        continue
                    q.append((nr, nc))
                    dist[nr][nc] = dist[r][c] + 1
                    ans = max(ans, dist[nr][nc])

    print(ans)


if __name__ == "__main__":
    main()

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

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


def bfs(sy, sx):
    reached = [[-1] * W for _ in range(H)]
    reached[sy][sx] = 0
    from collections import deque
    que = deque([[sy, sx]])
    
    while que:
        iy, ix = que.popleft()
        for d in direction:
            tx, ty = ix + d[0], iy + d[1]
            if tx >= W or ty >= H or tx < 0 or ty < 0:
                continue
            if reached[ty][tx] != -1 or maze[ty][tx] == '
                continue
            reached[ty][tx] = reached[iy][ix] + 1
            
            que.append([ty, tx])
    d_max = 0
    for i in range(H):
        for j in range(W):
            d_max = max(d_max,reached[i][j])

    return d_max


ans = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            ans = max(ans, bfs(i, j))









print(ans)

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        


        class Edge():
            

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            
            self.inf=10**20
            self.G = [[] for _ in range(V)] 
            self. _E = 0 
            self._V = V 

        
        def E(self):
            return self._E

        
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):
            
            que = [] 
            d = [self.inf] * self.V()

            
            

            d[s] = 0
            heapq.heappush(que,(0,s)) 

            while len(que)!=0:
                
                cost,v = heapq.heappop(que)

                
                if d[v] < cost:
                    continue

                
                for i in range(len(self.G[v])):
                    e = self.G[v][i] 
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost 

                        
                        

                        heapq.heappush(que,(d[e.to],e.to)) 

            """
            path = []
            pos = g 
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                
                pos = prev[pos]
            path.reverse()
            

            return d
    
    mod=10**9+7
    H,W=MI()
    S=[]
    S.append("
    for i in range(H):
        s="
        S.append(s)
    S.append("
    
    djk=Dijkstra((H+2)*(W+2))
    
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    for i in range(1,H+1):
        for j in range(1,W+1):
            if S[i][j]==".":
                for k in range(4):
                    ii=i+dx[k]
                    jj=j+dy[k]
                    if S[ii][jj]==".":
                        v= (W+2)*i + j
                        nv=(W+2)*ii+jj
                        djk.add2(v,nv,1)
                        
    ans=0
    for i in range((H+2)*(W+2)):
        d=djk.shortest_path(i)
        for di in d:
            if di<=10**10:
                ans=max(ans,di)
                
    print(ans)
            
            
    


main()

Solution (Python):
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

H,W=mint()
S=[input() for _ in range(H)]

ans=0
for s in product(range(H),range(W)):
    if S[s[0]][s[1]]=='
        continue
    q=deque([s])
    d=[[-1]*W for _ in range(H)]
    d[s[0]][s[1]]=0
    while len(q)>0:
        i,j = q.popleft()
        for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
            if 0<=x<H and 0<=y<W and S[x][y]=='.' and d[x][y]<0:
                d[x][y]=d[i][j]+1
                q.append((x,y))
    for i in range(H):
        for j in range(W):
            ans=max(ans,d[i][j])
print(ans)

Solution (Python):
def solve(maze,H, W, S):
    next_set = set()
    next_set.add(S)
    seen = [[False]*W for _ in range(H)]
    n = 0
    while next_set:
        n += 1
        curr_ = list(next_set)
        next_set = set()
        for h, w in curr_:
            if seen[h][w]:
                continue
            seen[h][w] = True
            for nh, nw in maze[h][w]:
                if seen[nh][nw] == False:
                    next_set.add((nh, nw))
    return n-1


H, W = list(map(int, input().split()))
maze = [[[] for _ in range(W)] for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '
            maze[h][w] = False



for h in range(H):
    for w in range(W):
        if maze[h][w] == False:
            continue
        for nh, nw in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
            if 0 <= nh < H and 0<= nw < W:
                if maze[nh][nw] != False:
                    maze[h][w].append((nh, nw))
        

ans = 0
for i in range(H*W-1):
        h = i//W
        w = i%W
        if maze[h][w]:
            ans = max(ans, solve(maze, H, W, (h, w)))

print(ans)