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 numpy as np
import queue
from collections import deque

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

maze = np.zeros((H, W))

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

max_run = 0

tan = [[1, 0], [-1, 0], [0, 1], [0, -1]]
g = (100, 100)

def max_route(h, w):
    
    q = deque()
    checker = maze.copy()
    q.append((h, w))
    checker[h, w] = 2
    q.append(g)

    run = 0

    while len(q):
        target = q.popleft()
        if target == g:
            if len(q):
                run += 1
                q.append(g)
        else:
            for t in tan:
                check = [target[0]+t[0], target[1]+t[1]]
                if 0 <= check[0] < H and 0 <= check[1] < W:
                    if checker[check[0], check[1]] == 1:
                        q.append((check[0], check[1]))
                        checker[check[0], check[1]] = 2

    return run


for h in range(H):
    for w in range(W):
        if maze[h, w] == 0:
            continue
        cur = max_route(h, w)
        if cur > max_run:
            max_run = cur

print(max_run)

Solution (Python):
from collections import deque

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


INF = 100000000
dist = [[[[INF for j2 in range(w)] for i2 in range(h)] for j1 in range(w)] for i1 in range(h)]

def dfs(i1, j1, i2, j2):
    dist[i1][j1][i2][j2] = 0
    q = deque([(i2, j2, 0)])
    while q:
        i3, j3, d = q.popleft()
        for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            i4 = i3 + di
            j4 = j3 + dj
            if (0 <= i4 < h) and (0 <= j4 < w):
                if s[i4][j4] == "
                    continue
                if d + 1 < dist[i1][j1][i4][j4]:
                    dist[i1][j1][i4][j4] = d + 1
                    q.append((i4, j4, d+1))


for i in range(h):
    for j in range(w):
        if s[i][j] == "
            continue
        dfs(i, j, i, j)

ans = 0
for i1 in range(h):
    for j1 in range(w):
        if s[i1][j1] == "
            continue
        for i2 in range(h):
            for j2 in range(w):
                if s[i2][j2] == "
                    continue
                ans = max(ans, dist[i1][j1][i2][j2])

print(ans)

Solution (Python):
h,w = map(int,input().split())
field = [list(input())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= [[0]*w for i in range(h)]
        
        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] = a[x][y]+1
                    
                    
            stack = next
        ans = max(ans,max(max(row)for row in a))
print(ans)

Solution (Python):
from collections import deque




def bfs():
    
    
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

    
    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()
        
        if p[0] == gx and p[1] == gy:
            break
        
        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] != "
                
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


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

count = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            count += 1
if count == 400:
    print(38)
    exit()

ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if sx == gx and sy == gy:
                        continue
                    if maze[gx][gy] == ".":
                        ans = max(ans, bfs())

print(ans)

Solution (Python):

from collections import deque
h,w = map(int, input().split())
s = [input() for _ in range(h)]

if h==1 and w==1:
    print(0)
    exit()

maxr = 0
for hi in range(h):
    for wi in range(w):
        if s[hi][wi]==".":
            maxr += 1

def solve(sh,sw):
    res = -1
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[sh][sw] = True
    q = deque([(sh,sw,0)])
    while len(q)>0:
        hi,wi,r = q.popleft()
        for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
            if hi+dh>=0 and hi+dh<h and wi+dw>=0 and wi+dw<w and s[hi+dh][wi+dw]==".":
                if not visited[hi+dh][wi+dw]:
                    visited[hi+dh][wi+dw] = True
                    q.append((hi+dh,wi+dw,r+1))
                    res = max(res, r+1)

    return res

res = -1
for shi in range(h):
    for swi in range(w):
        if s[shi][swi]=="
            continue
        r = solve(shi,swi)
        res = max(res, r)

print(res)

Solution (Python):
import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

sys.setrecursionlimit(10**9)
mod = 998244353
inf = 10**20

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


H,W = LI()
field = [list(input()) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j]==".":
            field[i][j]=inf

tmp = copy.deepcopy(field)

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


