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 collections
h, w = list(map(int, input().split()))

s = []
for i in range(h):
    line = input()
    s.append(line)

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

        stack = collections.deque()
        stack.append((i, j, 0))
        d[i][j] = True
        while stack:
            y, x, score = stack.popleft()
            if y > 0 and s[y-1][x] == '.' and not d[y-1][x]:
                stack.append((y-1, x, score+1))
                d[y-1][x] = True
            if x < w-1 and s[y][x+1] == '.' and not d[y][x+1]:
                stack.append((y, x+1, score+1))
                d[y][x+1] = True
            if y < h-1 and s[y+1][x] == '.' and not d[y+1][x]:
                stack.append((y+1, x, score+1))
                d[y+1][x] = True
            if x > 0 and s[y][x-1] == '.' and not d[y][x-1]:
                stack.append((y, x-1, score+1))
                d[y][x-1] = True
            if score > ans:
                ans = score
print(ans)

Solution (Python):
from collections import deque

def bfs(maze, visited,h,w,sx,sy):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    mx = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0<=new_y<h and 0<=new_x<w:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    if visited[new_y][new_x] > mx:
                        mx = visited[new_y][new_x]
                    queue.append([new_y, new_x])

    return mx

if __name__ == "__main__":
    h, w = map(int, input().split())

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

    ans = []
    for idxi,i in enumerate(maze):
        for idxj,j in enumerate(i):
            if j == '.':
                sx,sy = idxj,idxi
                visited = [[-1]*w for j in range(h)]
                ans.append(bfs(maze, visited,h,w,sx,sy))

    print(max(ans))

Solution (Python):

