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 heapq import heappush, heappop
def main():
    def dijkstra_search(s):
        d = [INF] * size
        searched = [False] * size
        d[s] = 0
        searched[s] = True
        edge_list = []
        count = 1
        for i in edge[s]:
            heappush(edge_list,i)
        while edge_list:
            min_d,min_v = heappop(edge_list)
            if searched[min_v] or min_d > d[min_v]:
                continue
            v = min_v
            d[v] = min_d
            searched[v] = True
            count += 1
            for i,j in edge[v]:
                next_d = i+d[v]
                if not searched[j]:
                    heappush(edge_list,(next_d,j))
            if count == size:
                break
        return d
    def judge(a,b):
        if a >= 0 and a < h and b >= 0 and b < w and s[a][b] == ".":
            return True
        else:
            return False
    h,w = map(int,input().split())
    s = [list(input()) for _ in range(h)]
    size = h*w
    INF = float('inf')
    edge = [[] for _ in range(size)]
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                if judge(i+1,j):
                    edge[i*w+j].append((1,((i+1)*w+j)))
                if judge(i-1,j):
                    edge[i*w+j].append((1,((i-1)*w+j)))
                if judge(i,j+1):
                    edge[i*w+j].append((1,(i*w+(j+1))))
                if judge(i,j-1):
                    edge[i*w+j].append((1,(i*w+(j-1))))
    ans = []
    for i in range(size):
        if s[i//w][i%w-1] == ".":
            d_list = dijkstra_search(i)
            for j in d_list:
                if not j == INF:
                    ans.append(j)
    print(max(ans))
    
if __name__ == '__main__':
    main()

Solution (Python):

import numpy as np
from scipy.sparse.csgraph import shortest_path

H, W = list(map(int, input().split()))
s_table = []
node_index = 0

for _ in range(H):
    s_list = list(input())
    s_table.append(s_list)

adj = [[0] * (W * H) for _ in range(W * H)]
node_index = -1
for h_i, s_list in enumerate(s_table):
    for w_i, s in enumerate(s_list):
        node_index += 1
        if s == "
            continue
        if w_i + 1 < W:
            
            if s_list[w_i + 1] == ".":
                adj[node_index][node_index + 1] = 1
                adj[node_index + 1][node_index] = 1
        if h_i + 1 < H:
            
            if s_table[h_i + 1][w_i] == ".":
                adj[node_index][(h_i + 1) * W + w_i] = 1
                adj[(h_i + 1) * W + w_i][node_index] = 1

adj = np.array(adj)
d_matrix = shortest_path(adj)

d_matrix[d_matrix == float("inf")] = -1
ans = int(d_matrix.max())
print(ans)

Solution (Python):
h,w=map(int,input().split())
ans=-1
s=[]
for i in range(h):
	ss=input()
	s.append(ss)
from collections import deque as dq
for i in range(h):
	for j in range(w):
		if s[i][j]=="
			continue
		dis=[[10**3 for _ in range(w)]for _ in range(h)]
		dis[i][j]=0
		queue=dq([[i,j]])
		while queue:
			r=queue.popleft()
			if r[0]+1<h:
				if s[r[0]+1][r[1]]=="." and dis[r[0]+1][r[1]]==10**3:
					queue.append([r[0]+1,r[1]])
					dis[r[0]+1][r[1]]=dis[r[0]][r[1]]+1
			if r[0]-1>=0:
				if s[r[0]-1][r[1]]=="." and dis[r[0]-1][r[1]]==10**3:
					queue.append([r[0]-1,r[1]])
					dis[r[0]-1][r[1]]=dis[r[0]][r[1]]+1
			if r[1]+1<w:
				if s[r[0]][r[1]+1]=="." and dis[r[0]][r[1]+1]==10**3:
					queue.append([r[0],r[1]+1])
					dis[r[0]][r[1]+1]=dis[r[0]][r[1]]+1
			if r[1]-1>=0:
				if s[r[0]][r[1]-1]=="." and dis[r[0]][r[1]-1]==10**3:
					queue.append([r[0],r[1]-1])
					dis[r[0]][r[1]-1]=dis[r[0]][r[1]]+1
		for k in range(h):
			for l in range(w):
				if dis[k][l]!=10**3:
					ans=max(ans,dis[k][l])
print(ans)

Solution (Python):
from collections import deque
from itertools import product
from copy import deepcopy

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

sls = list(product(range(h),range(w)))
ans = 0
move = [[0,1], [1,0],[0,-1], [-1,0]]
for s in sls:
    if ls[s[0]][s[1]] == '
        continue
    else:
        lss = deepcopy(ls)
        d=deque()
        d.append(s)
        lss[s[0]][s[1]] = 0
        while d:
            x,y = d.popleft()
            c = lss[x][y]
            for dx,dy in move:
                if 0<=x+dx<h and 0<=y+dy<w and lss[x+dx][y+dy] == '.' :
                    lss[x+dx][y+dy] = c+1
                    d.append([x+dx, y+dy])
                    

        dist = 0
        for i in range(h):
            for j in range(w):
                if type(lss[i][j]) is int:
                    dist = max(dist, lss[i][j])

        ans = max(ans, dist)

print(ans)

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

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

def search(s_h, s_w):
    stack = []
    isuse = [[False] * w for _ in range(h)]
    def add(a, b,score):
        nonlocal stack, isuse
        if not (0 <= a < h and 0 <= b < w):
            return 0
        if s[a][b] == "
            return 0
        if isuse[a][b]:
            return 0
        isuse[a][b] = True
        stack.append((a,b,score+1))
        
    add(s_h, s_w, -1)
    c=0
    while stack:
        a,b,c = stack.pop(0)
        add(a + 1, b, c)
        add(a , b + 1, c)
        add(a, b - 1, c)
        add(a - 1, b, c)
    return c

search(0,0)

ans = 0
for s_h in range(h):
    for s_w in range(w):
        ans = max(search(s_h, s_w), ans)
        
print(ans)

Solution (Python):



def f(S, H, W, y, x):
    if S[y][x] == '
        return 0
        
    C = [-1]*(H*W)
    C[y*W + x] = 0
    Q = [(y, x)]

    while len(Q) > 0:
        Q2 = []
        for y2, x2 in Q:
            c = C[y2*W + x2]

            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                y3 = y2 + dy
                x3 = x2 + dx

                if (y3 >= 0 and y3 < H and x3 >= 0 and x3 < W and
                    S[y3][x3] == '.' and C[y3*W + x3] == -1):

                    C[y3*W + x3] = c + 1
                    Q2.append((y3, x3))

        Q = Q2

    return max(C)
                

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

    print(max(f(S, H, W, y, x) for y in range(H) for x in range(W)))
        


if __name__ == '__main__':
    main()

Solution (Python):
import queue

class BreadthFirstSearch:
    def __init__(self, h, w, start_xy, board):
        self.h, self.w = h, w
        (self.sx, self.sy) = start_xy
        self.board = board
        self.hist = [[False] * w for i in range(h)]

    def get_step(self, wall="
        '''
        区切り文字を指定する(デフォルトは
        ゴールに着くまでの最短距離を出力
        ゴールにたどり着かない場合は0を出力
        '''
        q = queue.Queue()
        q.put((self.sx, self.sy))
        self.hist[self.sy][self.sx] = True
        step = 0
        count = 1
        next_count = 1
        ans = 0
        
        while not q.empty():
            x, y = q.get()
            count -= 1
            if count == 0:
                step += 1
                count = next_count
                next_count = 0
            
            for (i, j) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                
                if not(0 <= x+i <= w - 1) or not(0 <= y+j <= h - 1):
                    continue
                
                if self.board[y+j][x+i] == wall:
                    continue
                
                if self.hist[y+j][x+i]:
                    continue
                
                self.hist[y+j][x+i] = True
                q.put((x+i, y+j))
                next_count += 1
        return step



h, w = map(int, input().split())

board = [[i for i in list(str(input()))] for i in range(h)]

ans_ = []
for s_i in range(h):
    for s_j in range(w):
        if board[s_i][s_j] == "
            continue
        s_xy = (s_j, s_i)
        bfs = BreadthFirstSearch(h, w, s_xy, board[:])
        ans = bfs.get_step()
        ans_.append(ans)
print(max(ans_) - 1)

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

def search(sh,sw):

    if S[sh][sw] == "
        return -1
    ans = 0
    queue = [(sh,sw)]
    M = [[0]*(W + 2) for _ in range(H+2)]
    M[sh][sw] =  1

    while len(queue) > 0:
        h,w = queue.pop(0)
        if S[h + 1][w] == "." and M[h + 1][w] == 0:
            queue.append((h+1,w))
            M[h+1][w] = M[h][w] + 1
        if S[h - 1][w] == "." and M[h - 1][w] == 0:
            queue.append((h-1,w))
            M[h-1][w] = M[h][w] + 1
        if S[h][w + 1] == "." and M[h][w + 1] == 0:
            queue.append((h,w+1))
            M[h][w+1] = M[h][w] + 1
        if S[h][w - 1] == "." and M[h][w - 1] == 0:
            queue.append((h,w-1))
            M[h][w-1] = M[h][w] + 1
        
    for mm in M:
        ans = max(ans,max(mm))
    return ans-1


def main():
    ans = 0
    for i in range(1,H+1):
        for j in range(1,W+1):
            ans = max( ans, search(i,j) )
    print(ans)
    return 


if __name__ == "__main__":
    main()

Solution (Python):


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



def bfs():
    while queue:
        now_row,now_column = queue.pop(0)

        
        
        for i in range(4):
            next_row, next_column = now_row + dy[i] , now_column + dx[i]
            if 0 <= next_row < H and 0 <= next_column < W and \
                    maze[next_row][next_column] != "
                visited[next_row][next_column] = visited[now_row][now_column] + 1
                queue.append([next_row,next_column])


ans = 0
for column in range(W):
    for row in range(H):
        if maze[row][column] == "
            continue
        
        queue = [[row, column]]
        
        visited = [[INF] * W for _ in range(H)]
        visited[row][column] = 0
        bfs()
        tmp_max = 0
        for i in range(H):
            if tmp_max < max(visited[i]):
                tmp_max = max(visited[i])
        if tmp_max > ans:
            ans = tmp_max
print(ans)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
lst1 = [list(list(input())) for i in range(H)]

def dfs(maze,visited, sh, sw):
    a = 0
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.popleft()
        
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): 
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W: 
                continue
            elif maze[new_h][new_w] != "
                visited[new_h][new_w] == 0: 
                visited[new_h][new_w] = visited[h][w]+1
                stack.append([new_h, new_w])
    a = 0
    for s in range(H):
        for x in range(W):
            a = max(a,visited[s][x])
    return a

ans = 0

for i in range(H):
    for q in range(W):
        visited = [[0]*W for _ in range(H)]
        if lst1[i][q] == ".":
            ans = max(ans,dfs(lst1,visited,i,q))
print(ans-1)

Solution (Python):
map_height,map_width=map(int,input().split())
d={'.':0,'
map_data= [list(map(lambda x: d[x],list(input()))) for _ in range(map_height)]

import itertools
Z= map_width*map_height


m = [[401 for _ in range(Z)] for _ in range(Z)]
for i,j in itertools.product(range(map_height),range(map_width)):
    if map_data[i][j] == 0:
        for i_n, j_n in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
            if 0 <= i_n < map_height and 0 <= j_n < map_width:
                if map_data[i_n][j_n] == 0:
                    m[map_width*i+j][map_width*i_n+j_n] = 1
for i in range(Z):
    m[i][i]=0
for k in range(Z):
    for i in range(Z):
        for j in range(Z):
            temp = min(m[i][j],m[i][k] + m[k][j])
            m[i][j] = temp
                
ans = 0
for i in range(Z):
    for j in range(Z):
        temp = m[i][j]
        if temp != 401:
            if ans < m[i][j]:
                ans = m[i][j]
print(ans)

Solution (Python):
def main():
    from collections import deque

    h, w = map(int, input().split())

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

    drdc = (1, 0), (-1, 0), (0, 1), (0, -1)

    ret = -1
    for r in range(h):
        for c in range(w):
            if s[r][c] == '.':
                dist = [[-1] * w for _ in range(h)]
                dist[r][c] = 0

                q = deque()
                q.append((r, c, 0))

                md = -1
                while q:
                    qr, qc, d = q.popleft()
                    for dr, dc in drdc:
                        nr = qr + dr
                        if nr < 0 or h <= nr:
                            continue
                        nc = qc + dc
                        if nc < 0 or w <= nc:
                            continue
                        if s[nr][nc] == '
                            continue
                        if dist[nr][nc] != -1:
                            continue
                        nd = d + 1
                        dist[nr][nc] = nd
                        if md < nd:
                            md = nd

                        q.append((nr, nc, nd))

                ret = max(ret, md)

    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):

def dfs_deep_measure(st, h, w, reach):
    
    deep = [[500] * w for _ in range(h)]
    check = [[0] * w for _ in range(h)]
    stack = [st]
    st_i, st_j = st[0], st[1]
    check[st_i][st_j] = 1
    deep[st_i][st_j] = 0
    while len(stack) > 0:
        tmp = stack.pop(0)
        tmp_i, tmp_j = tmp[0], tmp[1]
        tmp_list = reach[tmp_i][tmp_j]
        for i in range(len(tmp_list)):
            t_i, t_j = tmp_list[i][0], tmp_list[i][1]
            if check[t_i][t_j] != 1:
                stack.append((t_i, t_j))
                check[t_i][t_j] = 1
                for j in range(len(reach[t_i][t_j])):
                    ii = (reach[t_i][t_j])[j][0]
                    jj = (reach[t_i][t_j])[j][1]
                    deep[t_i][t_j] = min(deep[ii][jj]+1, deep[t_i][t_j])
    return deep


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

move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
reach = [[[] for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        for k in range(len(move)):
            if s[i][j] == '
                pass
            else:
                x = i + move[k][0]
                y = j + move[k][1]
                if 0 <= x <= h-1 and 0 <= y <= w-1:
                    if s[x][y] == '.':
                        reach[i][j].append((x, y))




ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            pass
        else:
            tmp_deep = dfs_deep_measure((i, j), h, w, reach)
            
            
            for k in range(h):
                for l in range(w):
                    if tmp_deep[k][l] != 500:
                        ans = max(ans, tmp_deep[k][l])


print(ans)

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

G = [[] for i in range(h*w)]
for i in range(h):
    for j in range(w):
        if sl[i][j] == "
            continue
        a = i*w + j
        if j != w - 1:
            if sl[i][j+1] != "
                b = i*w + j + 1
                G[a].append(b)
        if j != 0:
            if sl[i][j-1] != "
                b = i*w + j - 1
                G[a].append(b)
        if i != 0:
            if sl[i-1][j] != "
                b = i*w + j - w
                G[a].append(b)
        if i != h - 1:
            if sl[i+1][j] != "
                b = i*w + j + w
                G[a].append(b)




ans = 0
from collections import deque
for i in range(h*w):
    if sl[i//w][i%w] == "
        continue
    dist = [-1]*(w*h)
    que = deque([i])
    dist[i] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for p in G[v]:
            if dist[p] > -1:
                continue
            dist[p] = d + 1
            que.append(p)
    ans = max(ans, max(dist))
    
print(ans)

Solution (Python):
import copy
import itertools
from collections import deque
INF = float('inf')
ROAD = '.'
WALL = '
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def main():
    H, W = map(int, input().split())
    
    
    initial_maze = [None] * H

    
    for i in range(H):
        initial_maze[i] = list(input())
        for j in range(W):
            if initial_maze[i][j] == ROAD:
                initial_maze[i][j] = INF
    
    ans = 0
    for sy, sx in itertools.product(range(H), range(W)):
        if initial_maze[sy][sx] == WALL:
            continue

        maze = copy.deepcopy(initial_maze)
        maze[sy][sx] = 0
        que = deque([[sy, sx]])

        while que:
            y,x = que.popleft()

            for (i, j) in STEPS:
                ny, nx = y+i, x+j
                if ny < 0 or ny >= H or nx < 0 or nx >= W:
                    continue

                target = maze[ny][nx]
                if target != WALL:
                    if target > maze[y][x]+1:
                        maze[ny][nx] = maze[y][x] + 1
                        if maze[ny][nx] > ans:
                            ans = maze[ny][nx]
                        que.append([ny,nx])
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


def bfs(p):
    q = deque()
    q.append((p[0], p[1], 0))
    dis = 0
    path[p[0]][p[1]] = 0
    while len(q):
        x, y, s = q.popleft()
        dis = max(dis, s)  
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and path[nx][ny] > s + 1 and maze[nx][ny] == '.':
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

    return dis

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

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

print(ans)

Solution (Python):
import heapq

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

ans = 0
for h in range(H):
    for w in range(W):
        visited = [[False] * W for _ in range(H)]
        queue = [(0, h, w)]
        max_move = 0
        while queue:
            move, nh, nw = heapq.heappop(queue)
            if not (0 <= nh < H and 0 <= nw < W):
                continue
            if visited[nh][nw]:
                continue
            if maze[nh][nw] == "
                continue
            visited[nh][nw] = True
            max_move = max(max_move, move)
            heapq.heappush(queue, (move + 1, nh + 1, nw))
            heapq.heappush(queue, (move + 1, nh - 1, nw))
            heapq.heappush(queue, (move + 1, nh, nw + 1))
            heapq.heappush(queue, (move + 1, nh, nw - 1))
        ans = max(ans, max_move)
print(ans)

Solution (Python):
H, W = map(int, input().split())
A = [[0 for i in range(W)] for j in range(H)]
maze = [input() for i in range(H)]
X = []
for i in range(H):
  for j in range(W):
    if maze[i][j] == '.':
      p = [i, j]
      Al = [p]
      luck = 0
      A[p[0]][p[1]] = -1
      while Al != []:
        luck += 1
        n = len(Al)
        for m in range(n):
          if Al[0][0] > 0 and maze[Al[0][0]-1][Al[0][1]] == '.' and A[Al[0][0]-1][Al[0][1]] == 0:
            A[Al[0][0]-1][Al[0][1]] = luck
            Al.append([Al[0][0]-1, Al[0][1]])
          if Al[0][0] < H - 1 and maze[Al[0][0]+1][Al[0][1]] == '.' and A[Al[0][0]+1][Al[0][1]] == 0:
            A[Al[0][0]+1][Al[0][1]] = luck
            Al.append([Al[0][0]+1, Al[0][1]])
          if Al[0][1] > 0 and maze[Al[0][0]][Al[0][1]-1] == '.' and A[Al[0][0]][Al[0][1]-1] == 0:
            A[Al[0][0]][Al[0][1]-1] = luck
            Al.append([Al[0][0], Al[0][1]-1])
          if Al[0][1] < W - 1 and maze[Al[0][0]][Al[0][1]+1] == '.' and A[Al[0][0]][Al[0][1]+1] == 0:
            A[Al[0][0]][Al[0][1]+1] = luck
            Al.append([Al[0][0], Al[0][1]+1])
          Al = Al[1:]
      X.append(luck-1)
      A = [[0 for i in range(W)] for j in range(H)]
print(max(X))

Solution (Python):
from collections import deque

INF = 10**5


def bfs(maze, sx, sy):
    if maze[sx][sy] == "
        return [[-1]]
    
    d = [[-INF] * m for i in range(n)]

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

    
    
            
            
            
            
            
            
            

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

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

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

    return d


n, m = map(int, input().split())
ma = [list(input()) for i in range(n)]
maxm=0
for i in range(m):
    for j in range(n):
        a = bfs(ma, j, i)
        
        for x in a:
            for y in x:
                maxm = maxm if maxm>y else y
print(maxm)

Solution (Python):
from collections import deque

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

maze = []
for _ in range(H):
    maze.append(input())


def bfs(sy, sx):
    table = [[-1] * W for _ in range(H)]
    table[sy][sx] = 0
    queue = deque([[sy, sx]])
    while queue:
        y, x = queue.popleft()
        for dy, dx in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + dy, x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and table[ny][nx] == -1:
                table[ny][nx] = table[y][x] + 1
                m = table[ny][nx]
                queue.append([ny, nx])
    return m


ans = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == '.':
            ans = max(ans, bfs(y, x))
print(ans)

Solution (Python):
from heapq import heappop,heappush

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

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

edges = [[-1 for _ in range(h*w)] for __ in range(h*w)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            for x in delta:
                to_i = i+x[0]
                to_j = j+x[1]
                if 0 <= to_i < h and 0 <= to_j < w:
                    if s[to_i][to_j] == '.':
                        edges[i*w+j][to_i*w+to_j] = 1
                        edges[to_i*w+to_j][i*w+j] = 1

n = h*w

def dijkstra(s,n,edges):
    
    
    d = [10**13] * n
    d[s] = 0
    q = [(0,s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if c >= 0:
                if d[v] > dist_u + c:
                    d[v] = dist_u + c
                    heappush(q, (d[v], v))
    return d

ans = 0

for i in range(h):
    for j in range(w):
        d = dijkstra(i*w+j,n,edges)
        for l in d:
            if l < 10**6:
                ans = max(ans,l)

print(ans)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

cell_name = [[np.infty]*W for i in range(H)]
count = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            cell_name[i][j] = count
            count += 1
            
tot_cell = count

dist = [[np.infty]*tot_cell for i in range(tot_cell)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            name = cell_name[i][j]
            if i >= 1:
                if S[i-1][j] == ".":
                    dist[name][cell_name[i-1][j]] = 1
            if i < H-1:
                if S[i+1][j] == ".":
                    dist[name][cell_name[i+1][j]] = 1
            if j >= 1:
                if S[i][j-1] == ".":
                    dist[name][cell_name[i][j-1]] = 1
            if j < W-1:
                if S[i][j+1] == ".":
                    dist[name][cell_name[i][j+1]] = 1

cost = floyd_warshall(dist)

max_dist = 0
for i in range(tot_cell):
    for j in range(tot_cell):
        if cost[i][j] > max_dist:
            max_dist = cost[i][j]
print(int(max_dist))

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(input() for _ in range(H))
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]

    def bfs(h,w):
        Q = deque([(h,w)])
        dist = [[-1] * W for _ in range(H)]
        dist[h][w] = 0
        while Q:
            y, x = Q.popleft()

            for i in range(4):
                nh = y + dy[i]
                nw = x + dx[i]

                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and dist[nh][nw] == float(-1):
                    dist[nh][nw] = dist[y][x] + 1
                    Q.append((nh,nw))

        tmp = 0
        for a in range(H):
            tmp = max(tmp, max(dist[a]))
        return tmp
    
    ans = []
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                ans.append(bfs(h,w))
    

    print(max(ans))


    

if __name__ == "__main__":
    main()

Solution (Python):
H, W = list(map(int, input().split()))
S = [list(input()) for _ in range(H)]
import queue
import copy
class gridMan:
  def __init__(s, L):
    s.L = L
  def makeWall(s, x):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S):
    T = copy.deepcopy(s.L)
    T[S[0] + 1][S[1] + 1] = 1
    q = queue.Queue()
    q.put([S[0] + 1, S[1] + 1])
    ans = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      ans = max(ans, k)
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if T[hh][ww] == -1:
          continue
        t = T[hh][ww]
        if t == 0:
          q.put([hh, ww])
          T[hh][ww] = k + 1
    return ans - 1

for i in range(H):
  for j in range(W):
    if S[i][j] == "
      S[i][j] = -1
    else:
      S[i][j] = 0

g = gridMan(S)
g.makeWall(-1)
ans = 0
for sx in range(H):
  for sy in range(W):
    if S[sx][sy] == -1:
      continue
    ans = max(ans, g.dist([sx, sy]))

print(ans)

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


road=[]

for i in range(h):
    row=input()
    road.append(row)

ikel=0

for i in range(h):
    for j in range(w):
        if road[i][j]=='.':
            ikel+=1

maxrecord=0

for i in range(h):
    for j in range(w):
        turn=1
        ima=1
        now=[[i, j]]
        rlist=[]
        for hh in range(h):
            rlist.append([999]*w)
        rlist[i][j]=0
        if road[i][j]=='.':
            while ima<ikel:
                koho=[]
                for nw in now:
                    if nw[0]>0:
                        koho.append([nw[0]-1, nw[1]])
                    if nw[0]<h-1:
                        koho.append([nw[0]+1, nw[1]])
                    if nw[1]>0:
                        koho.append([nw[0], nw[1]-1])
                    if nw[1]<w-1:
                        koho.append([nw[0], nw[1]+1])
                now=[]
                for kh in koho:
                    if road[kh[0]][kh[1]]=='.':
                        if rlist[kh[0]][kh[1]]>turn:
                            rlist[kh[0]][kh[1]]=turn
                            now.append([kh[0], kh[1]])
                            ima+=1
                            record=turn
                turn+=1
            if record>maxrecord:
                maxrecord=record

print(maxrecord)

Solution (Python):
H, W = map(int, input().split())
Map = []
for i in range(H):
    Map.append(input())
for i in range(H):
    for j in range(W):
        if Map[i][j] == 's':
            (sx, sy) = (j, i)
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)

def maxlen(sx, sy):
    visited = [[-1] * W for i in range(H)]
    stack = [(sx, sy)]
    visited[sy][sx] = 0
    c = 1
    while stack:
        st = []
        for a in stack:
            x = a[0]
            y = a[1]
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<W and 0<=ny<H and visited[ny][nx] == -1:
                    if Map[ny][nx] == '.':
                        visited[ny][nx] = c
                        st.append((nx, ny))
        stack = st
        c += 1
    return c-2
ans = -1
for i in range(H):
    for j in range(W):
        if Map[i][j] == '.':
            ans = max(ans, maxlen(j, i))
print(ans)

Solution (Python):
from collections import deque

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

S = [[c == '.' for c in input()] for _ in range(H)]

INF = 10 ** 5


def get_new_maze():
    return [[INF for _ in range(W)] for _ in range(H)]


def get_max_distance(w_start, h_start):
    if not S[h_start][w_start]:
        return -1
    maze_map = get_new_maze()
    q = deque()
    q.append([w_start, h_start, 0])

    ret_dist = 0

    while len(q) > 0:
        next_q = q.popleft()
        h = next_q[1]
        w = next_q[0]
        g = next_q[2]
        if S[h][w] and maze_map[h][w] > g:
            maze_map[h][w] = g
            ret_dist = max(g, ret_dist)
            if h > 0:
                q.append([w, h - 1, g + 1])
            if h < H - 1:
                q.append([w, h + 1, g + 1])
            if w > 0:
                q.append([w - 1, h, g + 1])
            if w < W - 1:
                q.append([w + 1, h, g + 1])

    return ret_dist


ans = 0

for c in range(W):
    for r in range(H):
        ans = max(ans, get_max_distance(c, r))

print(ans)