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 sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline






















def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	global Y
	global X
	global q
	global maps
	global maze

	H,W = inputMap()
	Y = H
	X = W
	mapmap = []
	ser = []
	for i in range(H):
		tmp = input()
		tmp = tmp[:-1]
		mapmap.append(tmp)

		for j,val in enumerate(tmp):
			if val == ".":
				ser.append((i,j))

	maps = [[-1 for _ in range(X)] for _ in range(Y)]
	maze = mapmap
	q = Queue()

	ans = 0
	for i,val in enumerate(ser):
		s,e = val
		tmp = serchs(s,e,s,e)

		for i in maps:
			tmptmp = max(i)
			
			if tmptmp > ans:
				ans = tmptmp

		maps = [[-1 for _ in range(X)] for _ in range(Y)]

	print(ans)

def serchs(start_y,start_x, goal_y,goal_x):
	q.enqueue((start_y, start_x))
	maps[start_y][start_x] = 0
	run()

	return(maps[goal_y][goal_x])

def run():
	while True:
		tmp = q.dequeue()
		if tmp == None:
			return

		y, x = tmp

		counts = maps[y][x] + 1
		if not y <= 0 and maps[y-1][x] == -1 and maze[y-1][x] == ".":
			q.enqueue((y-1, x))
			maps[y-1][x] = counts
		if not x <= 0 and maps[y][x-1] == -1 and maze[y][x-1] == ".":
			q.enqueue((y, x-1))
			maps[y][x-1] = counts
		if not y >= Y-1 and maps[y+1][x] == -1 and maze[y+1][x] == ".":
			q.enqueue((y+1, x))
			maps[y+1][x] = counts
		if not x >= X-1 and maps[y][x+1] == -1 and maze[y][x+1] == ".":
			q.enqueue((y, x+1))
			maps[y][x+1] = counts

class Queue:
    def __init__(self, queue = None):
        if type(queue) is type([]):
            self.queue = queue
        else:
            self.queue = []

    def enqueue(self, e):
        self.queue.append(e)
        return self.queue

    def dequeue(self):
        try:
            qEl = self.queue[0]
            del self.queue[0]
            return qEl
        except IndexError:
            return None


if __name__ == "__main__":
	main()

Solution (Python):
dxys = [(-1,0), (1,0), (0,-1), (0,1)]

