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):
row,col=map(int,input().split())
maze=[list(input()) for _ in range(row)]
result = []
 
def create_next_adj_list(point):
  cur_x, cur_y, cur_depth = point
  return [(cur_x, cur_y+1, cur_depth+1), (cur_x+1, cur_y, cur_depth+1), (cur_x, cur_y-1, cur_depth+1), (cur_x-1, cur_y, cur_depth+1)]
 
for r in range(row):
  for c in range(col):
    if maze[r][c] == '.':
 
      visited = [ [0]*col for _ in range(row)]
      visited[r][c] = -1
    
      adj_list = [(r, c+1, 0), (r+1, c, 0), (r, c-1, 0), (r-1, c, 0)]

      while adj_list:
        point = adj_list.pop(0)

        if 0<=point[0]<row and 0<=point[1]<col and visited[point[0]][point[1]] != -1:
          visited[point[0]][point[1]] = -1
          if maze[point[0]][point[1]] != '
            for adj in create_next_adj_list(point):
              adj_list.append(adj)

      result.append(point[-1])

print(max(result))

Solution (Python):
import bisect
import math
from queue import Queue
import sys
from copy import copy, deepcopy
from collections import defaultdict, Counter, deque
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush

read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines 

inf = float("inf")


def main():

    H, W = map(int, readline().split())
    S = [[s for s in input()] for h in range(H)]
    
    ret = 0
    delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                tmp_ret = 0
                maze = deepcopy(S)
                maze[h][w] = tmp_ret
                
                q1 = Queue()
                q1.put((h, w))
                
                q2 = Queue()
                
                while not (q1.empty() and q2.empty()):
                    while not q1.empty():
                        h, w = q1.get()
                        for dh, dw in delta:
                            if h + dh < H and h + dh >= 0 \
                            and w + dw < W and w + dw >= 0 \
                            and maze[h + dh][w + dw] == '.':
                                maze[h + dh][w + dw] = '
                                q2.put((h + dh, w + dw))

                    if not q2.empty():
                        q1 = q2
                        q2 = Queue()
                        tmp_ret += 1
                        
                ret = max(ret, tmp_ret)
    
    print(ret)


if __name__ == "__main__":
    main()

Solution (Python):
import bisect
import math
from queue import Queue
import sys
from copy import copy, deepcopy
from collections import defaultdict, Counter, deque
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush

read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines 


inf = float("inf")

def main():

    H, W = map(int, readline().split())
    S = [[s for s in input()] for h in range(H)]
    
    ret = 0
    
    delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    
    
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                tmp_ret = 0
                maze = deepcopy(S)
                maze[h][w] = tmp_ret
                
                q1 = Queue()
                q1.put((h, w))
                
                q2 = Queue()
                
                while not (q1.empty() and q2.empty()):
                    while not q1.empty():
                        h, w = q1.get()
                        for dh, dw in delta:
                            if h + dh < H and h + dh >= 0 \
                            and w + dw < W and w + dw >= 0 \
                            and maze[h + dh][w + dw] == '.':
                                maze[h + dh][w + dw] = tmp_ret
                                q2.put((h + dh, w + dw))

                    if not q2.empty():
                        q1 = q2
                        q2 = Queue()
                        tmp_ret += 1
                        
                ret = max(ret, tmp_ret)
    
    print(ret)


if __name__ == "__main__":
    main()

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

d=((-1,0),(0,-1),(1,0),(0,1))
ans_l=set()

def search(pos):
    D=[[0]*W for _ in range(H)]
    while len(pos)>0:
        x,y,depth=pos.popleft()
        D[x][y]=-1
        for i in range(4):
            nx=x+d[i][0]
            ny=y+d[i][1]
            if 0<=nx<H and 0<=ny<W and MAZE[nx][ny]=='.' and D[nx][ny]!=-1:
                pos.append((nx,ny,depth+1))
                D[nx][ny]=-1
    return depth

for i in range(H):
    for j in range(W):
        if MAZE[i][j]=='.':
            p=deque([[i,j,0]])
            ans_l.add(search(p))

