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

h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['
for _ in range(h-2):
    MAZE.append('
else:
    MAZE.append('


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


INF = 10**18


def bfs(start):
    i, j = start
    dist = [[INF] * w for _ in range(h)]
    dist[i][j] = 0
    next_v = deque([start])
    while next_v:
        i, j = next_v.popleft()
        direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in direction:
            x, y = i+di, j+dj
            if MAZE[x][y] == "
                continue
            if dist[x][y] <= dist[i][j] + 1:
                continue
            dist[x][y] = dist[i][j] + 1
            next_v.append((x, y))
    return dist


ans = 0
for ls1 in start:
    r = bfs(ls1)
    for ls2 in start:
        ans = max(ans, r[ls2[0]][ls2[1]])

print(ans)

Solution (Python):
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(map(str,input())))

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

def bfs(s):
    MAX = 0
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    goal = s
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for k,d in depth.items():
        if MAX < d:
            MAX = d
            goal = k

    return MAX, goal


for r in range(0,H):
    if "." in MAP[r]:
        start = [r, MAP[r].index(".")]

MAX, goal = bfs(tuple(start))
MAX, _ = bfs(tuple(goal))
print(MAX)
exit()

Solution (Python):
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))

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

def bfs(s):
    global MAX
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for d in depth.values():
        MAX = max(MAX,d)


for i in range(0,H):
    for j in range(0,W):
        if MAP[i][j] == '.':
            bfs(tuple([i,j]))
print(MAX)

Solution (Python):
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))

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

def bfs(s):
    global MAX
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for d in depth.values():
        MAX = max(MAX,d)


for i in range(0,H):
    for j in range(0,W):
        if MAP[i][j] == '.':
            bfs(tuple([i,j]))

for i in range(0,W):
    for j in range(0,H):
        if MAP[j][i] == '.':
            bfs(tuple([j,i]))

print(MAX)

Solution (Python):
"""参考
@drken
2020年02月02日に更新
BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜
https://qiita.com/drken/items/996d80bcae64649a6580
"""
import numpy as np 
from copy import deepcopy,copy
from copy import copy
def Breadth_first_search(start,already_initial):
    already=set()
    already =copy(already_initial)
    already.add(start)    
    now = start
    now_generation =copy(queue_dic[start]) 
    next_preparation =set() 
    count_generation=0
    while len(already) < (H+2)*(W+2):
        for now in now_generation:
            if now in already:          
                continue            
            elif now_generation <= already:   
                already.add(now)
                continue
            else:
                
                already.add(now)
                next_preparation    |= queue_dic[now] 

        now_generation.clear()
        now_generation           |= next_preparation
        next_preparation.clear()
        count_generation +=1
    return count_generation 



H,W = (int(x) for x in input().split())