H, W = map(int, input().split())
Sss = ['

N = H*W
adjL = [[] for _ in range(N)]
for x in range(1, H+1):
    for y in range(1, W+1):
        if Sss[x][y] != '.': continue
        for dx, dy in dxys:
            x2, y2 = x+dx, y+dy
            if Sss[x2][y2] != '.': continue
            z = (x-1)*W + y-1
            z2 = (x2-1)*W + y2-1
            adjL[z].append(z2)


def getDiameterOfUnweightedGraph(adjList):
    numV = len(adjList)
    def bfs(vSt):
        costs = [-1] * numV
        costs[vSt] = cost = 0
        vs = [vSt]
        while vs:
            cost += 1
            v2s = []
            for v in vs:
                for v2 in adjList[v]:
                    if costs[v2] == -1:
                        costs[v2] = cost
                        v2s.append(v2)
            vs = v2s
        return cost - 1
    return max([bfs(vSt) for vSt in range(numV)])

maxDist = getDiameterOfUnweightedGraph(adjL)
print(maxDist)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline






















def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	global Y
	global X
	global q
	global maps
	global maze

	H,W = inputMap()
	Y = H
	X = W
	mapmap = []
	ser = []
	for i in range(H):
		tmp = input()
		tmp = tmp[:-1]
		mapmap.append(tmp)

		for j,val in enumerate(tmp):
			if val == ".":
				ser.append((i,j))

	maps = [[-1 for _ in range(X)] for _ in range(Y)]
	maze = mapmap
	q = Queue()

	ans = 0
	for i,val in enumerate(ser):
		s,e = val
		tmp = serchs(s,e,s,e)

		for i in maps:
			tmptmp = max(i)
			
			if tmptmp > ans:
				ans = tmptmp

		maps = [[-1 for _ in range(X)] for _ in range(Y)]

	print(ans)

def serchs(start_y,start_x, goal_y,goal_x):
	q.enqueue((start_y, start_x))
	maps[start_y][start_x] = 0
	run()

	return(maps[goal_y][goal_x])

def run():
	while True:
		tmp = q.dequeue()
		if tmp == None:
			return

		y, x = tmp

		counts = maps[y][x] + 1
		if not y <= 0 and maps[y-1][x] == -1 and maze[y-1][x] == ".":
			q.enqueue((y-1, x))
			maps[y-1][x] = counts
		if not x <= 0 and maps[y][x-1] == -1 and maze[y][x-1] == ".":
			q.enqueue((y, x-1))
			maps[y][x-1] = counts
		if not y >= Y-1 and maps[y+1][x] == -1 and maze[y+1][x] == ".":
			q.enqueue((y+1, x))
			maps[y+1][x] = counts
		if not x >= X-1 and maps[y][x+1] == -1 and maze[y][x+1] == ".":
			q.enqueue((y, x+1))
			maps[y][x+1] = counts

class Queue:
    def __init__(self, queue = None):
        if type(queue) is type([]):
            self.queue = queue
        else:
            self.queue = []

    def enqueue(self, e):
        self.queue.append(e)
        return self.queue

    def dequeue(self):
        try:
            qEl = self.queue[0]
            del self.queue[0]
            return qEl
        except IndexError:
            return None


if __name__ == "__main__":
	main()

Solution (Python):
from collections import deque
import copy

def bfs(graph, sh, sw):
    td = deque([[sh, sw]])
    graph[sh][sw] = "0"
    mx = 0
    while td:
        h, w = td.popleft()
        num = int(graph[h][w])
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h + j, w + k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            elif graph[new_h][new_w] == ".":
                graph[new_h][new_w] = str(num+1)
                if int(graph[new_h][new_w]) > mx:
                    mx = int(graph[new_h][new_w])
                td.append([new_h, new_w])

    return mx

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

ans = []

for i in range(H):
    for j in range(W):
        if ls[i][j] == ".":
            sh = i
            sw = j
            graph = copy.deepcopy(ls)
            ans.append(bfs(graph, sh, sw))

print(max(ans))

Solution (Python):
from collections import deque

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

def solve(x, y):
    offset = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    visited = [[-1] * W for _ in range(H)]
    visited[y][x] = 0
    
    q = deque()
    q.append((x, y))

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

        for u, v in offset:
            if not (0 <= x + u < W) or not (0 <= y + v < H):
                continue

            if visited[y + v][x + u] > -1 or S[y + v][x + u] == "
                continue

            visited[y + v][x + u] = visited[y][x] + 1
            q.append((x + u, y + v))
            
    return visited

ans = 0
for y, ss in enumerate(S):
    for x, s in enumerate(ss):
        if s == ".":
            ans = max(ans, max(max(v) for v in solve(x, y)))

print(ans)

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 queue
r,c=map(int,input().split())


a=[list(input()) for i in range(r)]
sy,sx = (1,1)

def minload(sy,sx,a):
    sy-=1
    sx-=1
    
    
    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 True:
        if queue.Queue.empty(q):
            break
        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]))
    
    max = 0
    for i in a:
        for j in i:
            if j != '
                if j > max:
                    max = j
    return(max)
ans = 0
for sy in range(1,r+1): 
    for sx in range(1,c+1):
        b = []
        for i in a:
            b.append(list(i))
        if a[sy-1][sx-1]==".":
            local_max = minload(sy,sx,b)
            
            
        else:
            local_max = 0
        if local_max > ans:
            ans = local_max
print(ans)

Solution (Python):
import sys
from pprint import pprint

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

def solve(h, w, s):
    
    n_node = 0
    nodes = [] 
    
    for y in range(h):
        nodes.append([])
        for x in range(w):
            nodes[y].append(n_node)
            n_node += 1
    edges = [[float("inf") for i in range(n_node)] for j in range(n_node)]
    
    for y in range(h):
        for x in range(w):
            if s[y][x] != ".":
                continue
            for dx, dy in ((1,0), (-1,0), (0,1), (0,-1)):
                if 0 <= y+dy < h and 0 <= x+dx < w and s[y+dy][x+dx] == ".":
                    edges[nodes[y][x]][nodes[y+dy][x+dx]] = 1
    for i in range(n_node):
        edges[i][i] = 0
    
    dist = warshall_floyd(edges, n_node)
    
    ans = -1
    for y in range(n_node):
        for x in range(n_node):
            if dist[y][x] < float("inf"):
                ans = max(ans, dist[y][x])
    print(ans)