def bfs(sh,sw):
    field[sh][sw] = 0
    que = collections.deque([[sh,sw]])

    while que:
        h,w = que.popleft()
        for i in range(4):
            nh = h+dx[i]
            nw = w+dy[i]
            if (nh<0) or (nw<0) or (nw>W-1) or (nh>H-1):
                continue
            dist = field[nh][nw]
            if dist!="
                if dist>field[h][w]+1:
                    field[nh][nw] = field[h][w]+1
                    que.append([nh,nw])

    m = 0
    for i in range(H):
        for j in range(W):
            if field[i][j]!="
                if field[i][j]>m:
                    m = field[i][j]
    return m

for i in range(H):
    for j in range(W):
        field = copy.deepcopy(tmp)
        if field[i][j]=="
            continue
        ans.append(bfs(i,j))


print(max(ans))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)


from collections import deque
def bfs():
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while len(Q) > 0:
        q = Q.popleft()
        y,x =  q[0], q[1]
        if S[y][x] == "
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == "
                box[ny][nx] = -1
            if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == "." and box[ny][nx] == -1000:
                box[ny][nx] = box[y][x] + 1
                Q.append([ny,nx])
    for i in range(H):
        if len(box[i]) == 0:
            continue
        else:
            ans.append(max(box[i]))
    return


H, W = map(int,input().split())
S = [ [] for _ in range(H)]
for i in range(H):S[i] = list(input())
ans = []
Q = deque()
for i in range(H):
    for j in range(W):
        
        box = [[-1000 for _ in range(W)] for __ in range(H)]
        Q.append([i,j])
        box[i][j] = 0
        bfs()
if len(ans)==0:
    print(0)
    exit()
print(max(ans))

Solution (Python):
from collections import deque


H, W = [int(a) for a in input().split()]
S = [None for _ in range(H)]
for i in range(H):
    S[i] = list(input())


UNVISITED = -1

dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)



def bfs(sy, sx):
    dist = [[UNVISITED for _ in range(W)] for _ in range(H)]
    que = deque() 
    que.append((sx, sy))
    dist[sy][sx] = 0

    while(len(que) > 0):
        x, y = que.popleft()
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]

            if (0 <= nx < W) and (0 <= ny < H) and S[ny][nx] == '.' and dist[ny][nx] == UNVISITED:
                que.append((nx, ny))
                dist[ny][nx] = dist[y][x] + 1
    return( max( [max(dist[i]) for i in range(H)]))

m = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            m = max(m, bfs(i, j))

print(m)

Solution (Python):
h, w = map(int, input().split())
maze = [input() for i in range(h)]
graph = {}

for i, s_i in enumerate(maze):
  for j, s_ij in enumerate(s_i):
    if s_ij == ".":
      graph[i * w + j] = []
      if i > 0 and maze[i - 1][j] == ".":
        graph[i * w + j].append((i - 1) * w + j)
      if j > 0 and maze[i][j - 1] == ".":
        graph[i * w + j].append(i * w + j - 1)
      if j < w - 1 and maze[i][j + 1] == ".":
        graph[i * w + j].append(i * w + j + 1)
      if i < h - 1 and maze[i + 1][j] == ".":
        graph[i * w + j].append((i + 1) * w + j)

ans = 0
for start in graph.keys():
  dist = {}
  c = 0
  dist[start] = c
  hoge = {start}
  for _ in graph.keys():
    c += 1
    fuga = set()
    for h in hoge:
      fuga |= set(graph[h])
    fuga -= set(dist.keys())
    for f in fuga:
      dist[f] = c
    hoge = fuga
    if len(dist) == len(graph):
      break
  ans = max(ans, max(dist.values()))
  
print(ans)

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

from collections import deque

def dfs(maze, sh, sw):
    visited = [[0]*W for _ in range(H)]
    queue = deque([[sh, sw, 0]])
    visited[sh][sw] = 1
    maxlen = 0
    while queue:
        h, w , tmplen = queue.pop()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            temp = tmplen
            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] = 1
                temp += 1
                maxlen = max(maxlen, temp)
                queue.appendleft([new_h, new_w, temp])
    
    return maxlen

res = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '
            continue
        res = max(res, dfs(s, i, j))

print(res)

Solution (Python):

import queue
import copy

import time
sss = time.time()
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**9 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
l = 0

for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
            l += 1