print(max(ans_l))

Solution (Python):
INF = 1001001001
from collections import deque
di = [-1, 0, 1 ,0]
dj = [ 0,-1, 0, 1]

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

ans = 0
for si in range(H):
    for sj in range(W):
        if S[si][sj] == '
        q = deque([(si, sj)])
        d = [[INF] * W for _ in range(H)]
        d[si][sj] = 0
        while q:
            i, j = 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] == '
                if d[ni][nj] == INF:
                    d[ni][nj] = d[i][j] + 1
                    q.append((ni,nj))
        tmp = 0
        for i in range(H):
            for j in range(W):
                if d[i][j] != INF:
                    tmp = max(tmp, d[i][j])
        ans = max(ans, tmp)
print(ans)

Solution (Python):
n, m = list(map(int, input().split()))
maze = []
for i in range(n):
  l = input()
  dl = []
  for j in range(m):
    if l[j] == '.':
      dl.append(0)
    else:
      dl.append(1)
  maze.append(dl)
ans = 0
for i in range(n):
  for j in range(m):
    if maze[i][j] == 0:
      a = [list(l) for l in maze]
      a[i][j] = 1
      q = [(i, j)]
      d = 0
      while len(q) > 0:
        nq = []
        for x, y in q:
          if x > 0 and a[x - 1][y] == 0:
            a[x - 1][y] = 1
            nq.append((x - 1, y))
          if y > 0 and a[x][y - 1] == 0:
            a[x][y - 1] = 1
            nq.append((x, y - 1))
          if x < n - 1 and a[x + 1][y] == 0:
            a[x + 1][y] = 1
            nq.append((x + 1, y))
          if y < m - 1 and a[x][y + 1] == 0:
            a[x][y + 1] = 1
            nq.append((x, y + 1))
        if len(nq) > 0:
          d += 1
        q = nq
      ans = max(ans, d)
print(ans)

Solution (Python):
from collections import deque

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

def bfs(sy, sx):
    if S[sy][sx] == '
        return 0
        
    reached = [[-1]*W for _ in range(H)]
    que = deque([[sy, sx]])
    reached[sy][sx] = 0
    
    while que:
        [y, x] = que.pop()
        for i in range(4):
            yy, xx = y + dy[i], x + dx[i]
            if yy < 0 or xx < 0 or yy > H-1 or xx > W-1 or S[yy][xx] == '
                continue
            else:
                reached[yy][xx] = reached[y][x] + 1
                que.appendleft([yy, xx])
                
    distance = 0
    for i in range(H):
        for j in range(W):
            distance = max(distance, reached[i][j])
            
    return distance

ans = 0
for a in range(H):
    for b in range(W):
        ans = max(ans, bfs(a, b))

print(ans)

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

def bfs(maze, sy, sx, H, W):
    queue = deque([[sy, sx]])
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = 0
    di = [-1, 0, 1, 0]
    dj = [0, -1, 0, 1]
    while queue:
        y, x = queue.popleft()
        for dir in range(4):
            new_y, new_x = y+di[dir], x+dj[dir]
            if new_x >= W or new_y >= H:
                pass
            elif new_x < 0 or new_y < 0:
                pass
            elif 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

H, W = map(int, input().split())
MAZE = [input() for _ in range(H)]
ans = 0
tmp = 0
for i in range(H):
    for j in range(W):
        if MAZE[i][j] == "
            continue
        tmp = np.max(bfs(MAZE, i, j, H, W))
        ans = max(ans, tmp)
print(ans)

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

for i in range(H):
    S = input()
    for j in range(W):
        s = S[j]
        if s=='.':
            D[i][j] = 1

ans = 0
import heapq