from collections import deque


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())
    walls = [[c == '

    count = 0
    Q = deque()

    for sy in range(h):
        for sx in range(w):
            if walls[sy][sx]:
                continue

            passed = [[False]*w for _ in range(h)]
            Q.append((sx, sy, 0))
            while Q:
                x, y, c = Q.popleft()
                if walls[y][x] or passed[y][x]:
                    continue

                passed[y][x] = True
                count = max(c, count)

                if 0 < x:
                    Q.append((x-1, y, c+1))
                if x+1 < w:
                    Q.append((x+1, y, c+1))
                if 0 < y:
                    Q.append((x, y-1, c+1))
                if y+1 < h:
                    Q.append((x, y+1, c+1))

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
import numpy as np
import queue
H, W = map(int, input().split())
S = [input() for _ in range(H)]
reach = [[False] * W for i in range(H)]
step = np.ones((H, W)) * (-1)
m = 0
q = queue.Queue()

for sh in range(H):
    for sw in range(W):
        if False and S[sh][sw] == '
            pass
        elif ((sh - 1 >= 0 and S[sh -1][sw] != '
            pass
        else:
            reach = [[False] * W for i in range(H)]
            step = np.ones((H, W)) * (-1)
            q.put((sw, sh, 0))
            while not q.empty():
                x, y, s = q.get()
                if x < 0 or W <= x or y < 0 or H <= y:
                    pass
                elif reach[y][x]:
                    pass
                elif S[y][x] == '
                    pass
                else:
                    reach[y][x] = True
                    step[y, x] = min(s, step[y, x]) if step[y, x] != -1 else s

                    q.put((x+1, y, s+1))
                    q.put((x-1, y, s+1))
                    q.put((x, y-1, s+1))
                    q.put((x, y+1, s+1))

            m = max(m, np.max(step))

print(int(m))

Solution (Python):
H, W = map(int, input().split())
N = H * W
board = [[int(x == "
INF = N ** 2
A = [[INF] * N for _ in range(N)]
for i in range(N):
    A[i][i] = 0
drc = [(-1, 0), (1, 0), (0, 1), (0, -1)]
for r in range(H):
    for c in range(W):
        for dr, dc in drc:
            nr, nc = r + dr, c + dc
            if nr < 0 or H <= nr or nc < 0 or W <= nc:
                continue
            if board[nr][nc] == 1:
                continue
            A[r * W + c][nr * W + nc] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])
ans = 0
for sr in range(H):
    for sc in range(W):
        if board[sr][sc]:
            continue
        for gr in range(H):
            for gc in range(W):
                if board[gr][gc]:
                    continue
                ans = max(ans, A[sr*W+sc][gr*W+gc])
print(ans)

Solution (Python):


def clear_maze(sx, sy, maze):

    INF=-10**9
    global cnt
    cnt=0


    distance = [[INF for i in range(w+1)] for j in range(h+1)]
    



    def bfs():
        global cnt
        queue = []

        queue.insert(0, (sx, sy))

        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()



            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]


                if (0 <= nx and  0 <= ny  and maze[nx][ny] != '
                    queue.insert(0, (nx, ny))

                    distance[nx][ny] = distance[x][y] + 1
                    if cnt<=distance[nx][ny]:
                        cnt=distance[nx][ny]





        return cnt

    cnt=0
    distance = [[INF for i in range(w + 1)] for j in range(h + 1)]




    return bfs()

h,w = map(int, input().split())
maze=[list(input()) for i in range(h)]
t=[[0]*w for i in range(h)]
for i in range(h):
    maze[i]=['

maze=[['




ans=0

for i in range(1,h+1):
    for j in range(1,w+1):
        if maze[i][j]=='
            continue
        v=(clear_maze(i, j, maze))

        if ans<=v:
            ans=v
print(ans)

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

LOAD = '.'
WALL = '
NOT_REACHED = -1

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

s = [0] * h
for i in range(h):
    s[i] = input().strip()

def bfs(graph, queue, dist):
    _max = 0
    while queue:
        current = queue.pop(0)

        top = (current[0] - 1, current[1])
        bottom = (current[0] + 1, current[1])
        left = (current[0], current[1] - 1)
        right = (current[0], current[1] + 1)

        for target in (top, bottom, left, right):
            if (target[0] < 0) or (target[0] >= h) or (target[1] < 0) or (target[1] >= w):
                continue
            if dist[target] != NOT_REACHED:
                continue
            if graph[target[0]][target[1]] == LOAD:
                dist[target] = dist[current] + 1
                _max = max(dist[target], _max)
                queue.append(target)
    return _max

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == WALL:
            continue
        queue = [(i, j)]
        dist = {}
        for inner_i in range(h):
            for inner_j in range(w):
                dist[(inner_i, inner_j)] = NOT_REACHED
        dist[(i, j)] = 0
        ans = max(bfs(s, queue, dist), ans)

print(ans)

Solution (Python):
import numpy as np
from collections import deque
infinity = -10**5
H,W = map(int,input().split())

A = np.zeros((H+1,W+1))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            A[i][j] = 1
        else:
            A[i][j] = -1

N = H*W
G=[[] for i in range(N)]

for i in range(H):
    for j in range(W):
        if A[i][j] ==1:
            if A[i+1][j] == 1:
                G[W*(i+1)+j].append(W*i+j)
                G[W*i+j].append(W*(i+1)+j)

            if A[i][j+1] == 1:
                G[W*i+(j+1)].append(W*i+j)
                G[W*i+j].append(W*i+(j+1))

def BFS (s):
    queue = deque()
    d = [infinity]*N
    
    queue.append(s)
    d[s]= 0
    
    while len(queue)!=0:
      u = queue.popleft()
      for v in G[u]:
      	if d[v] == infinity:
        	d[v] = d[u]+1
        	queue.append(v) 	  
  
    return d

ans = 0


for i in range(N):
    I = i//W
    J = i%W
    if A[I][J] == 1:
        d = BFS(i)
        for k in range(N):
            if d[k] == infinity:
                d[k] = -1
        ans = max(ans,max(d))
        
"""

for i in range(H):
    for j in range(W):
        if A[i][j] == 1:
            d = BFS(W*i+j)
        ans = max(ans,max(d))
"""
print(ans)

Solution (Python):
import heapq
import numpy as np

H, W = [int(x) for x in input().split()]
maze = np.zeros((H, W))

for i in range(H):
    for j, way in enumerate(input()):
        if way == '.':
            maze[i, j] = 1
        else:
            maze[i, j] = 0

able_list = []

for i in range(H):
    for j in range(W):
        able = []
        if maze[i,j] == 1:
            if 0 <= i-1 < H:
                if maze[i-1, j] == 1:
                    able.append([(i-1) * W + j, 1])
            if 0 <= j-1 < W:
                if maze[i, j-1] == 1:
                    able.append([i * W + j - 1, 1])
            if 0 <= j+1 < W:
                if maze[i, j+1] == 1:
                    able.append([i* W + j + 1, 1])
            if 0 <= i+1 < H:
                if maze[i+1, j] == 1:
                    able.append([(i+1)*W + j, 1])
        able_list.append(able)



def Dijkstra(list_adjlist, initnode):
    
    list_D = [-1] * len(list_adjlist)
    
    list_D[initnode] = 0
    
    list_T = [-1] * len(list_adjlist)
    
    list_check = [False] * len(list_adjlist)
    
    list_S = []
    heapq.heappush(list_S, (list_D[initnode], initnode))
    
    while(len(list_S)):
        
        pair_w_node = heapq.heappop(list_S)
        if list_check[pair_w_node[1]] is False:
            list_check[pair_w_node[1]] = True
            
            for neighbor in list_adjlist[pair_w_node[1]]:
                if list_D[neighbor[0]] == -1 or list_D[neighbor[0]] > list_D[pair_w_node[1]] + neighbor[1]:
                    list_D[neighbor[0]] = list_D[pair_w_node[1]] + neighbor[1]
                    list_T[neighbor[0]] = pair_w_node[1]
                    heapq.heappush(list_S, (list_D[neighbor[0]], neighbor[0]))
    return list_D, list_T

ans = 0
for i in range(H):
    for j in range(W):
        if maze[i, j] == 1:
            list_D, list_T = Dijkstra(able_list, i*W + j)
            if ans < max(list_D):
                ans = max(list_D)
print(ans)

Solution (Python):
def meiro(sx,sy):
    num = [[-1] * w for i in range(h)]
    num[sx][sy] = 0
    now = {(sx,sy)}
    for i in range(1,400):
        tmp = set()
        for x,y in now:
            if x > 0:
                if lis[x-1][y] == "." and num[x-1][y] == -1:
                    num[x-1][y] = i
                    tmp.add((x-1,y))
            if x < h-1:
                if lis[x+1][y] == "." and num[x+1][y] == -1:
                    num[x+1][y] = i
                    tmp.add((x+1,y))
            if y > 0:
                if lis[x][y-1] == "." and num[x][y-1] == -1:
                    num[x][y-1] = i
                    tmp.add((x,y-1))
            if y < w-1:
                if lis[x][y+1] == "." and num[x][y+1] == -1:
                    num[x][y+1] = i
                    tmp.add((x,y+1))
        now = tmp
    nu = -1
    for i in range(h):
        for j in range(w):
            if num[i][j] != -1:
                nu = max(nu,num[i][j])
    return nu

h,w = map(int,input().split())
lis = [str(input()) for i in range(h)]
ans = -1
for sx in range(h):
    for sy in range(w):
        if lis[sx][sy] == ".":
            ans = max(ans,meiro(sx,sy))
print(ans)

Solution (Python):
import copy
from collections import deque


def dfs(x,y,z,grid,H,W):
    if(x-1>=0):
        if(grid[y][x-1]>z or grid[y][x-1]==0):
            grid[y][x-1]=z+1
            dfs(x-1,y,z+1,grid,H,W)
    if(x+1<W):
        if(grid[y][x+1]>z or grid[y][x+1]==0):
            grid[y][x+1]=z+1
            dfs(x+1,y,z+1,grid,H,W)
    if(y-1>=0):
        if(grid[y-1][x]>z or grid[y-1][x]==0):
            grid[y-1][x]=z+1
            dfs(x,y-1,z+1,grid,H,W)
    if(y+1<H):
        if(grid[y+1][x]>z or grid[y+1][x]==0):
            grid[y+1][x]=z+1
            dfs(x,y+1,z+1,grid,H,W)
    return 0
    
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(x,y,grid,H,W):
    dist=[[0 for _ in range(W)] for _ in range(H)]
    que=deque()
    que.append((y,x))
    dist[y][x]=1
    while(len(que)>0):
        y,x=que.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if(0 <= nx < W) and (0 <= ny < H) and grid[ny][nx]==0 and dist[ny][nx] == 0:
                que.append((ny,nx))
                dist[ny][nx]=dist[y][x]+1
    return( max([max(dist[i]) for i in range(H)]))
    
H,W=map(int,input().split())
grid=[]
tmp=[]
for i in range(H):
    S=str(input())
    tmp=[]
    for j in range(W):
        if(S[j]=="."):
            tmp.append(0)
        else:
            tmp.append(-1)
    grid.append(tmp)
ans=0
result=0
for i in range(W):
    for j in range(H):
        if(grid[j][i]==0):
                ans=bfs(i,j,grid,H,W)
                result=max(result,ans)
print(result-1)

Solution (Python):
from collections import deque

def bfs(maze, visited, sy, sx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[y][x]

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

maze = ["
for i in range(H):
    tmp = "
    tmp += input()
    tmp += "
    maze.append(tmp)
maze.append("
    



max_bfs = 0
for sy in range(1, H+2):
    for sx in range(1, W+2):
        if maze[sy][sx] == ".":
            visited = [[-1]*(W+2) for j in range(H+2)]
            tmp_bfs = bfs(maze, visited, sy, sx)
            if tmp_bfs > max_bfs:
                max_bfs = tmp_bfs
        
print(max_bfs)

Solution (Python):
from collections import deque
r, c = map(int, input().split())
 
orig_maze = [[val for val in list(input())] for _ in range(r)]

maze = [[None for _ in range(c+2)] for _ in range(r+2)]
for r_index in range(r+2):
  for c_index in range(c+2):
    if r_index == 0 or r_index == r+1 or c_index == 0 or c_index == c+1:
      maze[r_index][c_index] = "
    else:
      maze[r_index][c_index] = orig_maze[r_index-1][c_index-1]
      
def wfs(queue):
    finish_dist = None
    max_way = 0
    while len(queue) > 0:
        a = queue.popleft()
        y = a[0]
        x = a[1]
        count = a[2]
        if checked_maze[y][x]:
            continue
        
        checked_maze[y][x] = True
        if not maze[y][x] == "
            max_way = count
            count += 1
            queue.append((a[0]+1, a[1], count))
            queue.append((a[0]-1, a[1], count))
            queue.append((a[0], a[1]+1, count))
            queue.append((a[0], a[1]-1, count))

    return max_way 
 
if __name__ == "__main__":
    result = 0
    
    for s_y in range(1, r+1):
      for s_x in range(1, c+1):
        checked_maze = [[None for _ in range(c+2)] for _ in range(r+2)]
        que = deque()
        checked_maze[s_y][s_x]= 0
        que.append((s_y, s_x, 0))
        finish_dist = wfs(que)
        result = max(result,finish_dist)
    print(result)

Solution (Python):
def bfs(H, W, h, w, maze):
    if maze[h][w] == '
        return 0
    visited = []
    distance = []
    for i in range(H):
        visited.append([False] * W)
        distance.append([0] * W)
    visited[h][w] = True
    position = [[h, w]]
    current = 0
    while len(position) > 0:
        h, w = iter(position.pop(0))
        current = distance[h][w]
        if h - 1 >= 0 and maze[h-1][w] == '.' and not(visited[h-1][w]):
            distance[h-1][w] = current + 1
            visited[h-1][w] = True
            position.append([h-1, w])
        if h + 1 < H and maze[h+1][w] == '.' and not(visited[h+1][w]):
            distance[h+1][w] = current + 1
            visited[h+1][w] = True
            position.append([h+1, w])
        if w - 1 >= 0 and maze[h][w-1] == '.' and not(visited[h][w-1]):
            distance[h][w-1] = current + 1
            visited[h][w-1] = True
            position.append([h, w-1])
        if w + 1 < W and maze[h][w+1] == '.' and not(visited[h][w+1]):
            distance[h][w+1] = current + 1
            visited[h][w+1] = True
            position.append([h, w+1])
    return current


H, W = map(int, input().split())
maze = []
for i in range(H):
    maze.append(input())
M = 0
for h in range(H):
    for w in range(W):
        d = bfs(H, W, h, w, maze)
        if d > M:
            M = d
print(M)

Solution (Python):
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import random



readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

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

for i in range(H):
    a = input()
    for j in range(len(a)):
        if a[j] == "
            MEIJI[i][j] = 1


def findStart():
    for x in range(H):
        for y in range(W):
            if MEIJI[x][y] == 0:
                return x, y

    return False


def bfs(H, W, sx, sy):
    if MEIJI[sx][sy] == 1:
        return 0, 0, 0, -1
    d = [[-1] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque([])
    q.append((sx, sy))
    d[sx][sy] = 0

    mx = -1
    gx, gy = -1, -1
    while(len(q) != 0):
        x, y = q.popleft()

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

            if (0 <= nx and nx <= (H-1) and 0 <= ny and ny <= (W-1) and MEIJI[nx][ny] == 0 and d[nx][ny] == -1):
                q.append((nx, ny))
                l = d[x][y] + 1
                d[nx][ny] = l

                if l > mx:
                    gx, gy = nx, ny
                    mx = l
    return d, gx, gy, mx


mx = 0
for x in range(H):
    for y in range(W):
        _, _, _, l = bfs(H, W, x, y)
        if l > mx:
            mx = l

print(mx)
exit()

sx, sy = findStart()
_, x, y, _ = bfs(H, W, sx, sy)
_, _, _, l = bfs(H, W, x, y)

if l < 0:
    l = 0

print(l)

Solution (Python):
import queue
import itertools
r,c=map(int,input().split())
s=[list(input()) for i in range(r)]
ans=0
for i1 in range(r):
    for i2 in range(c):
        p=0
        a=[[s[j][i] for i in range(c)] for j in range(r)]
        sy,sx=i1,i2
        if a[sy][sx]=="
            continue
                
        q = queue.Queue()
        d=[(-1,0),(1,0),(0,-1),(0,1)]
        a[sy][sx]=0
        for i in d:
            if 0<=sy+i[0]<r and 0<=sx+i[1]<c and a[sy+i[0]][sx+i[1]]==".":
                a[sy+i[0]][sx+i[1]]=1
                q.put((sy+i[0],sx+i[1]))
        while not q.empty():
            y,x=q.get()
            for i in d:
                if 0<=y+i[0]<r and 0<=x+i[1]<c and a[y+i[0]][x+i[1]]==".":
                    a[y+i[0]][x+i[1]]=a[y][x]+1
                    q.put((y+i[0],x+i[1]))
        for i in range(r):
            for j in range(c):
                if type(a[i][j])==int:
                    p=max(p,a[i][j])
        ans=max(p,ans)
print(ans)

Solution (Python):
from collections import deque
import itertools
h,w=map(int,input().split())
s=["
s.insert(0,'
s.append('
def dep(s,t,p,q,time):
    print(s)
    s[p][q]=min(time,s[p][q])
    time+=1
    if t[p+1][q]=="." :
        dep(s,t,p+1,q,time)
    if t[p-1][q]=="." :
        dep(s,t,p-1,q,time)
    if t[p][q+1]=="." :
        dep(s,t,p,q+1,time)
    if t[p][q-1]=="." :
        dep(s,t,p,q-1,time)
    return max(itertools.chain.from_iterable(s))

m=0
for i in range(h):
    for j in range(w):
        if s[i+1][j+1]=='.':
            t=[[-1 for l in range(w+2)] for l2 in range(h+2)]
            time=0
            q1=deque([])
            t[i+1][j+1]=time
            q1.appendleft([i+1,j+1])
            while len(q1)!=0:
                q=q1.pop()
                time=t[q[0]][q[1]]+1
                if s[q[0]+1][q[1]]=='.' and t[q[0]+1][q[1]]==-1:
                    t[q[0]+1][q[1]]=time
                    q1.appendleft([q[0]+1,q[1]])
                if s[q[0] - 1][q[1]] == '.' and t[q[0]-1][q[1]] == -1:
                    t[q[0] - 1][q[1]] = time
                    q1.appendleft([q[0] - 1, q[1]])
                if s[q[0]][q[1]+1] == '.' and t[q[0]][q[1]+1] == -1:
                    t[q[0] ][q[1]+1] = time
                    q1.appendleft([q[0] , q[1]+1])
                if s[q[0]][q[1]-1] == '.' and t[q[0]][q[1]-1] == -1:
                    t[q[0] ][q[1]-1] = time
                    q1.appendleft([q[0], q[1]-1])
            m=max(max(itertools.chain.from_iterable(t)),m)
print(m)

Solution (Python):
import collections

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

ans=0
for i in range(h):
  for j in range(w):
    if board[i][j]=='
      continue
    q=collections.deque()
    q.append((i,j,0))
    checked=[[0]*w for _ in range(h)]
    checked[i][j]=1
    while 1:
      y,x,s=q.popleft()
      if x>0 and board[y][x-1]!='
        q.append((y,x-1,s+1))
        checked[y][x-1]=1
      if x<w-1 and board[y][x+1]!='
        q.append((y,x+1,s+1))
        checked[y][x+1]=1
      if y>0 and board[y-1][x]!='
        q.append((y-1,x,s+1))
        checked[y-1][x]=1
      if y<h-1 and board[y+1][x]!='
        q.append((y+1,x,s+1))
        checked[y+1][x]=1
      if len(q)==0:
        ans=max(ans,s)
        break
print(ans)

Solution (Python):
from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()

Solution (Python):
h,w = map(int,input().split())
field = [list(input())for i in range(h)]
a= [[10**4]*w for i in range(h)]

vec = [(-1,0),(1,0),(0,1),(0,-1)]
ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == "
        stack = [(i,j)]
        visited = [[0]*w for i in range(h)]
        a[i][j] = 0
        
        while stack:
            next = []
            for x,y in stack:
                
                if visited[x][y]:continue

                visited[x][y] = 1
                

                for tx,ty in vec:
                    nx = x+tx
                    ny = y+ty
                    if nx < 0 or ny <0 or nx >=h or ny >=w:continue
                    if field[nx][ny] == "
                    if visited[nx][ny]:continue
                    next.append((nx,ny))
                    a[nx][ny] = min(a[x][y] + 1,a[nx][ny])
                    
                    
            stack = next
   
        for m in range(h):
            for n in range(w):
                if a[m][n] != 10**4:
                    ans = max(ans,a[m][n])
                a[m][n] = 10**4
print(ans)

Solution (Python):
import queue
import copy
 
def ngoin(bo,now):
    return 0 <= now[0] and now[0] < len(bo) and 0 <= now[1] and now[1] < len(bo[0])
 
def minido(bo,si,sj):
    tb = [[False for i in range(len(bo[0]))] for j in range(len(bo))]
    q = queue.Queue()
    q.put([si,sj,0])
    tb[si][sj] = True
    ret = 0
    while not q.empty():
        now = q.get()
        ret = now[2]
        if ngoin(bo,[now[0]-1,now[1]]):
            if bo[now[0]-1][now[1]] and not tb[now[0]-1][now[1]]:
                q.put([now[0]-1,now[1],now[2]+1])
                tb[now[0]-1][now[1]] = True
                
        if ngoin(bo,[now[0],now[1]+1]):
            if bo[now[0]][now[1]+1] and not tb[now[0]][now[1]+1]:
                q.put([now[0],now[1]+1,now[2]+1])
                tb[now[0]][now[1]+1] = True
                
        if ngoin(bo,[now[0]+1,now[1]]):
            if bo[now[0]+1][now[1]] and not tb[now[0]+1][now[1]]:
                q.put([now[0]+1,now[1],now[2]+1])
                tb[now[0]+1][now[1]] = True
                
        if ngoin(bo,[now[0],now[1]-1]):
            if bo[now[0]][now[1]-1] and not tb[now[0]][now[1]-1]:
                q.put([now[0],now[1]-1,now[2]+1])
                tb[now[0]][now[1]-1] = True
    return ret
            
 
h,w = map(int,input().split())
bo = [[True if x == '.' else False for x in input()] for i in range(h)]
grap = [[float('inf') for i in range(h*w)] for j in range(h*w)]
ans = 0
for i in range(h*w):
    grap[i][i] = 0
for si in range(h):
    for sj in range(w):
        if not bo[si][sj]:
            continue
        ans = max(ans,minido(bo,si,sj))
                
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())

graph_list = []
for i in range(H):
    temp_graph_str = str(input())
    temp_list = [1 if i == "." else 0 for i in temp_graph_str]
    graph_list.append(temp_list)

graph_tree_list = []
for i in range(H):
    for j in range(W):
        temp_list = [0 for x in range(H * W)]
        if graph_list[i][j] == 1:
            if i > 0:
                if graph_list[i - 1][j] == 1:
                    temp_list[(i - 1) * W + j] = 1
            if i < H - 1:
                if graph_list[i + 1][j] == 1:
                    temp_list[(i + 1) * W + j] = 1
            if j > 0:
                if graph_list[i][j - 1] == 1:
                    temp_list[i * W + (j - 1)] = 1
            if j < W - 1:
                if graph_list[i][j + 1] == 1:
                    temp_list[i * W + (j + 1)] = 1
        graph_tree_list.append(temp_list)

graph_tree_array = np.array(graph_tree_list)

sp = shortest_path(graph_tree_array, directed=False, unweighted=True)


sp[np.isinf(sp)] = 0
print(int(np.max(sp)))

Solution (Python):
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
import numpy as np

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

v_id_dict = {}
dista = np.ones((400, 400)) * np.inf

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            v_id_dict[i, j] = len(v_id_dict)

            if (i > 0) and (S[i - 1][j] == "."):
                dista[v_id_dict[(i, j)], v_id_dict[(i - 1, j)]] = 1

            if (j > 0) and (S[i][j - 1] == "."):
                dista[v_id_dict[(i, j)], v_id_dict[(i, j - 1)]] = 1

dist_mat = dijkstra(
    csgraph_from_dense(dista[: len(v_id_dict), : len(v_id_dict)]),
    directed=False,
    unweighted=False,
)

print(int(dist_mat.max()))

Solution (Python):

import sys

def solve(h, w, a):
    dp = [[-1] * (h * w) for _ in range(h * w)]
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    def bfs(x1, y1, x2, y2):
        s = y1 * w + x1
        t = y2 * w + x2
        visited = [[False] * w for _ in range(h)]
        cur = []
        visited[y1][x1] = True
        cur.append((x1, y1))
        cnt = 1
        while True:
            nex = []
            for x, y in cur:
                for i in range(4):
                    tx = x + dx[i]
                    ty = y + dy[i]
                    if 0 <= tx < w and 0 <= ty < h and a[ty][tx] != '
                        visited[ty][tx] = True
                        dp[s][ty * w + tx] = cnt
                        dp[ty * w + tx][s] = cnt
                        if tx == x2 and ty == y2:
                            return cnt
                        nex.append((tx, ty))
            if len(nex) > 0:
                cur = nex
            else:
                break
            cnt += 1
        return -1

    ret = -1
    for i in range(h):
        for j in range(w):
            for i2 in range(h):
                for j2 in range(w):
                    if (i == i2 and j == j2):
                        dp[w * i + j][w * i2 + j2] = 0
                        dp[w * i2 + j2][w * i + j] = 0
                    elif a[i][j] == '.' and a[i2][j2] == '.' and dp[w * i + j][w * i2 + j2] < 0:
                        tmp = bfs(j, i, j2, i2)
                        ret = max(ret, tmp)
                        
                        
                        
                        
    print(ret)
    return

def main():
    h, w = map(int, input().split())
    a = []
    for i in range(h):
        a.append(input())
    solve(h, w, a)

if __name__ == '__main__':
    main()

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

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))

def bfs(s):
    q = deque([(s, 0)])
    dist = {v: -1 for v in V}
    while q:
        v, d = q.popleft()
        if dist[v] >= 0: continue
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                q.append((u, d+1))
    return dist

ans = 0
for v in V:
    dist = bfs(v)
    ans = max(ans, max(dist.values()))
print(ans)