if l >= H*W-(H-2):
    print(H+W-2)
    exit()
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start, bb):
    dist = [[10**9 for _ in range(W)] for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        bb[x][y] == '
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            if x+dx>=0 and x+dx<= H-1 and y+dy>=0 and y+dy<=W-1 and abs(dx-dy)==1:
                if bb[x+dx][y+dy] != '
                    if dist[x+dx][y+dy] > dist[x][y]:
                        dist[x+dx][y+dy] = dist[x][y] + 1
                        if dist[x+dx][y+dy] > far:
                            far = dist[x+dx][y+dy]
                        q.put((x+dx,y+dy))
        if q.empty():
            break
    return far
res = 0
while 1:
    ttt = time.time()
    if ttt-sss >= 1:
        break
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)

Solution (Python):
import sys
from collections import deque
from copy import deepcopy
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
sys.setrecursionlimit(10 ** 9)


def main():
    H, W = MAP()
    c = [list(INPUT()) for _ in range(H)]

    C = []
    for i in range(H+2):
        tmpc = []
        for j in range(W+2):
            if i == 0 or i == H+1 or j == 0 or j == W+1: tmpc.append(0)
            else: tmpc.append(c[i-1][j-1])
        C.append(tmpc)

    sp = deque()
    for i in range(H+2):
        for j in range(W+2):
            if C[i][j] == ".": sp.append([i, j])
            elif C[i][j] == "

    ans = 0
    while sp:
        copy_c = deepcopy(C)
        sy, sx = sp.popleft()
        copy_c[sy][sx] = 0
        d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        queue = deque([[sy, sx]])

        while queue:
            y, x = queue.popleft()
            for dy, dx in d:
                if copy_c[y+dy][x+dx] == ".":
                    copy_c[y+dy][x+dx] = copy_c[y][x] + 1
                    queue.append([y+dy, x+dx])

        tmp = -1
        for i in range(H+2):
            tmp = max(tmp, max(copy_c[i]))

        ans = max(tmp, ans)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
input = raw_input

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

meiro = []
coords = []
for i in range(h):
    line = list(input())
    cur_coords = [(j, i) for j in range(w) if line[j] == "."]
    coords += cur_coords
    meiro.append(line)

graphs = []
graph = {}
for cur_coord in coords:
    x, y = cur_coord
    tugi_kouhos = [(x+dx, y) for dx in [-1, 1] if 0 <= x+dx < w]
    tugi_kouhos += [(x, y+dy) for dy in [-1, 1] if 0 <= y+dy < h]
    childs = []
    for tugi_kouho in tugi_kouhos:
        if tugi_kouho in coords:
            childs.append(tugi_kouho)
    graph[cur_coord] = childs



def calc_depth(coord1):

    cur_coord = coord1
    
    cur_depth = 0
    used_coords = [coord1]

    childs = graph[coord1]
    while len(childs) != 0:
        cur_depth += 1
        next_childs = []
        used_coords += childs

        num_res_s = []
        for child in childs:
            res = get_childs(child, used_coords)
            
            
            num_res = len(res)
            num_res_s.append(num_res)
            next_childs += res
        if max(num_res_s) == 0:
            return cur_depth

        childs = list(set(next_childs))
        

    return 0

def get_childs(jibun, used_coords):
    
    childs = []
    for child in graph[jibun]:
        if child not in used_coords:
            childs.append(child)
    return childs
       
n_coords = len(coords)
max_depth = 0
for i in range(n_coords):
    coord1 = coords[i]
    cur_depth = calc_depth(coord1)
    max_depth = max(max_depth, cur_depth)

print(max_depth)

Solution (Python):
import queue
import copy

vx = [0,1,0,-1];
vy = [1,0,-1,0];
q = queue.Queue()

hw = input().split(' ');
h = int(hw[0]);
w = int(hw[1]);
s = [ [0]*w for i in range(h)];
for i in range(h) :
	si = input();
	for j in range(w) :
		s[i][j] = si[j];

s_alt = copy.deepcopy(s);
ans = 0;
for sy in range(h) :
	for sx in range(w) :
		s = copy.deepcopy(s_alt);
		if s[sy][sx] == '.' :
			q_a = [0]*2;
			q_a[0] = sy;
			q_a[1] = sx;
			q.put(q_a);
			s[sy][sx] = 0;
			while not q.empty() :
				q_a = q.get();
				for i in range(4):
					ny = q_a[0] + vy[i];
					nx = q_a[1] + vx[i];
					if ny >= 0 and ny < h and nx >= 0 and nx < w and s[ny][nx] == '.':
						s[ny][nx] = s[q_a[0]][q_a[1]] + 1;
						q_b = [0]*2;
						q_b[0] = ny;
						q_b[1] = nx;
						q.put(q_b);
			max_path = 0;
			for i in range(h) :
				for j in range(w) :
					if s[i][j] == '
						continue;
					elif s[i][j] > max_path :
						max_path = s[i][j];
			if max_path > ans :
				ans = max_path;