for i in range(H):
    for j in range(W):
        if D[i][j] == 1:
            tmp = 0
            h = [[0,i,j]]
            visited = [[0]*W for i in range(H)]
            while h!=[]:
                w,nowi,nowj = heapq.heappop(h)
                tmp = max(tmp,w)
                visited[nowi][nowj] = 1
                if 0<nowi<H-1:
                    for k in [-1,1]:
                        if D[nowi+k][nowj]==1 and visited[nowi+k][nowj]==0:
                            heapq.heappush(h,[w+1,nowi+k,nowj])
                            visited[nowi+k][nowj]=1
                elif nowi+1<=H-1:
                    if D[nowi+1][nowj]==1 and visited[nowi+1][nowj]==0:
                        heapq.heappush(h,[w+1,nowi+1,nowj])
                        visited[nowi+1][nowj]=1
                elif nowi-1 >=0:
                    if D[nowi-1][nowj]==1 and visited[nowi-1][nowj]==0:
                        heapq.heappush(h,[w+1,nowi-1,nowj])
                        visited[nowi-1][nowj]=1

                if 0<nowj<W-1:
                    for k in [-1,1]:
                        if D[nowi][nowj+k]==1 and visited[nowi][nowj+k]==0:
                            heapq.heappush(h,[w+1,nowi,nowj+k])
                            visited[nowi][nowj+k]=1
                elif nowj-1>=0:
                    if D[nowi][nowj-1]==1 and visited[nowi][nowj-1]==0:
                        heapq.heappush(h,[w+1,nowi,nowj-1])
                        visited[nowi][nowj-1]=1
                elif nowj+1 <= W-1:
                    if D[nowi][nowj+1]==1 and visited[nowi][nowj+1]==0:
                        heapq.heappush(h,[w+1,nowi,nowj+1])
                        visited[nowi][nowj+1]=1
            ans = max(ans,tmp)
            
print(ans)

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

H, W = map(int, input().split())
S = np.zeros((H, W), dtype='U1')
for hi in range(H):
    raw = input()
    S[hi, :] = list(raw)

maxmove = np.zeros_like(S, dtype='int')

for hi, wi in product(range(H), range(W)):
    
    if S[hi, wi] == '

    
    VisitOrScheduled = np.zeros_like(S, dtype='bool')
    VisitOrScheduled[hi, wi] = True
    nummove = np.zeros_like(S, dtype='int')
    deq = deque()

    deq.append((hi, wi))
    while True:
        try:
            hj, wj = deq.popleft()
        except IndexError:
            break
        VisitOrScheduled[hj, wj] = True
        for neighbour in [(hj, wj-1), (hj, wj+1), (hj+1, wj), (hj-1, wj)]:
            if not (0 <= neighbour[0] < H and 0 <= neighbour[1] < W): continue
            if S[neighbour] == '
                continue
            if not VisitOrScheduled[neighbour]:
                nummove[neighbour] = nummove[hj, wj] + 1
                deq.append(neighbour)
                VisitOrScheduled[neighbour] = True
    
    maxmove[hi, wi] = np.max(nummove)

print(np.max(maxmove))

Solution (Python):






from queue import Queue
from collections import deque
from itertools import product
import numpy as np

H, W = map(int, input().split())
S = np.zeros((H, W), dtype='U1')
for hi in range(H):
    raw = input()
    S[hi, :] = list(raw)

maxmove = np.zeros_like(S, dtype='int')

for hi, wi in product(range(H), range(W)):
    
    if S[hi, wi] == '

    
    
    
    
    VisitOrScheduled = np.zeros_like(S, dtype='bool')
    VisitOrScheduled[hi, wi] = True
    nummove = np.zeros_like(S, dtype='int')
    
    deq = deque()

    
    deq.append((hi, wi))
    
    while True:
        try:
            
            hj, wj = deq.popleft()
        except IndexError:
            break
        
        VisitOrScheduled[hj, wj] = True
        for neighbour in [(hj, wj-1), (hj, wj+1), (hj+1, wj), (hj-1, wj)]:
            if not (0 <= neighbour[0] < H and 0 <= neighbour[1] < W): continue
            if S[neighbour] == '
                continue
            
            if not VisitOrScheduled[neighbour]:
                nummove[neighbour] = nummove[hj, wj] + 1
                
                deq.append(neighbour)
                
                VisitOrScheduled[neighbour] = True
    
    maxmove[hi, wi] = np.max(nummove)