if __name__ == '__main__':
    h, w = map(int, sys.stdin.readline().strip().split(" "))
    s = []
    for i in range(h):
        s.append(list(sys.stdin.readline().strip()))
    
    
    solve(h, w, s)

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

S = [[True]*(W+2)]
S += [[True] + [x == '
S.append([True]*(W+2))

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

edge = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j]:
            continue
        for d in range(4):
            x = dx[d]
            y = dy[d]
            if (not S[i+y][j+x]) and (not ((i+y-1)*W+(j+x),(i-1)*W+j) in edge):
                edge.append(((i-1)*W+j,(i+y-1)*W+(j+x)))

S = [[float("inf")] * (H*W) for _ in range(H*W)]
for i in range(H*W):
    S[i][i] = 0
for a,b in edge:
    S[a-1][b-1] = 1
    S[b-1][a-1] = 1

from scipy.sparse.csgraph import floyd_warshall
S = floyd_warshall(S)

answer = 0
for i in range(H*W):
    for j in range(i):
        if S[i][j] < float("inf"):
            answer = max(answer, S[i][j])

print(int(answer))

Solution (Python):
def warshall_floyd(d, n):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


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

fld = [""] * H
for i in range(H):
    fld[i] = input()

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

d = [[float("inf") for i in range(H * W)] for i in range(H * W)]
for i in range(H):
    for j in range(W):
        if fld[i][j] == '
            continue
        for k in range(4):
            x = i + dx[k]
            y = j + dy[k]
            if x < 0 or x >= H or y < 0 or y >= W:
                continue
            if fld[x][y] == ".":
                d[i*W+j][x*W+y] = 1


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

warshall = warshall_floyd(d, H*W)
ans = 0
for val in warshall:
    for v in val:
        if v != float("inf"):
            ans = max(ans, v)

print(ans)

Solution (Python):
from collections import deque

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

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

def bfs(sx,sy):
    if l[sy][sx]=="
      return 0
    
    d=[[float("inf")]*w for i in range(h)]
    
    que=deque([])
    que.append((sx,sy))
    d[sy][sx]=0

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

          if 0<=nx<w and 0<=ny<h and l[ny][nx] != "
              que.append((nx,ny))
              d[ny][nx] = d[p[1]][p[0]] + 1
              gx=nx
              gy=ny
 
    return d[gy][gx]

for i in range(h):
  for k in range(w):
    ma = max(ma,bfs(k,i))
    
print(ma)

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

def cl(sx, sy, m):
    Z = -1
    dist = [[Z for i in range(w)] for j in range(h)]
    for i in range(h):
        for j in range(w):
            if m[i][j] == '
                dist[i][j] = -1

    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dist[sy][sx] = 0
        while len(q):
            x, y = q.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0 <= nx < w and 0 <= ny < h and m[ny][nx] != '
                    q.insert(0, (nx, ny))
                    dist[ny][nx] = dist[y][x] + 1
        return dist
    return bfs()

S = [list(input()) for _ in range(h)]
ans = 0
for y in range(h):
    for x in range(w):
        e = S[y][x]
        if e != '
            num = cl(x, y, S)
            for k in range(h):
                ans = max(ans, max(num[k]))
print(ans)

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


def dfs(start_h,start_w):
    q=deque()
    maze_copy=copy.deepcopy(maze)
    walk_count=[[0 for _ in range(w)] for _ in range(h)]
    q.append([start_h,start_w])
    maze_copy[start_h][start_w]="
    max_count=0
    while(len(q)!=0):
        position=q.popleft()
        now_h=position[0]
        now_w=position[1]
        now_count=walk_count[now_h][now_w]
        if(now_h>0 and maze_copy[now_h-1][now_w]=='.'):
            walk_count[now_h-1][now_w]=now_count+1
            maze_copy[now_h-1][now_w]="
            q.append([now_h-1,now_w])
            if(max_count<now_count+1):
                max_count=now_count+1

        if(now_h<h-1 and maze_copy[now_h+1][now_w]=='.'):
            walk_count[now_h+1][now_w]=now_count+1
            maze_copy[now_h+1][now_w]="
            q.append([now_h+1,now_w])
            if(max_count<now_count+1):
                max_count=now_count+1

        if(now_w>0 and maze_copy[now_h][now_w-1]=='.'):
            walk_count[now_h][now_w-1]=now_count+1
            maze_copy[now_h][now_w-1]="
            q.append([now_h,now_w-1])
            if(max_count<now_count+1):
                max_count=now_count+1

        if(now_w<w-1 and maze_copy[now_h][now_w+1]=='.'):
            walk_count[now_h][now_w+1]=now_count+1
            maze_copy[now_h][now_w+1]="
            q.append([now_h,now_w+1])
            if(max_count<now_count+1):
                max_count=now_count+1
    return max_count

ans=0
for i in range(h):
    for j in range(w):
        if(maze[i][j]=='.'):
            ij_count=dfs(i,j)
            if(ans<ij_count):
                ans=ij_count
print(ans)

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

input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
m = [['
hs = []
ws = []
for hi in range(1, h+1):
    for wi, s in enumerate(input().strip(), start=1):
        m[hi][wi] = s
        if s == '.':
            hs.append(hi)
            ws.append(wi)

def bfs(hs, ws, m):
    cost = 0
    q = deque([])
    m[hs][ws] = '
    for offset in [(0, 1), (-1, 0), (0, -1), (1, 0)]:
        if m[hs+offset[0]][ws+offset[1]] == '.':
            q.append((hs+offset[0], ws+offset[1]))
    while q:
        cost += 1
        q_ = deque(q)
        q = deque([])
        for h, w in q_:
            m[h][w] = '
            for offset in [(0, 1), (-1, 0), (0, -1), (1, 0)]:
                if m[h+offset[0]][w+offset[1]] == '.':
                    m[h+offset[0]][w+offset[1]] = '
                    q.append((h+offset[0], w+offset[1]))

    return cost, h, w

maxi = -1
for hss, wss in zip(hs, ws):
    maxi_, hh, ww = bfs(hss, wss, deepcopy(m[:]))
    maxi = max(maxi, maxi_)

print(maxi)

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+1][j] == 1:
            
                
            
            G[W*i+j].append(W*(i+1)+j)

        if i>=1:
            if A[i-1][j] == 1:
                
                    
                
                G[W*i+j].append(W*(i-1)+j)            
            
        
        if A[i][j+1] == 1:
            
                
            
            G[W*i+j].append(W*i+(j+1))
        
        if j>=1:
            if A[i][j-1] == 1:
                
                    
                
                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))