print(ans);

Solution (Python):
from collections import deque

def search(h, w, pre_h, pre_w):
    can = []
    if h > 0:
        can.append((h-1, w))
    if h < H-1:
        can.append((h+1, w))
    if w > 0:
        can.append((h, w-1))
    if w < W-1:
        can.append((h, w+1))
    res = []
    for h, w in can:
        if S[h][w]=='.' and (h, w) != (pre_h, pre_w):
            res.append((h, w))
    return res

def bfs(h, w):
    d = [[float('inf') for _ in range(W)] for _ in range(H)]
    d[h][w] = 0
    pre_h, pre_w = h, w
    adj_list = search(h, w, pre_h, pre_w)
    open_list = deque([])
    closed_list = []
    closed_list = set(closed_list)
    for adj in adj_list:
        open_list.append((adj[0], adj[1], pre_h, pre_w))
    cnt = 0
    while True:
        cnt+=1
        if H==20 and W==20:
            if cnt > 10000:
                break
        if len(open_list) == 0:
            break
        h, w, pre_h, pre_w = open_list.popleft()
        closed_list.add((h, w, pre_h, pre_w))
        d[h][w] = min(d[h][w], d[pre_h][pre_w] + 1)
        adj_list = search(h, w, pre_h, pre_w)
        for adj in adj_list:
            if (adj[0], adj[1], h, w) in closed_list:
                continue
            open_list.append((adj[0], adj[1], h, w))

    res = 0
    for h in range(H):
        for w in range(W):
            if not d[h][w] == float('inf'):
                res = max(res, d[h][w])
    return res

def bounday():
    for h in range(H):
        for w in range(W):
            if S[h][w] == '
                return False
    return True

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

if __name__ == "__main__":

    if bounday():
        print(H+W-2)
        exit(0)

    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '
                continue
            maxd = bfs(h, w)
            ans = max(maxd, ans)
    print(ans)

Solution (Python):