print(np.max(maxmove))

Solution (Python):
from collections import deque




def make_list(i, j):
    global c
    global h
    global w

    l = []
    a = [-1, 0, 1]
    b = [-1, 0, 1]

    for y in a:
        for x in b:
            if i+y < 0 or j+x < 0 or i+y >= h or j+x >= w:
                continue
            if (x == 0 and y == 0) or (abs(x) == 1 and abs(y) == 1):
                continue
            if c[i][j] == 1:
                continue
            if c[i + y][j + x] == 0:
                l.append((i+y)*w + (j+x))

    return l

hw = list(map(int, input().split()))
h = hw[0]
w = hw[1]

c = [[0] * w for i in range(h)]

for i in range(h):
    line = input()
    for j in range(w):
        if line[j] == '.':
            c[i][j] = 0
        else:
            c[i][j] = 1

rlist = []
for i in range(h):
    for j in range(w):
        rlist.append(make_list(i, j))

def bfs(u):
    color[u] = 'gray'
    d[u] = 0
    queue.append(u)

    while(len(queue) > 0):
        u = queue.popleft()
        for rl in rlist[u]:
            if color[rl] == 'white':
                queue.append(rl)
                color[rl] = 'gray'
                d[rl] = d[u] + 1
        color[u] = 'black'

result = 0
for i in range(len(rlist)):
    color = ['white'] * len(rlist)
    queue = deque([])
    d = [-1] * len(rlist)
    if len(rlist[i]) > 0:
        bfs(i)
        if result < max(d):
            result = max(d)

print(result)

Solution (Python):
from collections import deque

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

area = [[] for _ in range(h+2)]