print(ans)

Solution (Python):
h,w = map(int,input().split())
s = [list(input()) for i in range(h)]
p = [(0,1),(1,0),(-1,0),(0,-1)]
mx = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != '
            start = (i,j)
            n1 ={start}
            corse = {}
            corse[start]=1
            cnt = 1
            while n1 != set():
                n2 = set()
                for k in n1:
                    for l in p:
                        nk = (k[0]+l[0],k[1]+l[1])
                        if 0<=nk[0]<h and 0<=nk[1]<w:
                         if s[nk[0]][nk[1]] != '
                            corse[nk] = 1
                            mx = max(cnt,mx)
                            n2.add(nk)
                cnt += 1
                n1 = n2
print(mx)

Solution (Python):

from collections import deque
h, w = list(map(int,input().split()))

def bfs(que,c):
    while que:
        c += 1
        qq = que
        que = deque([])
        while qq:
            x, y = qq.popleft()
            field[x][y] = "
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
        
                if 0 <= nx <= h-1 and 0 <= ny <= w-1 and field[nx][ny] == ".":
                    if (nx,ny) not in que:
                        que.append((nx,ny))
            
    return c-1
            
A = [list(input()) for _ in range(h)]



dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque([]) 
ans = []

for p in range(h):
    for q in range(w):
        if A[p][q] == ".":
            field = [k[:] for k in A]
            
            que.append((p,q))
            ans.append(bfs(que,0))
print(max(ans))

Solution (Python):
def main():

    from collections import deque
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    cost = [[600] * w for _ in range(h)]
    nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    ans = 0

    def bfs(sx, sy):
        q = deque([(sx, sy)])
        cost[sx][sy] = 0
        value = 0
        while q:
            x, y = q.popleft()
            for dx, dy in nb:
                nx = x + dx
                ny = y + dy
                if 0 <= nx and nx < h and 0 <= ny and ny < w and s[nx][ny] == "." and cost[nx][ny] == 600:
                    q.append((nx, ny))
                    cost[nx][ny] = cost[x][y] + 1
                    value = max(value, cost[nx][ny])
        return value

    ans = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                cost = [[600] * w for _ in range(h)]
                tmp = bfs(i, j)
                ans = max(tmp, ans)

    print(ans)