map_np =np.full((H+2,W+2),"
for i in range(1,H+1):
    S = input()
    S.strip()
    for j in range(1,W+1):
        map_np[i,j]=S[j-1]


queue_dic={(h,w):set()for h in range(1,H+1) for w in range(1,W+1)}
already_initial=set() 
for h in range(H+2):
    for w in range(W+2):
        if map_np[h,w] ==".":
            if map_np[h+1,w] =="." :
                queue_dic[h,w].add((h+1  ,w  ))
            if map_np[h-1,w] =="." :
                queue_dic[h,w].add((h-1  ,w  ))
            if map_np[h,w+1] =="." :
                queue_dic[h,w].add((h    ,w+1))
            if map_np[h,w-1] =="." :
                queue_dic[h,w].add((h    ,w-1))
        else:
            already_initial.add((h,w)) 
grid_all =queue_dic.keys() 
can_pass =grid_all - already_initial  


distance_list =[] 
for start1 in can_pass:
    already1 =set()
    already1=copy(already_initial )
    
    distance_from_start =Breadth_first_search(start1,already_initial)
    distance_list.append(distance_from_start)

print(max(distance_list))

Solution (Python):


import sys


from collections import deque                
















def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    h, w = mi()
    maze = []
    maze.append(['
    for _ in range(h):
        maze.append(['
    maze.append(['

    
    


    def bfs(point_dist):
        'point から BFS を行い最も離れていた点との距離を返す'
        q = deque([point_dist])
        max_distance = 0
        while q:
            point, dist = q.popleft()
            i, j = point
            
            if visited[i][j]:
                continue
            else:
                visited[i][j] = True
            max_distance = max(max_distance, dist)

            tmp = [(i-1, j), (i, j-1), (i, j+1), (i+1, j)]
            for elm in tmp:
                if not visited[elm[0]][elm[1]] and maze[elm[0]][elm[1]] == '.':
                    q.append([elm, dist+1])
        return max_distance



    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if maze[i][j] == '.':
                
                visited = [[False] * (w + 2) for _ in range(h + 2)]
                ans = max(ans, bfs([(i, j), 0]))
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

INF=1001001001

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

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


def bfs(y,x):
  
  
  dx=[1,0,-1,0]
  dy=[0,-1,0,1]
  dist=[[INF for i in range(w)] for j in range(h)]
  dist[y][x]=0
  que=deque()
  que.append([y,x])
  mxd=0
  while que:
    v,u=que.popleft()
    
    for i in range(4):
      ny=v+dy[i]
      nx=u+dx[i]
      
      if 0<=ny<h and 0<=nx<w and maze[ny][nx]=="." and dist[ny][nx]==INF:
        que.append([ny,nx])
        dist[ny][nx]=dist[v][u]+1
        mxd=max(mxd,dist[ny][nx])
  return mxd

ans=0
for i in range(w):
  for j in range(h):
    if maze[j][i]=="
      continue
    d=bfs(j,i)
    
    ans=max(ans,d)
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):

import queue


def getlist():
	return list(map(int, input().split()))

INF = float("inf")

def BFS(H, W, L, start):
	dist = [[INF for i in range(W)] for j in range(H)]
	sy, sx = start
	dist[sy][sx] = 0
	Q = queue.Queue()
	Q.put([sy, sx])
	while not Q.empty():
		y, x = Q.get()
		if y - 1 >= 0:
			if L[y - 1][x] == "." and dist[y - 1][x] > dist[y][x] + 1:
				dist[y - 1][x] = dist[y][x] + 1
				Q.put([y - 1, x])
		if y + 1 <= H - 1:
			if L[y + 1][x] == "." and dist[y + 1][x] > dist[y][x] + 1:
				dist[y + 1][x] = dist[y][x] + 1
				Q.put([y + 1, x])
		if x - 1 >= 0:
			if L[y][x - 1] == "." and dist[y][x - 1] > dist[y][x] + 1:
				dist[y][x - 1] = dist[y][x] + 1
				Q.put([y, x - 1])
		if x + 1 <= W - 1:
			if L[y][x + 1] == "." and dist[y][x + 1] > dist[y][x] + 1:
				dist[y][x + 1] = dist[y][x] + 1
				Q.put([y, x + 1])

	return dist


def main():
	H, W = getlist()
	L = []
	for i in range(H):
		l = list(input())
		L.append(l)

	ans = 0
	for i in range(H):
		for j in range(W):
			if L[i][j] == ".":
				BF = BFS(H, W, L, [i, j])
				for p in range(H):
					for q in range(W):
						if BF[p][q] != INF:
							ans = max(ans, BF[p][q])

	print(ans)


if __name__ == '__main__':
	main()

Solution (Python):

import sys




def solve(H, W, a):
    
    inf = H*W**2
    d = [[inf]*(H*W) for _ in range(H*W)]
    for h in range(H):
        for w in range(W):
            if (a[h][w] == "0"):
                d[h*W+w][h*W+w] = 0
                if (w+1<W)and(a[h][w+1] == "0"):
                    d[h*W+w][h*W+w+1] = 1
                if (h+1<H)and(a[h+1][w] == "0"):
                    d[h*W+w][(h+1)*W+w] = 1
                if (w-1>=0)and(a[h][w-1] == "0"):
                    d[h*W+w][h*W+w-1] = 1
                if (h-1>=0)and(a[h-1][w] == "0"):
                    d[h*W+w][(h-1)*W+w] = 1
                
    

    for k in range(H*W):  
        for st in range(H*W):  
            for ed in range(H*W):  
                d[st][ed] = min(d[st][ed], d[st][k]+d[k][ed])

    

    print(max(*map(lambda x: max([_ if _ != inf else 0 for _ in x ]), d)))
    return

if __name__ == '__main__':
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  

    a = [[_ for _ in next(tokens).replace(".","0").replace("
    solve(H, W, a)

Solution (Python):

import sys




def solve(H, W, a):
    
    inf = H*W**2
    d = [[inf]*(H*W) for _ in range(H*W)]
    for h in range(H):
        for w in range(W):
            if (a[h][w] == "0"):
                d[h*W+w][h*W+w] = 0
                if (w+1<W)and(a[h][w+1] == "0"):
                    d[h*W+w][h*W+w+1] = 1
                if (h+1<H)and(a[h+1][w] == "0"):
                    d[h*W+w][(h+1)*W+w] = 1
                if (w-1>=0)and(a[h][w-1] == "0"):
                    d[h*W+w][h*W+w-1] = 1
                if (h-1>=0)and(a[h-1][w] == "0"):
                    d[h*W+w][(h-1)*W+w] = 1
                
    

    for k in range(H*W):  
        for st in range(H*W):  
            for ed in range(H*W):  
                d[st][ed] = min(d[st][ed], d[st][k]+d[k][ed])

    

    print(max(*map(lambda x: max([_ if _ != inf else -1 for _ in x ]), d)))
    return

if __name__ == '__main__':
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  

    a = [[_ for _ in next(tokens).replace(".","0").replace("
    solve(H, W, a)

Solution (Python):
from collections import deque

def bfs(sy,sx):
    m_dis=0
    
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    visited=[[-1]*yoko for i in range(tate)]
    queue=deque()
    queue.append([sy,sx]) 
    visited[sy][sx]=0 
    while queue:
        y,x=queue.popleft()
        for dy,dx in move:
            my,mx=y+dy,x+dx
            if not(0<=my<tate) or not(0<=mx<yoko):
                continue
            if maze[my][mx]=="." and visited[my][mx]==-1:
                queue.append([my,mx])
                visited[my][mx]=visited[y][x]+1 
                m_dis=visited[my][mx]
        
    return m_dis

tate,yoko=map(int,input().split())
maze=[]
for i in range(tate):
    line=list(input())
    maze.append(line)
ans=0
for y in range(tate):
    for x in range(yoko):
        if maze[y][x]==".":
            ans=max(ans,bfs(y,x))
print(ans)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    from collections import deque
    dy,dx=[1,0,-1,0],[0,1,0,-1]
    def maze_init(grid,road_chr='.',wall_chr='
        H,W=len(grid),len(grid[0])
        if isinstance(grid[0],str):
            grid=[list(row) for row in grid]
        S,G=None,None
        c=[[-1]*(W+2) for _ in range(H+2)]
        for i,row in enumerate(grid,1):
            for j,x in enumerate(row,1):
                if x==road_chr:
                    c[i][j]=0
                elif x==wall_chr:
                    c[i][j]=1
                elif x==start_chr:
                    S=(i,j)
                    c[i][j]=0
                elif x==goal_chr:
                    G=(i,j)
                    c[i][j]=0
        return c,S,G
    def maze_bfs(grid,start_coordinate,road_cost=1,wall_cost=None):
        d=[[INF]*len(grid[0]) for _ in range(len(grid))]
        que=deque()
        que.append((start_coordinate[0],start_coordinate[1]))
        d[start_coordinate[0]][start_coordinate[1]]=0
        while que:
            v=que.popleft()
            for k in range(4):
                nv=(v[0]+dy[k],v[1]+dx[k])
                if grid[nv[0]][nv[1]]==0:
                    if d[nv[0]][nv[1]]>d[v[0]][v[1]]+road_cost:
                        que.append(nv)
                        d[nv[0]][nv[1]]=d[v[0]][v[1]]+road_cost
                elif grid[nv[0]][nv[1]]==1 and wall_cost is not None:
                    if d[nv[0]][nv[1]]>d[v[0]][v[1]]+wall_cost:
                        que.append(nv)
                        d[nv[0]][nv[1]]=d[v[0]][v[1]]+wall_cost
        return d
    
    H,W=map(int,input().split())
    s=[list(input()) for _ in range(H)]
    
    grid,S,G=maze_init(s,road_chr='.',wall_chr='
    
    ans=0
    for i in range(1,H+1):
        for j in range(1,W+1):
            d=maze_bfs(grid,(i,j),road_cost=1,wall_cost=None)
            for k in range(1,H+1):
                for l in range(1,W+1):
                    if grid[i][j]==grid[k][l]==0:
                        ans=max(ans,d[k][l])
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


def bfs(start):
    Q = deque()
    child = deque()
    Q.append(start)
    dist[start[1] - 1][start[0] - 1] = 0
    r = 0

    while Q:
        x, y = Q.popleft()
        x = x - 1
        y = y - 1

        for i in range(4):
            child.clear()
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue
            if G[ny][nx] == "
                continue
            if dist[ny][nx] != -1:
                continue

            child.append((nx + 1, ny + 1))

            if len(child) > 0:
                for c in child:
                    dist[c[1] - 1][c[0] - 1] = dist[y][x] + 1
                    Q.append(c)

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

    return r


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

for i in range(H):
    G[i] = list(input())


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

res = 0
for i in range(H):
    for j in range(W):
        if G[i][j] != "
            
            dist = [[-1 for _ in range(W)] for _ in range(H)]
            start = (j + 1, i + 1)
            res = max(res, bfs(start))

print(res)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
square = [list(input()) for i in range(h)]
def bfs(si, sj):
    INF = 100
    que = deque([(si, sj)])
    d = [[INF] * w for i in range(h)]
    d[si][sj] = 0
    move = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    while que:
        i, j = que.popleft()
        for mi, mj in move:
            ni, nj = i + mi, j + mj
            if 0 <= ni < h and 0 <= nj < w and square[ni][nj] == '.' and d[ni][nj] == INF:
                que.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

max_num = 0
for i in range(h):
    for j in range(w):
        if square[i][j] == '.':
            max_ij = bfs(i, j)
            max_num = max(max_num, max_ij)
print(max_num)

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

def bfs(y, x):
  q = deque([[y, x]])
  while q:
    y,x = q.popleft()

    for a, b in zip([1,0,-1,0], [0,1,0,-1]):
      if 0 <= y+a < H and 0 <= x+b < W:
        if maze[y+a][x+b] == "." and visted[y+a][x+b] == -1:
          visted[y+a][x+b] = visted[y][x] + 1
          q.append([y+a, x+b])
  return 0

maze = []
dots=[]
for h in range(H):
  maze.append(input())
  for w in range(W):
    if maze[-1][w] == ".":
      dots.append([h, w])

ans=0
for i in range(len(dots)):
  sy = dots[i][0]
  sx = dots[i][1]
  visted = [[-1] * W for _ in range(H)]
  visted[sy][sx]=0
  bfs(sy, sx)
  for g in dots[i+1:]:
    gy = g[0]
    gx = g[1]
    ans = max(ans, visted[gy][gx])

print(ans)

Solution (Python):
from collections import defaultdict
import heapq
import math

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

edges = defaultdict(list)
field = []

for _ in range(H):
    field.append(input())

weight = 1
for i in range(H):
    for j in range(W):
        if j + 1 < W and field[i][j] == '.' and field[i][j + 1] == '.':
            edges[W * i + j].append((W * i + j + 1, weight))
            edges[W * i + j + 1].append((W * i + j, weight))
        if i + 1 < H and field[i][j] == '.' and field[i + 1][j] == '.':
            edges[W * i + j].append((W * (i + 1) + j, weight))
            edges[W * (i + 1) + j].append((W * i + j, weight))


def dijkstra(s):
    que = []
    dist = [float('inf')] * (H * W)
    dist[s] = 0
    heapq.heappush(que, (0, s))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if dist[v] < p[0]:
            continue
        for i in range(len(edges[v])):
            e = edges[v][i]
            if dist[e[0]] > dist[v] + e[1]:
                dist[e[0]] = dist[v] + e[1]
                heapq.heappush(que, (dist[e[0]], e[0]))

    dist = [0 if d == float('inf') else d for d in dist]
    return dist


ans = 0
for i in range(H*W):
    ans = max(ans, max(dijkstra(i)))

print(ans)

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

field = []
dist = [[float('inf')] * (W * H) for h in range(W * H)]

for _ in range(H):
    field.append(input())

weight = 1
for i in range(H):
    for j in range(W):
        if j + 1 < W and field[i][j] == '.' and field[i][j + 1] == '.':
            dist[W * i + j][W * i + j + 1] = weight
            dist[W * i + j + 1][W * i + j] = weight
        if i + 1 < H and field[i][j] == '.' and field[i + 1][j] == '.':
            dist[W * i + j][W * (i + 1) + j] = weight
            dist[W * (i + 1) + j][W * i + j] = weight


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


warshall_floyd(dist)

ans = 0
for i in range(H * W):
    for j in range(i + 1, H * W):
        if dist[i][j] != float('inf'):
            ans = max(ans, dist[i][j])

print(ans)

Solution (Python):
from collections import defaultdict
import heapq
import math

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

edges = defaultdict(list)
field = []

for _ in range(H):
    field.append(input())

weight = 1
for i in range(H):
    for j in range(W):
        if j + 1 < W and field[i][j] == '.' and field[i][j + 1] == '.':
            edges[W * i + j].append((W * i + j + 1, weight))
            edges[W * i + j + 1].append((W * i + j, weight))
        if i + 1 < H and field[i][j] == '.' and field[i + 1][j] == '.':
            edges[W * i + j].append((W * (i + 1) + j, weight))
            edges[W * (i + 1) + j].append((W * i + j, weight))


def dijkstra(s):
    que = []
    dist = [float('inf')] * (H * W)
    dist[s] = 0
    heapq.heappush(que, (0, s))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if dist[v] < p[0]:
            continue
        for i in range(len(edges[v])):
            e = edges[v][i]
            if dist[e[0]] > dist[v] + e[1]:
                dist[e[0]] = dist[v] + e[1]
                heapq.heappush(que, (dist[e[0]], e[0]))

    dist = [0 if d == float('inf') else d for d in dist]
    return dist


ans = 0
for i in range(H*W):
    ans = max(ans, max(dijkstra(i)))

print(ans)

Solution (Python):
def main():
    import numpy as np
    def bfs(S,s,h,w):
        dist = np.ones((h,w))*-1
        dist[s[0],s[1]]=0
        que = [s]
        while len(que)>0:
            v = que.pop(0)
            if v[0]+1<h:
                if S[v[0]+1][v[1]]=='.' and dist[v[0]+1][v[1]] == -1:
                    dist[v[0]+1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]+1,v[1]])
            if v[0]-1>-1:
                if S[v[0]-1][v[1]]=='.' and dist[v[0]-1][v[1]]==-1:
                    dist[v[0]-1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]-1,v[1]])
            if v[1]+1<w:
                if S[v[0]][v[1]+1]=='.' and dist[v[0]][v[1]+1]==-1:
                    dist[v[0]][v[1]+1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]+1])
            if v[1]-1>-1:
                if S[v[0]][v[1]-1]=='.' and dist[v[0]][v[1]-1]==-1:
                    dist[v[0]][v[1]-1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]-1])
        return np.max(dist)

    h,w = map(int,input().split())
    S = []
    for i in range(h):
        S.append(input())
    m = 0
    spot = []
    for i in range(h):
        for j in range(w):
            spot.append([i,j])
    for i in range(len(spot)):
        s = spot[i]
        if S[s[0]][s[1]]=='
            continue
        d = bfs(S,s,h,w)
        if m<d:
            m = d
    print(int(m))


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
h, w = map(int, input().split())
square = [list(input()) for i in range(h)]
def bfs(si, sj):
    que = deque()
    que.append((si, sj))
    d = [[float('inf')] * w for i in range(h)]
    d[si][sj] = 0
    move = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    while que:
        i, j = que.popleft()
        for mi, mj in move:
            ni, nj = i + mi, j + mj
            if 0 <= ni < h and 0 <= nj < w and square[ni][nj] != '
                que.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

max_num = 0
for i in range(h):
    for j in range(w):
        if square[i][j] == '.':
            max_ij = bfs(i, j)
            max_num = max(max_num, max_ij)
print(max_num)

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

maze=[]
for _ in range(h):
    temp=input()
    ary=[]
    for s in temp:
        ary.append(s)
    maze.append(ary)

"""

def DFS(yy,xx):
    global maze,h,w,maze_temp
    kyori=0
    for UDRL in [(0,1),(1,0),(-1,0),(0,-1)]:
        ny=UDRL[0]+yy
        nx=UDRL[1]+xx
        if 0<=ny<h and 0<=nx<w and maze_temp[ny][nx]==".":
            maze_temp[ny][nx]="
            kyori=max(kyori,DFS(ny,nx))
    
    return kyori+1
"""

import queue
from collections import deque







import copy


result=0

for y in range(h):
    for x in range(w):
        fifo = deque([])
        if maze[y][x]==".":
            maze_temp=[[-1]*w for _ in range(h)]
            fifo.append([y,x])
            maze_temp[y][x]=0
            result_temp=0
            while len(fifo)>0:
                temp=fifo.popleft()
                yy=temp[0]
                xx=temp[1]
                for yyy,xxx in [(0,1),(1,0),(-1,0),(0,-1)]:
                    ny=yyy+yy
                    nx=xxx+xx
                    if 0<=ny<h and 0<=nx<w:
                        if maze[ny][nx]=="." and maze_temp[ny][nx]==-1:
                            maze_temp[ny][nx]=maze_temp[yy][xx]+1
                            result_temp=max(result_temp,maze_temp[ny][nx])
                            fifo.append([ny,nx])
                            
            result=max(result_temp,result)
            
            
print(result)

Solution (Python):
def bfs_longest(x,y):
    queuex = [x]
    queuey = [y]
    queuedis = [0]
    ans = [0]
    dis = [[-1 for _ in range(w+2)]for k in range(h+2)]
    dis[x][y] = 0
    while(len(queuex)):
        nowx = queuex.pop(0)
        nowy = queuey.pop(0)
        nowdis = queuedis.pop(0)
        search = [[nowx+1,nowy],[nowx-1,nowy],[nowx,nowy+1],[nowx,nowy-1]]
        for i in range(len(search)):
            if dis[search[i][0]][search[i][1]] == -1:
                if maze[search[i][0]][search[i][1]] == ".":
                    queuex.append(search[i][0])
                    queuey.append(search[i][1])
                    queuedis.append(nowdis+1)
                    ans.append(nowdis+1)
                    dis[search[i][0]][search[i][1]] = nowdis+1
    return ans[-1]

h,w = map(int,input().split())
maze = [["
anchor = []
for i in range(h):
    data = str(input())
    for j in range(w):
        maze[i+1][j+1] = data[j]
        if data[j] == ".":
            anchor.append([i+1,j+1])

answer = 0
for i in range(len(anchor)):
    answer = max(bfs_longest(anchor[i][0],anchor[i][1]),answer)
print(answer)

Solution (Python):
def bfs_longest(x,y):
    queuex = [x]
    queuey = [y]
    queuedis = [0]
    looked = [[x,y]]
    ans = [0]
    while(len(queuex)):
        nowx = queuex.pop(0)
        nowy = queuey.pop(0)
        nowdis = queuedis.pop(0)
        search = [[nowx+1,nowy],[nowx-1,nowy],[nowx,nowy+1],[nowx,nowy-1]]
        for i in range(len(search)):
            if not (search[i] in looked):
                if maze[search[i][0]][search[i][1]] == ".":
                    queuex.append(search[i][0])
                    queuey.append(search[i][1])
                    queuedis.append(nowdis+1)
                    ans.append(nowdis+1)
                    looked.append([search[i][0],search[i][1]])
    return ans[-1]

h,w = map(int,input().split())
maze = [["
anchor = []
for i in range(h):
    data = str(input())
    for j in range(w):
        maze[i+1][j+1] = data[j]
        if data[j] == ".":
            anchor.append([i+1,j+1])

answer = 0
if (len(anchor)) == (h*w):
    print(h+w-2)
    exit()
for i in range(len(anchor)):
    answer = max(bfs_longest(anchor[i][0],anchor[i][1]),answer)
print(answer)

Solution (Python):
from collections import deque
 
inf = float('inf')
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

ans = 0
 

for si in range(h):
    for sj in range(w):
        if s[si][sj] == '
            continue
        dist = [[inf for j in range(w)] for i in range(h)]
        q = deque()
        
        def update(i, j, x):
            if dist[i][j] != inf:
                return
            dist[i][j] = x
            q.append([i, j])
        
        update(si, sj, 0)
        
        while len(q):
            i = q[0][0]
            j = q[0][1]
            q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                if s[ni][nj] == '
                    continue
                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):
from collections import deque

inf = float('inf')
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

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

ans = 0


for si in range(h):
    for sj in range(w):
        if s[si][sj] == '
            continue
        dist = [[-inf for j in range(w)] for i in range(h)]
        q = deque()
        
        def update(i, j, x):
            if dist[i][j] != -inf:
                return
            dist[i][j] = x
            q.append([i, j])
        
        update(si, sj, 0)
        
        while len(q):
            i = q[0][0]
            j = q[0][1]
            q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                if s[ni][nj] == '
                    continue
                update(ni, nj, dist[i][j] + 1)

        
        dist_max = max(list(map(lambda x: max(x), dist)))
        ans = max(ans, dist_max)

print(ans)