h,w = list(map(int,input().split()))
maze = [list(input()) for i in range(h)]
for i in maze:
    i.insert(0,"
    i.append("
maze.insert(0,["
maze.append(["


import copy
def clear_maze(maze,target=0):
    con = False
    for r,v1 in enumerate(maze):
        for c,v2 in enumerate(v1):
            if v2==target:
                con = True
                if maze[r-1][c]==".":
                    maze[r-1][c]=target+1
                if maze[r+1][c]==".":
                    maze[r+1][c]=target+1
                if maze[r][c-1]==".":
                    maze[r][c-1]=target+1
                if maze[r][c+1]==".":
                    maze[r][c+1]=target+1
    if con:
        return clear_maze(maze,target+1)
    else:
        return target - 1
ret = 0
for i in range(h+1):
    for j in range(w+1):
        if maze[i][j]==".":
            m = copy.deepcopy(maze)
            m[i][j]=0
            ret = max(ret,clear_maze(m))

print(ret)

Solution (Python):
from collections import deque

H, W = [int(a) for a in input().split()]

S = [None for _ in range(H)]


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




INF = -1

dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)



def bfs(sx, sy):
    dist = [[INF for _ in range(W)] for _ in range(H)]
    que = deque() 
    que.append((sx, sy))
    dist[sy][sx] = 0

    
    
    while(len(que) > 0):
        
        x, y = que.popleft()
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]

            
            if (0 <= nx < W) and (0 <= ny < H) and S[ny][nx] == '.' and dist[ny][nx] == INF:
                que.append((nx, ny))
                dist[ny][nx] = dist[y][x] + 1
    return( max( [max(dist[i]) for i in range(H)]))

m = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            m = max(m, bfs(j, i))

print(m)

Solution (Python):
from collections import deque
import copy
h,w = map(int,input().split())
maze = [["
for i in range(h):
    lu = list(input())
    l = ["
    maze.append(l)
maze.append(["


def breadth_first_search(start,W,Wn):
    work_q = deque([])
    visited = set()
    work_q.append(start)
    visited.add(start)
    Wn[start[0]][start[1]] = 0
    while work_q:
        here = work_q.popleft()
        move = [(here[0]+1,here[1]), (here[0],here[1]+1),
                (here[0]-1,here[1]),(here[0],here[1]-1)]
        for i in move:
            if W[i[0]][i[1]] == "." and i not in visited:
                work_q.append(i)
                visited.add(i)
                Wn[i[0]][i[1]] = Wn[here[0]][here[1]] + 1

    return Wn


ans = 0
for i in range(h+2):
    for j in range(w+2):
        maze_num = copy.deepcopy(maze)
        if maze[i][j] == ".":
            start = (i,j)
            wn =breadth_first_search(start,maze, maze_num)
            wn_max = 0
            for k in range(h+2):
                for l in range(w+2):
                    if wn[k][l] != "
                        wn_max = max(wn_max, wn[k][l])
            ans = max(ans, wn_max)
print(ans)

Solution (Python):
import copy
H,W = list(map(int,input().split()))
F = [] 
for i in range(H):
    a = input()
    b = []
    for j in range(W):
        if a[j] == ".":
            b.append(0)
        else:
            b.append("w")
    F.append(b)
    




s = [0,0]

def n_route(s):
    """
    F:マップ配列
    s:スタート座標
    """
    C = copy.deepcopy(F)
    P = []
    nP = []
    P.append(s)
    C[s[0]][s[1]] = -1
    
    c = 1
    while P:
        
        
        for p in P:
            
            for v in [[1,0],[0,1],[-1,0],[0,-1]]:
                np = [p[0]+v[0],p[1]+v[1]]
                
                
                if 0<=np[0]<H and 0<=np[1]<W and C[np[0]][np[1]] == 0:
                    C[np[0]][np[1]] = c
                    
                    if [np[0],np[1]] not in nP:
                        nP.append([np[0],np[1]])
        
        P = []
        while nP:
            P.append(nP.pop(0))
            
        
        
        
        c += 1
        
    return C
    


Mn = [[0]*W for i in range(H)]



for i in range(H):
    for j in range(W):
        if F[i][j] == 0:
            
            nr = n_route([i,j])
            
            
            for k in range(H):
                for l in range(W):
                    if nr[k][l] != "w" and Mn[k][l] < nr[k][l]:
                        Mn[k][l] = nr[k][l]
                        


m=[]
for i in Mn:
    
    m.append(max(i))
print(max(m))

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def dfs(B,si,sj, H, W):
    R = [-1]*(H*W)
    R[si*W+sj] = 0
    d = deque([si*W+sj])
    while d:
        p = d.popleft()
        x = p//W
        y = p%W
        t = R[x*W+y]

        if x > 0:
            if B[(x-1)*W+y] == 0:
                if R[(x-1)*W+y] == -1:
                    R[(x-1)*W+y] = t+1
                    d.append((x-1)*W+y)

        if x < H-1:
            if B[(x+1)*W+y] == 0:
                if R[(x+1)*W+y] == -1:
                    R[(x+1)*W+y] = t+1
                    d.append((x+1)*W+y)
        if y > 0:
            if B[x*W+y-1] == 0:
                if R[x*W+y-1] == -1:
                    R[x*W+y-1] = t+1
                    d.append(x*W+y-1)
        if y < W-1:
            if B[x*W+y+1] == 0:
                if R[x*W+y+1] == -1:
                    R[x*W+y+1] = t+1
                    d.append(x*W+y+1)

    return max(R)
    

def main():
    H, W = map( int, input().split())
    S = [ list( input()) for _ in range(H)]
    B = [0]*(H*W)
    for i in range(H):
        for j in range(W):
            if S[i][j] == '
                B[i*W+j] = 1
    ans = 0


    for i in range(H):
        for j in range(W):
            if B[i*W+j] == 1:
                continue
            t = dfs(B, i, j, H, W)
            if t > ans:
                ans = t
    print(ans)
            
if __name__ == '__main__':
    main()

Solution (Python):
from array import array

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

cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            cnt += 1

if cnt == w*h:
    print(w+h-2)
else:
    nodes = h*w

    g = []

    for i in range(nodes):
        g.append(array('l', [10000000] * (w * h)))

    for i in range(nodes):
        g[i][i] = 0

    for i in range(h):
        for j in range(w):
            if maze[i][j] == '
                continue
            if maze[i][j] == '.':
                if i > 0 and maze[i-1][j] != '
                    g[i * w + j][(i-1) * w + j] = 1
                    g[(i-1) * w + j][i * w + j] = 1
                if i < h-1 and maze[i+1][j] != '
                    g[i * w + j][(i+1) * w + j] = 1
                    g[(i+1) * w + j][i * w + j] = 1
                if j > 0 and maze[i][j-1] != '
                    g[i * w + j][i * w + j-1] = 1
                    g[i * w + j-1][i * w + j] = 1
                if j < w-1 and maze[i][j+1] != '
                    g[i * w + j][i * w + j+1] = 1
                    g[i * w + j+1][i * w + j] = 1

    def floyed(g, nodes):
        result = 0
        for k in range(nodes):
            for i in range(nodes):
                if i == k:
                    continue
                if g[i][k] == 10000000:
                    continue
                for j in range(nodes):
                    if g[k][j] == 10000000:
                        continue
                    if i == j or i == k or k == j:
                        continue
                    if g[i][j] > g[i][k] + g[k][j]:
                        g[i][j] = g[i][k] + g[k][j]

    floyed(g,nodes)

    result = 0
    for i in range(nodes):
        for j in range(nodes):
            if g[i][j] < 10000000 and g[i][j] > result:
                result = g[i][j]
    print(result)

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

chain_from_iterable = chain.from_iterable
inputs = sys.stdin.readlines()
h, w = map(int, inputs[0].split())
S = [list(map(lambda x: int(x=='.'), x)) for x in inputs[1:]]
S.insert(0, [0]*w)
S.append([0]*w)
for row in S:
    row.insert(0, 0)
    row.append(0)

max_dist = 0
for y in range(1, h+1):
    for x in range(1, w+1):
        if S[y][x] == 0:
            continue
        maze = deepcopy(S)
        maze_d = [[0]*(w+2) for _ in range(h+2)]
        queue = deque([(x, y, 0)])
        d = 0
        while queue:
            x, y, d = queue.popleft()
            d += 1
            maze[y][x] = 0
            if maze[y-1][x]:
                queue.append((x, y-1, d))
                maze[y-1][x] = 0
                maze_d[y-1][x] = d
            if maze[y][x-1]:
                queue.append((x-1, y, d))
                maze[y][x-1] = 0
                maze_d[y][x-1] = d
            if maze[y+1][x]:
                queue.append((x, y+1, d))
                maze[y+1][x] = 0
                maze_d[y+1][x] = d
            if maze[y][x+1]:
                queue.append((x+1, y, d))
                maze[y][x+1] = 0
                maze_d[y][x+1] = d
        max_dist = max(max_dist, max(chain_from_iterable(maze_d)))
print(max_dist)

Solution (Python):
from queue import Queue
import itertools
def solve():

    H, W = map(int, input().split())
    S = []
    for i in range(H):
        tmp = list(input())
        S.append(tmp)
    
    dw = (1,0,-1,0)
    dh = (0,1,0,-1)

    comb = itertools.permutations(tuple(range(20)), 2)
    mx = 0

    for c in comb:
        
        startH = c[0]
        startW = c[1]
        if startH >= H or startW >= W or S[startH][startW] == '
            continue

        q = Queue()
        cur = P(startH, startW)
        q.put(cur)

        time = [[float('inf')] * W for i in range(H)]
        time[startH][startW] = 0

        while not q.empty():
            p = q.get()
            
            for i in range(4):
                nh = p.H + dh[i]
                nw = p.W + dw[i] 
                if 0 <= nh and nh < H and 0 <= nw and nw < W and time[nh][nw] == float('inf') and S[nh][nw] != '
                    q.put(P(nh, nw))
                    time[nh][nw] = time[p.H][p.W] + 1
        
        flatten = list(itertools.chain.from_iterable(time))
        for i in range(len(flatten)):
            if flatten[i] == float('inf'):
                flatten[i] = -1 

        localmx = max(flatten)
        mx = max(localmx, mx)


    print(mx)

class P():
    def __init__(self, H, W):
        self.H = H
        self.W = W

if __name__ == '__main__':
    solve()