if __name__ == "__main__":
    main()

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

def cl(sx, sy, m):
    Z = -1
    x_len = len(m[0])
    y_len = len(m)
    dist = [[Z for i in range(x_len)]
                for j in range(y_len)]
    for i in range(y_len):
        for j in range(x_len):
            if m[i][j] == '
                dist[i][j] = -1

    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dist[sy][sx] = 0
        while len(q):
            x, y = q.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0 <= nx < x_len and 0 <= ny < y_len and m[ny][nx] != '
                    q.insert(0, (nx, ny))
                    dist[ny][nx] = dist[y][x] + 1
        
        return dist
    return bfs()

S = [list(input()) for _ in range(h)]
ans = 0
for y in range(h):
    for x in range(w):
        start = S[y][x]
        if start != '
            num = cl(x, y, S)
            for k in range(h):
                ans = max(ans, max(num[k]))
print(ans)

Solution (Python):
h,w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
max_step = 0

for h_i in range(h):
  for w_i in range(w):
    grid = [[-1]*w for _ in range(h)]
    
    if maze[h_i][w_i] == '.':
      grid[h_i][w_i] = 0
      loc = [[h_i,w_i]]
      
      for k in range(1, h*w):
        next_loc = []
        for y,x in loc:
          for i,j in ([1,0], [-1,0], [0,1], [0,-1]):
            next_h = y+i
            next_w = x+j
            
            if 0 <= next_h < h and 0 <= next_w < w and maze[next_h][next_w] == '.' and grid[next_h][next_w]==-1: 
              grid[next_h][next_w] = k
              next_loc.append([next_h, next_w])
        loc=next_loc
      
      temp_max_step = max(max(grid_w) for grid_w in grid)
      max_step = max(max_step, temp_max_step)
      
print(max_step)