for i in range(h+2):
    if i == 0 or i == h+1:
        area[i] = ['
    else:
        area[i] = list(input())
        area[i].insert(0, '
        area[i].append('

def bfs(i, j):
    distance_matrix = [[1000 for _ in range(w+2)] for _ in range(h+2)]
    distance_matrix[i][j] = 0
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    d = deque()
    d.append([i, j])
    max_distance = 0
    while len(d) > 0:
        x, y = d.popleft()
        for q, v in move:
            if area[x+q][y+v] =='.' and distance_matrix[x+q][y+v] == 1000:
                d.append([x+q,y+v])
                distance = distance_matrix[x][y] + 1
                distance_matrix[x+q][y+v] = distance
                if distance > max_distance:
                    max_distance = distance
    return max_distance

max_distance = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if area[i][j] == '
            continue
        else:
            distance = bfs(i, j)
            if distance > max_distance:
                max_distance = distance


print(max_distance)

Solution (Python):
""""
3 5
...
.
.
"""
from collections import deque
import numpy as np

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


def make_wall(W, Map):
    for map_row in Map:
        map_row.append("
        map_row.insert(0, "

    wall = ["
    Map.append(wall)
    Map.insert(0, wall)
    return Map


start_list = deque()
search_list = deque()
Map = make_wall(W, Map)
H += 2
W += 2

start_h = 0
for h in range(H):
    start_w = 0
    for w in range(W):
        if Map[h][w] == ".":
            start_list.append([start_h, start_w])
        start_w += 1
    start_h += 1



max_cost = 0
while start_list != deque():
    search_list.append(start_list.popleft())
    cost_map = np.array([[0] * W for i in range(H)])
    search_map = np.array([[0] * W for i in range(H)])

    while search_list != deque():
        tmp = search_list.popleft()
        x = tmp[0]
        y = tmp[1]
        search_map[x][y] = 1
        if Map[x][y+1] == "." and search_map[x][y+1] == 0 and [x, y+1] not in search_list:
            search_list.append([x, y+1])
            cost_map[x][y+1] = cost_map[x][y]+1
        if Map[x][y-1] == "." and search_map[x][y-1] == 0 and [x, y-1] not in search_list:
            search_list.append([x, y-1])
            cost_map[x][y-1] = cost_map[x][y]+1
        if Map[x+1][y] == "." and search_map[x+1][y] == 0 and [x+1, y] not in search_list:
            search_list.append([x+1, y])
            cost_map[x+1][y] = cost_map[x][y]+1
        if Map[x-1][y] == "." and search_map[x-1][y] == 0 and [x-1, y] not in search_list:
            search_list.append([x-1, y])
            cost_map[x-1][y] = cost_map[x][y]+1
    cost_map = np.array(cost_map)
    if max_cost < np.amax(cost_map):
        max_cost = np.amax(cost_map)

print(max_cost)

Solution (Python):
from queue import Queue
INF = 999999


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

m = 0
for si in range(H):
    for sj in range(W):
        if S[si][sj] == '
            continue
        
        q = Queue()
        q.put((si, sj, 0))
        done = [None] * H
        for i in range(H):
            done[i] = [False] * W
        done[si][sj] = True

        unit = ((1, 0), (-1, 0), (0, 1), (0, -1))
        while not q.empty():
            i, j, w = q.get()

            for u in unit:
                nexti = i + u[0]
                nextj = j + u[1]
                if nexti >= 0 and nexti < H and nextj >= 0 and nextj < W and S[nexti][nextj] == '.' and (not done[nexti][nextj]):
                    q.put((nexti, nextj, w+1))
                    m = max(m, w + 1)
                    done[nexti][nextj] = True
print(m)

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

maze=[]
maze.append(["
for h in range(H):
    line=list(input())

    maze.append(["

maze.append(["


maze_ori=copy.deepcopy(maze)

maxd=0

for h in range(1,H+1):
    for w in range(1,W+1):
        maze=copy.deepcopy(maze_ori)
        if maze[h][w]=="
            continue
        else:
            next_flag=True


        direction=[[-1,0],[0,-1],[1,0],[0,1]]
        distance=0
        maze[h][w]=distance

        next_list=[]
        next_list.append([h,w])
        while next_flag is True:
            p_list=next_list
            next_list=[]
            distance+=1
            next_flag=False
            for p in p_list:
                for d in direction:
                    i=p[0]+d[0]
                    j=p[1]+d[1]

                    if maze[i][j]==".":
                        maze[i][j]=distance
                        next_list.append([i,j])
                        next_flag=True
            
        maxd=max(maxd,distance-1)

print(maxd)

Solution (Python):
from itertools import count, combinations, product

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

H += 2
W += 2

visited = [2**31]*(W*H)

for i in range(1,H-1):
    S = input()
    for j,v in zip(range(1,W-1),S):
        if v == '.':
            visited[i*W + j] = 0

res = 1
D = (W,-W,1,-1)

for i in range(W*H):
    if visited[i] == 2**31:
        continue
    q = [i]
    visited[i] = i
    for dist in count():
        if not q:
            break
        nq = []
        for j in q:
            for d in D:
                if visited[j+d] < i:
                    visited[j+d] = i
                    nq.append(j+d)
        q = nq
    res = max(dist, res)

print(res-1)

Solution (Python):
from itertools import count, combinations, product

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

grid = [[False]*(W+2) for _ in range(H+2)]

for i in range(1,H+1):
    S = input()
    for j,v in zip(range(1,W+1),S):
        grid[i][j] = v == '.'

visited = [[0 if v else float('inf') for v in row] for row in grid]
cnt = 1
res = 0
for i,j in product(range(H+2),range(W+2)):
    if not grid[i][j]:
        continue
    q = [(i,j)]
    visited[i][j] = cnt 
    for d in count():
        if not q:
            break
        nq = []
        for x,y in q:
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                if visited[x+dx][y+dy] < cnt:
                    visited[x+dx][y+dy] = cnt
                    nq.append((x+dx,y+dy))
        q = nq
    cnt += 1
    res = max(d-1, res)

print(res)

Solution (Python):
from collections import deque
from itertools import chain
INF = 10**18 
H, W = map(int, input().split())
S = [input() for _ in range(H)]
def main():
    max_num = 0
    for sy in range(H):
        for sx in range(W):
            if S[sy][sx] == "
                continue
            m = check_max_route(sx, sy)
            max_num = max(max_num, m)
    print(max_num)
    
def check_max_route(x,y):
    state=[[INF for _ in range(W)] for _ in range(H)]
    state[y][x]=0
    q = deque([(x, y)])
    while q:
        tx, ty = q.popleft()
        tr = state[ty][tx]
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            x, y = tx+dx, ty+dy
            if not (0 <= x < W and 0 <= y < H):
                continue
            if S[y][x] == "
                continue
            if state[y][x] <= tr+1:
                continue
            state[y][x] = tr+1
            q.append((x, y))
    m = max([x for x in chain(*state) if x != INF])
    return m    
main()

Solution (Python):
from itertools import count, combinations, product

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

grid = [[False]*(W+2) for _ in range(H+2)]

for i in range(1,H+1):
    S = input()
    for j,v in zip(range(1,W+1),S):
        grid[i][j] = v == '.'

visited = [[0 if v else float('inf') for v in row] for row in grid]
cnt = 1
def dist(p1,p2):
    global cnt
    q = [p1]
    visited[p1[0]][p1[1]] = cnt 
    for d in count():
        if not q:
            break
        nq = []
        for x,y in q:
            if (x,y) == p2:
                cnt += 1
                return d
            else:
                for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                    if visited[x+dx][y+dy] < cnt:
                        visited[x+dx][y+dy] = cnt
                        nq.append((x+dx,y+dy))
        q = nq
    cnt += 1
    return float('inf')

emp = [(i,j) for i,j in product(range(H+2),range(W+2)) if grid[i][j]]

print(max(dist(*p) for p in combinations(emp,2)))

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

INF = 10**18

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

def check_max_route(sx, sy):
    r = [[INF for _ in range(W)] for _ in range(H)]
    r[sy][sx] = 0
    q = deque([(sx, sy)])
    while q:
        tx, ty = q.popleft()
        tr = r[ty][tx]

        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            x, y = tx+dx, ty+dy
            if not (0 <= x < W and 0 <= y < H):
                continue
            if S[y][x] == "
                continue
            if r[y][x] <= tr+1:
                continue
            r[y][x] = tr+1
            q.append((x, y))
    
    m = max([x for x in chain(*r) if x != INF])
    return m

max_num = 0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == "
            continue
        m = check_max_route(sx, sy)
        max_num = max(max_num, m)

print(max_num)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = ''
for _ in range(h):
    maze += input() + '
n = h*(w+1)
graph = [[] for _ in range(n)]
dire = [-w-1, -1, 1, w+1]
for i in range(n):
    if maze[i]=='
        continue
    for j in dire:
        ind = i+j
        if ind < 0 or n <= ind or maze[ind]=='
            continue
        graph[i].append(ind)
que = deque()
def BFS(node):
    for i in graph[node]:
        if lengths[i]<0:
            lengths[i] = lengths[node]+1
            que.append(i)
    if len(que)>0:
        BFS(que.popleft())
starts = [i for i, j in enumerate(graph) if len(j)>0]
max_len = 0
for start in starts:
    lengths = [-1]*n
    lengths[start] = 0
    BFS(start)
    max_len = max(max_len, max(lengths))
print(max_len)

Solution (Python):
from queue import Queue

def solve(h, w, SS):
    m = {
        (x, y): S[x] == '.'
        for y, S in enumerate(SS)
        for x in range(len(S))
    }
    conditions = {
        (-1, 0): lambda x, y: x > 0,
        (1, 0): lambda x, y: x < w - 1,
        (0, -1): lambda x, y: y > 0,
        (0, 1): lambda x, y: y < h - 1
    }

    def calc_max_len(x0, y0):
        q = Queue(maxsize = h * w)
        q.put((x0, y0))
        d = {(x0, y0): 0}
        max_len = 0
        while not q.empty():
            x, y = q.get(block=False)
            for dx, dy in conditions:
                key = (x + dx, y + dy)
                if conditions[(dx, dy)](x, y) and m[key] and key not in d:
                    q.put(key)
                    d[key] = d[(x, y)] + 1
            if max_len < d[(x, y)]:
                max_len = d[(x, y)]
        return max_len

    return max(calc_max_len(x, y) for x, y in filter(lambda key: m[key], m))

_h, _w = map(int, input().split())
_SS = [input() for _ in range(_h)]
print(solve(_h, _w, _SS))

Solution (Python):
from collections import deque
H,W = map(int,input().split())
maze = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ls = []
count = 0
for i in range(H):
    tmp = list(input())
    maze.append(tmp)
    for j in range(W):
        if tmp[j] != "
            ls.append([i,j])
            count += 1
def bfs(sx,sy):
    INF = -1
    cost = [[INF]*W for _ in range(H)]
    P = deque()
    P.append([sx,sy])
    cost[sx][sy] = 0
    while len(P) != 0:
        p = P.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "
                P.append([nx,ny])
                cost[nx][ny] = cost[p[0]][p[1]]+1
    return cost
def solve():
    ans = 0
    for i in ls:
        sx,sy = i[0],i[1]
        cs = bfs(sx,sy)
        for k in range(len(cs)):
            if ans == count:
                break
            if max(cs[k]) > ans:
                ans = max(cs[k])
    return ans
print(solve())

Solution (Python):
import itertools
H,W= [int(x) for x in input().split()]
meiro=[list(input())for _ in range(H)]

ans=0
dx = [1,0,-1,0]
dy=[0,1,0,-1]
for i in range(H):
  for j in range(W):
    result=[[0]*W for _ in range(H)]
    cnt=0
    
    if meiro[i][j]=="
      continue
    elif meiro[i][j]==".":
      stk =[[i,j]]
      result[i][j]=1
      while stk:
        x,y = stk.pop(0)
        
        for r in range(4):
          xx,yy=x+dx[r],y+dy[r]
          if yy<0 or xx<0 or W<=yy or H<=xx or meiro[xx][yy]=="
            continue
          result[xx][yy]=result[x][y]+1
          stk.append([xx,yy])
      for l in range(H):
        for t in range(W):
          ans = max(ans,result[l][t])
print(ans-1)

Solution (Python):
import numpy as np
def min_rounte(s, sta, path):
    move = [[0,1],[0,-1],[1,0],[-1,0]]
    for i in move:
        ax = [sta[0]+i[0], sta[1]+i[1]]
        if s[ax[0]][ax[1]] == -1:
            continue
        if s[ax[0]][ax[1]] > path:
            s[ax[0]][ax[1]] = path
    return s
 
def bfs(s, sta):
    s_ = np.array(s)
    s_[sta[0]][sta[1]] = 0
    tmp = sta
    for i in range(400):
        ind = np.where(s_==i)
        for j in range(len(ind[0])):
            s_ = min_rounte(s_, [ind[0][j], ind[1][j]], i+1)
        if len(ind[0]) == 0:
            break
        tmp = [[ind[0][k], ind[1][k]] for k in range(len(ind[0]))]
    return i-1, tmp
        

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

s = [[-1 for i in range(w+2)] for j in range(h+2)]
for i in range(h):
    a = input()
    for j in range(w):
        if a[j] == ".":
            s[i+1][j+1] = 512
        else:
            s[i+1][j+1] = -1

for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j] == -1:
            continue
        temp, ax = bfs(s, [i,j])
        break
ans = 1
for i in ax:
    ans_, t = bfs(s, i)
    if ans_ > ans:
        ans = ans_

print(ans)

Solution (Python):
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    st = [(h, w) for h in range(H) for w in range(W)]  

    def bfs(sy, sx):
        que = deque()
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))

    ans = 0
    for s in st:
        dist = [[-1]*W for h in range(H)]
        if c[s[0]][s[1]] == "
            continue
        bfs(*s)
        for t in st:
            if s == t or c[t[0]][t[1]] == "
                continue
            ans = max(ans, dist[t[0]][t[1]])
    print(ans)


if __name__ == '__main__':
    main()