Solution (Python):
from collections import deque
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    H, W = map(int, input().split())
    S = stdin.read().splitlines()

    maze = ['
    for s in S:
        maze.append('
    maze.append('

    def func(sx, sy):
        c1 = deque([(sx, sy)])
        c2 = [[None for _ in range(W + 1)] for _ in range(H + 1)]
        c2[sx][sy] = 0
        ret = 0
        while c1:
            x, y = c1.popleft()
            for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                if '.' in maze[x+i][y+j] and c2[x+i][y+j] is None:
                    c1.append((x+i, y+j))
                    c2[x+i][y+j] = c2[x][y] + 1
                    ret = max(ret, c2[x+i][y+j])
        return ret

    ans = 0
    for i, a in enumerate(maze[1:-1], start=1):
        for j, b in enumerate(a[1:-1], start=1):
            if b == '.':
                ans = max(ans, func(i, j))
    print(ans)


main()

Solution (Python):
from collections import deque


def solve(h, w, s_list):

    g = dict()
    for i in range(h):
        for j in range(w):
            if s_list[i][j] == ".":
                g[i * 100 + j] = dict()

    for i in range(h):
        for j in range(w - 1):
            if s_list[i][j] == "." and s_list[i][j + 1] == ".":
                g[i * 100 + j][i * 100 + j + 1] = 1
                g[i * 100 + j + 1][i * 100 + j] = 1

    for i in range(h - 1):
        for j in range(w):
            if s_list[i][j] == "." and s_list[i + 1][j] == ".":
                g[i * 100 + j][i * 100 + j + 100] = 1
                g[i * 100 + j + 100][i * 100 + j] = 1

    d_max = 0
    for x in g.keys():
        d_dict = {v: 10000 for v in g.keys()}
        queue = deque([x])
        d_dict[x] = 0
        while len(queue) > 0:
            p = queue.popleft()
            for q in g[p].keys():
                if d_dict[q] > d_dict[p] + 1:
                    d_dict[q] = d_dict[p] + 1
                    queue.append(q)
        d_max = max(d_max, max(d_dict.values()))

    return d_max


def main():
    h, w = map(int, input().split())
    s_list = []
    for _ in range(h):
        s = input()
        s_list.append(s)
    res = solve(h, w, s_list)
    print(res)


def test():
    assert solve(3, 3, ["...", "...", "..."]) == 4
    assert solve(3, 5, ["...


if __name__ == "__main__":
    test()
    main()

Solution (Python):
from collections import deque
H, W = map(int, input().split())
s = ["
DH, DW = [0, 0, 1, -1], [1, -1, 0, 0]

def bfs(start):
	que = deque([start])
	dist = [[-1 for _ in range(W+2)] for _ in range(H+2)]
	dist[start[0]][start[1]] = 0
	num = 0

	while que:

		label = que.pop()
		h, w = label[0], label[1]
		
		for dh, dw in zip(DH, DW):
			hh, ww = h+dh, w+dw
			if s[hh][ww] == "." and dist[hh][ww] < 0:
				que.appendleft((hh, ww))
				dist[hh][ww] = dist[h][w] + 1
				num = max(num, dist[hh][ww])

	return num

ans = 0
for h in range(1, H+1):
	for w in range(1, W+1):
		if s[h][w] == ".":
			ans = max(ans, bfs((h, w)))
print(ans)

Solution (Python):
import sys
import itertools

sys.setrecursionlimit(10**7)

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

S = list('
for _ in range(H):
    S.extend('
    S.extend(list(input()))
    S.extend('
S.extend(list('

dxs = [-1, 1, -(W + 2), W + 2]
sx, sy = 0, 0


def f(s):
    dist = [-1] * len(S)
    
    
    if S[s] == '
        return -1
    q = [s]
    dist[s] = 0
    while q:
        qq = []
        for x, dx in itertools.product(q, dxs):
            y = x + dx
            if S[y] == '
                continue
            if dist[y] != -1:
                continue
            dist[y] = dist[x] + 1
            qq.append(y)
        q = qq
    return max(dist)


ans = 0
for i in range(len(S)):
    v = f(i)
    if ans < v:
        ans = v
print(ans)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import shortest_path

H, W = map(int, input().split())
m = []
for i in range(H):
  s = input()
  z = []
  for x in s:
    if x == '.':
      z.append(0)
    if x == '
      z.append(1)
  m.append(z)
m = np.array(m)

graph = np.array([[0] * (H * W) for _ in range(H * W)])
for i in range(H):
  for j in range(W):
    if m[i][j] == 0:
      if i-1 >= 0:
        if m[i-1][j] == 0:
          graph[W * i + j][W * (i-1) + j] = 1
      if i+1 <= H-1:
        if m[i+1][j] == 0:
          graph[W * i + j][W * (i+1) + j] = 1
      if j-1 >= 0:
        if m[i][j-1] == 0:
          graph[W * i + j][W * i + (j-1)] = 1
      if j+1 <= W-1:
        if m[i][j+1] == 0:
          graph[W * i + j][W * i + (j+1)] = 1

a = shortest_path(graph)
print(int(np.nanmax(a[a != np.inf])))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from copy import deepcopy
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = float('INF')
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


h, w = LI()
maze = SRL(h)


def solve(sy, sx):
    min_cost = deepcopy(maze)
    min_cost[sy][sx] = 0
    que = deque([(sy, sx)])
    max_c = 0
    while que:
        cy, cx = que.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ny = cy + i
            nx = cx + j
            if 0 <= ny < h and 0 <= nx < w:
                if min_cost[ny][nx] == '.':
                    min_cost[ny][nx] = min_cost[cy][cx] + 1
                    que += [(ny, nx)]
                    max_c = max(max_c, min_cost[ny][nx])
    return max_c



ans = 0
for y in range(h):
    for x in range(w):
        if maze[y][x] == '
            continue
        else:
            max_c = solve(y, x)
            ans = max(max_c, ans)


print(ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
C = [['

for i in range(H):
    s = input()
    for j in range(W):
        C[i + 1][j + 1] = s[j]
ans = 0

for sy in range(1, H + 1):
    for sx in range(1, W + 1):

        q = deque()
        q.append((sy, sx, 0))
        S = set([])
        while len(q) > 0:
            t = q.popleft()
            y, x, d = t[0], t[1], t[2]
            ans = max(d, ans)
            if C[y][x] == '
                continue
            if (y, x) in S:
                continue
            else:
                S.add((y, x))

            q.append((y + 1, x , d + 1))
            q.append((y - 1, x, d + 1))
            q.append((y, x + 1, d + 1))
            q.append((y, x - 1, d + 1))




print(ans - 1)