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 Queue
import copy

def main():
    H, W = map(int, raw_input().split())
    S = []

    for i in range(H):
        S.append(list(raw_input()))


    def bfs(start, S2):
        q = Queue.Queue()
        q.put(start)
        candidates = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        dist = [[0]*W for _ in range(H)]
        S2[start[0]][start[1]] = "
        while not q.empty():
            i = q.get()
            x = i[0]
            y = i[1]

            for candi in candidates:
                x_new = x + candi[0]
                y_new = y + candi[1]

                if x_new < H and x_new >= 0:
                    if y_new < W and y_new >=0:
                        if S2[x_new][y_new] == ".":
                            dist[x_new][y_new] = dist[x][y] + 1
                            S2[x_new][y_new] = "
                            q.put([x_new, y_new])

        ans = 0
        for i in range(H):
            ans = max(ans, max(dist[i]))

        return ans

    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                S2 = copy.deepcopy(S)
                ans_temp = bfs([i, j], S2)

                ans = max(ans, ans_temp)


    print ans


if __name__ == "__main__":
    main()

Solution (Python):


from collections import deque

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]
    res = 0
    for i in range(h):
        for j in range(w):
            di = maxdistfrom(s, i, j, h, w)
            res = max(res, di)
    print(res)

def maxdistfrom(s, i, j, h, w):
    if s[i][j] == "
        return 0
    queued = [[False for l in range(w)] for k in range(h)]
    queue = deque()
    queue.append((i, j, 0)); queued[i][j] = True
    res = 0
    while queue:
        k, l, d = queue.popleft()
        res = max(res, d)
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            k2 = k + dy
            l2 = l + dx
            if not ((0 <= k2 < h) and (0 <= l2 < w)):
                continue
            if s[k2][l2] == "
                continue
            if queued[k2][l2]:
                continue
            queue.append((k2, l2, d + 1)); queued[k2][l2] = True
    return res

if __name__ == "__main__":
    main()

Solution (Python):
INF = float("inf")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

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

N = W * H
E = [[INF] * N  for _ in range(N)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            for di, dj in dij:
                ni, nj = i + di, j + dj
                if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
                    E[W * i + j][W * ni + nj] = 1

from scipy.sparse.csgraph import floyd_warshall
A = floyd_warshall(E)
ans = int(max(max(a if a != INF else 0 for a in a) for a in A))

print(ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
meiro = []
INF = 10**9
meiro.append(["
for _ in range(H):
    temp = list(input())
    temp.append("
    temp.insert(0,"
    meiro.append(temp)
meiro.append(["

def bfs(i,j):
    INF = 10 ** 9
    dist = [[INF for i in range(W+2)] for j in range(H+2)]
    dist[i][j] = 0
    q = deque([[i,j]])
    while q:
        v = q.popleft()
        dv = dist[v[0]][v[1]]
        
        if meiro[v[0]-1][v[1]] != "
            if dist[v[0]][v[1]]+1 < dist[v[0]-1][v[1]]:
                dist[v[0]-1][v[1]] = dist[v[0]][v[1]]+1
                q.append([v[0]-1,v[1]])
                
        if meiro[v[0]+1][v[1]] != "
            if dist[v[0]][v[1]]+1 < dist[v[0]+1][v[1]]:
                dist[v[0]+1][v[1]] = dist[v[0]][v[1]]+1
                q.append([v[0]+1,v[1]])
        
        if meiro[v[0]][v[1]-1] != "
            if dist[v[0]][v[1]]+1 < dist[v[0]][v[1]-1]:
                dist[v[0]][v[1]-1] = dist[v[0]][v[1]]+1
                q.append([v[0],v[1]-1])
        
        if meiro[v[0]][v[1]+1] != "
            if dist[v[0]][v[1]]+1 < dist[v[0]][v[1]+1]:
                dist[v[0]][v[1]+1] = dist[v[0]][v[1]]+1
                q.append([v[0],v[1]+1])
    
    dist = [[0 if x == INF else x for x in inner] for inner in dist]
    
    max_dist = 0
    for i in dist:
        max_dist = max(max_dist,max(i))
    return max_dist

ans = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if meiro[i][j] == ".":
            ans = max(ans,bfs(i,j))
print(ans)

Solution (Python):
H,W=map(int,input().split())
S=[]
for _ in range(H):
    s=input()
    ss=[a for a in s]
    S.append(ss)
answers=[]
start=[]
for h,c_h in enumerate(S):
    for w,c_w in enumerate(c_h):
        if c_w=='.':
            start.append([h,w])
for a in start:
    S[a[0]][a[1]]='s'
    stack=[]
    stack.append(a)
    visited_area=[[0 for _ in range(W)] for _ in range(H)]
    def bfs(S,visited_area,stack):
        while len(stack)>0:
            h,w=stack.pop()
            for x,y in ([1,0],[-1,0],[0,1],[0,-1]):
                new_h=h+x
                new_w=w+y
                if new_h<0 or new_h>=H or new_w<0 or new_w>=W:
                    continue
                if S[new_h][new_w]=='.' and visited_area[new_h][new_w]==0:
                    visited_area[new_h][new_w]=visited_area[h][w]+1
                    stack.insert(0,[new_h,new_w])
        kotae=[]
        for z in range(H):
            saidai=max(visited_area[z])
            kotae.append(saidai)
        large=max(kotae)
        answers.append(large)
        S[a[0]][a[1]] = '.'
    bfs(S, visited_area, stack)
print(int(max(answers)))

Solution (Python):
from collections import deque
def bfs(yy,xx):
  global ans
  d=[[float('inf')]*w for i in range(h)]
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  q=deque([])
  q.append((yy,xx))
  d[yy][xx]=0
  while q:
    y,x=q.popleft()
    for i in range(4):
      ny,nx=y+dy[i],x+dx[i]
      if 0<=ny<h and 0<=nx<w and s[ny][nx]=='.' and d[ny][nx]==float('inf'):
        d[ny][nx]=d[y][x]+1
        q.append((ny,nx))
        if ans<d[ny][nx]:
          ans=d[ny][nx]
  return ans
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
a=0
ans=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      a=max(a,bfs(i,j))
print(a)

Solution (Python):
import queue
INF = float("inf")

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

def A(i, j):
    saicho = 0
    q = queue.Queue()
    q.put([i,j])
    d = [[INF] * w for _ in range(h)]
    d[i][j] = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    while not q.empty():
        r = q.get()
        for k in range(4):
            x = r[0] + dx[k]
            y = r[1] + dy[k]
            if x>=0 and x<h and y>=0 and y<w and s[x][y]=="." and d[x][y]==INF:
                saicho = d[r[0]][r[1]] + 1
                d[x][y] = saicho
                q.put([x, y])
    return saicho

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans = max(ans, A(i,j))

print(ans)

Solution (Python):
import queue
def bfs(sx,sy):
  
  dist = [[-1 for _ in range(w)] for __ in range(h)]
  dist[sx][sy] = 0
  q = queue.Queue()
  q.put([sx,sy])
  res = 0
  
  while not q.empty():
    vx,vy = q.get()
    
    for dx,dy in [(0,1),(1,0),(-1,0),(0,-1)]:
      x = vx+dx
      y = vy+dy
      if 0<=x<h and 0<=y<w and S[x][y] == "." and dist[x][y]==-1:
        q.put([x,y])
        dist[x][y] = dist[vx][vy]+1
        res = max(res, dist[x][y])
  return res


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

for i in range(h):
  for j in range(w):
    if S[i][j] == '.':
      ans = max(ans, bfs(i,j))
print(ans)

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

def bfs(y,x,m):
  g = [[None if S[i][j] == '.' else -1 for j in range(W)] for i in range(H)]
  g[y][x] = 0
  q = deque()
  q.append((y,x))
  while q:
    i,j = q.popleft()
    for di,dj in ((0,1),(1,0),(-1,0),(0,-1)):
      ni = i+di; nj = j+dj
      if 0 <= ni < H and 0 <= nj < W and g[ni][nj] is None:
        g[ni][nj] = g[i][j] + 1
        q.append((ni,nj))
  return max(max(r) for r in g)

for i in range(H):
  for j in range(W):
    if S[i][j] == '.':
      deq = bfs(i,j,S)
      if ans < deq:
        ans = deq
print(ans)

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

dx = [1,0,-1,0]
dy = [0,1,0,-1]
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == "
			continue
		visited = [[0 for ii in range(w)] for jj in range(h) ]
		st = [[i,j]]
		visited[i][j] = 1
		while st:
			x,y = st.pop(0)
			for k in range(4):
				p = x + dx[k]
				q = y + dy[k]
				if p < 0 or q < 0 or p >= h or q >= w or s[p][q] == "
					continue
				st.append([p,q])
				visited[p][q] = visited[x][y] + 1
		
		for a in range(h):
			for b in range(w):
				ans = max(ans,visited[a][b])
print (ans-1)

Solution (Python):
import queue

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
INF = H*W+1

def movable(S,S_dist,px,py):
    if  0 <= px and px < H and 0 <= py and py < W:
        if S_dist[px][py] == INF and S[px][py] == ".":
            return True
    return False

def bfs(S,sx,sy):
    S_dist = [[INF for _ in range(W)] for _ in range(H)]
    
    
    S_dist[sx][sy] = 0
    q = queue.Queue()
    q.put((sx,sy))
    vec = [(0,1),(0,-1),(1,0),(-1,0)]
    ret = 0
    while not q.empty():
        p = q.get()
        ret = S_dist[p[0]][p[1]]
        for vx,vy in vec:
            if movable(S,S_dist,p[0]+vx,p[1]+vy):
                S_dist[p[0]+vx][p[1]+vy] = S_dist[p[0]][p[1]]+1
                q.put((p[0]+vx,p[1]+vy))
    return ret

ans = 0
for i in range(H*W):
    if S[i//W][i%W] == ".":
        ans = max(ans,bfs(S,i//W,i%W))
print(ans)

Solution (Python):
import queue
import copy

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
INF = H*W+1

def movable(S,S_dist,px,py):
    if  0 <= px and px < H and 0 <= py and py < W:
        if S_dist[px][py] == INF and S[px][py] == ".":
            return True
    return False

def bfs(S,sx,sy):
    S_dist = [[INF for _ in range(W)] for _ in range(H)]
    
    
    S_dist[sx][sy] = 0
    q = queue.Queue()
    q.put((sx,sy))
    vec = [(0,1),(0,-1),(1,0),(-1,0)]
    ret = 0
    while not q.empty():
        p = q.get()
        ret = S_dist[p[0]][p[1]]
        for vx,vy in vec:
            if movable(S,S_dist,p[0]+vx,p[1]+vy):
                S_dist[p[0]+vx][p[1]+vy] = S_dist[p[0]][p[1]]+1
                q.put((p[0]+vx,p[1]+vy))
    return ret

ans = 0
for i in range(H*W):
    if S[i//W][i%W] == ".":
        ans = max(ans,bfs(S,i//W,i%W))
print(ans)

Solution (Python):
from collections import deque

def bfs(grid, sy, sx, wall):
    queue = deque([])
    queue.append([sy, sx, 0])
    visited = {}
    visited[(sy,sx)] = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        y,x,cnt = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall or (y_,x_) in visited:
                continue
            queue.append([y_,x_,cnt+1])
            visited[(y_,x_)] = cnt+1
    return max(visited.values())

h,w = map(int, input().split())
wall = '
edges = [wall] * (w+2)
grid = [edges]
for i in range(h):
    s = input()
    grid.append([wall] + list(s) + [wall])
grid.append(edges)

starts = []
dxy = [(1,0), (-1,0), (0,1), (0,-1)]
for y in range(1,h+1):
    for x in range(1,w+1):
        if grid[y][x] == wall:
            continue
        cnt = 0
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                cnt += 1
        if cnt > 1:
            starts.append((y,x))

ans = 0
for y,x in starts:
    tmp = bfs(grid, y, x, wall)
    if ans < tmp:
        ans = tmp
print(ans)

Solution (Python):
from collections import deque
D = [(1,0),(0,1),(-1,0),(0,-1)]

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

def bfs(i,j):
  if maze[i][j] == '
    return 0
  queue = deque([(i,j,1)])
  distance = [[float('inf') for _ in range(W)] for _ in range(H)]
  distance[i][j] = 0
  
  while queue:
    x,y,d = queue.popleft()
    for dx,dy in D:
      nx,ny = x+dx,y+dy
      if not(0<= nx < H and 0 <= ny < W):
        continue
      if maze[nx][ny] == '
        continue
      if distance[nx][ny] != float('inf'):
        continue
      distance[nx][ny] = d
      queue.append((nx,ny,d+1))
  res = 0

  for i in range(H):
    for j in range(W):
      if distance[i][j] ==float('inf'):
        continue
      res = max(res,distance[i][j])
  return res

ans = 0
for i in range(H):
  for j in range(W):
    ans = max(ans,bfs(i,j))
print(ans)

Solution (Python):
h,w = map(int, input().split())
s = []
for i in range(h):
	a = input()
	s.append(a)
ans = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(h):
	for j in range(w):
		visited = [[0 for p in range(w)] for q in range(h)]
		c = 0
		if s[i][j] == "
			continue
		else:
			v = [[i,j]]
			visited[i][j] = 1
			while v:
				x, y = v.pop(0)
				for k in range(4):
					d = x + dx[k]
					e = y + dy[k]
					if d < 0 or e < 0 or d >= h or e >= w or visited[d][e] != 0 or s[d][e] == "
						continue
					visited[d][e] = visited[x][y] + 1
					v.append([d,e])
			for ii in range(h):
				for jj in range(w):
					ans = max(ans,visited[ii][jj])
print (ans-1)

Solution (Python):






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

graph = {i: {} for i in range(1, h * w + 1)}

data = []
data.append([False for i in range(w + 2)])
for i in range(h):
    s = list(input())
    sub = [False]
    for i in range(w):
        if s[i] is "
            sub.append(False)
        else:
            sub.append(True)
    sub.append(False)
    data.append(sub)
data.append([False for i in range(2 + w)])

for i in range(1, h + 1):
    for j in range(1, w + 1):
        
        if data[i][j]:
            now = w * (i - 1) + j
            if data[i - 1][j]:
                node = w * (i - 1) + j
                graph[now][node]=1
                graph[node][now]=1
            if data[i][j + 1]:
                node = w* (i - 1) + j + 1
                graph[now][node]=1
                graph[node][now]=1
            if data[i][j - 1]:
                node = w * (i - 1) + j - 1
                graph[node][now]=1
                graph[now][node]=1
            if data[i + 1][j]:
                node = w * i + j
                graph[node][now]=1
                graph[now][node]=1



import heapq
def dijkstra(s,graph,n):
    
    dist=[10**20 for i in range(n+1)]
    dist[s]=0
    pq=[]
    heapq.heapify(pq)
    
    heapq.heappush(pq,(0,s))
    while pq:
        x=heapq.heappop(pq)
        node,mini_dis=x[1],x[0]
        for point in graph[node].keys():
            w=graph[node][point]
            
            newlen=dist[node]+w
            if newlen<dist[point]:
                heapq.heappush(pq,(newlen,point))
                dist[point]=newlen
    mea=0
    for i in range(1,n+1):
        if 0<dist[i]<10**20:
            mea=max(dist[i],mea)
    return mea


ans=0
for i in range(1,h*w+1):
    if graph[i]:
        ans=max(ans,dijkstra(i,graph,h*w))
print(ans)

Solution (Python):
H,W = list(map(int,input().split()))
MAP = [[i for i in input()] for j in range(H)]
count = sum([l.count(".") for l in MAP])
def exaustive_search(start_h,start_w):
  determined = {(start_h,start_w):0}
  f = lambda h,w: (0<=h<H and 0<=w<W) 
  
  q = [(start_h,start_w)]
  q_idx = 0
  while count != q_idx:
    h,w = q[q_idx]
    cost = determined[(h,w)]
    for dh,dw in [(-1,0),(1,0),(0,-1),(0,1)]:
      if f(h+dh,w+dw) and (h+dh,w+dw) not in determined.keys() and MAP[h+dh][w+dw]!="
        determined[(h+dh,w+dw)] = cost + 1
        q.append((h+dh,w+dw))
    q_idx+=1
  return max(determined.values())


print(max([exaustive_search(h,w) for h in range(H) for w in range(W) if MAP[h][w] !="

Solution (Python):
from collections import deque
def dfs_2d(H,W,M,start):
    que = deque()
    que.append([start[0],start[1]])
    distance = [[-1 for i in range(W)] for j in range(H)]
    dxdy = [[1,0],[-1,0],[0,1],[0,-1]]

    distance[start[0]][start[1]] = 0

    flag = False
    
    while que:
        x,y = que.popleft()
        for i,j in dxdy:
            dx = x + i
            dy = y + j
            if 0 <= dx <= H-1 and 0 <= dy <= W-1 and M[dx][dy] != "
                distance[dx][dy] = distance[x][y] + 1
                que.append([dx,dy])
                
    return max(max(i) for i in distance)

def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(input())
    ans = 0
    for i in range(H):
        for j in range(W):
            if M[i][j] != "
                start = [i,j]
                ans = max(ans,dfs_2d(H,W,M,start))

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
h,w=map(int,input().split())
g=[input() for _ in range(h)]
def search(y,x):
	que=[(y,x)]
	vis=[[-1]*w for _ in range(h)]
	vis[y][x]=0
	while que:
		cy,cx=que.pop(0)
		for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
			ny,nx=cy+dy,cx+dx
			if 0<=ny<h and 0<=nx<w and g[ny][nx]=="." and vis[ny][nx]==-1:
				vis[ny][nx]=vis[cy][cx]+1
				que.append((ny,nx))
	return max(max(l) for l in vis)
ans=0
for i in range(h):
	for j in range(w):
		if g[i][j]==".":
			ans=max(search(i,j),ans)
print(ans)

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

def bfs(sx, sy):
    q = collections.deque([(sx, sy)])
    checked = [[0 for _ in range(w)] for _ in range(h)]
    checked[i][j] = 1
    res = 0
    while q:
        qx, qy = q.popleft()
        for dx, dy in [(0,1),(1,0),(-1,0),(0,-1)]:
            x = qx+dx
            y = qy+dy
            if 0<=x<h and 0<=y<w and s[x][y] == "." and checked[x][y]==0:
                q.append((x,y))
                checked[x][y] = checked[qx][qy]+1
                res = max(checked[x][y],res)
    return res


ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            ans = max(ans, bfs(i, j)-1)

print(ans)

Solution (Python):
import math
import time
from collections import deque
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def makemaze(H, W):
    maze = []
    for i in range(H):
        s = input()
        a = []
        for c in s:
            if c == ".":
                a.append(1000)
            if c == "
                a.append(9999)
        maze.append(a)
        
    return maze

def maxroot(maze, x, y, w, h):
    sn = 0
    if maze[y][x] == 9999:
        return 0

    maze = deepcopy(maze)
    maze[y][x] = 0
    que = deque()
    que.append((y, x))


    while que:
        xy = que.popleft()
        y = xy[0]
        x = xy[1]
        if maze[y][x] == 9999:
            continue

        minlist = []
        if x > 0:
            minlist.append((y, x-1))
        if y > 0:
            minlist.append((y-1, x))
        if x < w-1:
            minlist.append((y, x+1))
        if y < h-1:
            minlist.append((y+1, x))

        dd = min(maze[y][x] for y, x in minlist) + 1
        dd = min(dd, maze[y][x])
        maze[y][x] = dd

        for y, x in minlist:
            
            if maze[y][x] == 1000 and (y, x) not in que:
                que.append((y, x))
                sn += 1
                if sn > 500:
                    print(maze)
                    print(que)
                    raise Exception
            

    maxx = 0
    for line in maze:
        try:
            maxa = max([i for i in line if i < 1000])
        except:
            maxa = 0
        maxx = max(maxx, maxa)
    return maxx


def main():
    H, W = iip()
    maze = makemaze(H, W)

    maxx = 1
    for y in range(H):
        for x in range(W):
            maxx = max(maxx, maxroot(maze, x, y, W, H))
            pass

    print(maxx)
    


main()

Solution (Python):
import math
import time
from collections import deque
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def makemaze(H, W):
    maze = []
    for i in range(H):
        s = input()
        a = []
        for c in s:
            if c == ".":
                a.append(1000)
            if c == "
                a.append(9999)
        maze.append(a)
        
    return maze

def maxroot(maze, x, y, w, h):
    sn = 0
    maxx = 0
    if maze[y][x] == 9999:
        return 0

    maze = deepcopy(maze)
    maze[y][x] = 0
    que = deque()
    que.append((y, x))


    while que:
        xy = que.pop()
        y = xy[0]
        x = xy[1]
        if maze[y][x] == 9999:
            continue

        minlist = []
        if x > 0:
            minlist.append((y, x-1))
        if y > 0:
            minlist.append((y-1, x))
        if x < w-1:
            minlist.append((y, x+1))
        if y < h-1:
            minlist.append((y+1, x))

        dd = min(maze[y][x] for y, x in minlist) + 1
        dd = min(dd, maze[y][x])
        maze[y][x] = dd

        for y, x in minlist:
            if maze[y][x] != 9999 and maze[y][x] > dd+2:
                que.append((y, x))
                sn += 1
            

    maxx = 0
    for line in maze:
        try:
            maxa = max([i for i in line if i < 1000])
        except:
            maxa = 0
        maxx = max(maxx, maxa)
    return maxx


def main():
    H, W = iip()
    maze = makemaze(H, W)

    maxx = 1
    for y in range(H):
        for x in range(W):
            maxx = max(maxx, maxroot(maze, x, y, W, H))
            pass

    print(maxx)
    


main()

Solution (Python):
import numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()


    ss.append(s)

    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.popleft()
        if (now_h, now_w) in que:
            continue
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h][next_w] == "
                continue
            a = dp[now_h, now_w] + 1
            if dp[next_h, next_w] > a:
                dp[next_h, next_w] = a
                que.append((next_h, next_w))

    score = np.max(dp[dp != 9999])
    return score

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh][sw] == ".":
            if sh > 0 and sh < h - 1 and sw > 0 and sw < w - 1:
                if 0 + (ss[sh + 1][sw] == ".") + (ss[sh - 1][sw] == ".") + (ss[sh][sw + 1] == ".") + (ss[sh][sw - 1] == ".") >= 3:
                    continue
            score = find(sh, sw)
            if maximum < score:
                maximum = score

print(maximum)

Solution (Python):


def read_input():
    h, w = map(int, input().split())
    maze = [list(input()) for _ in range(h)]
    cell = lambda x, y : x * w + y

    edges = {}
    for hi in range(h):
        for wi in range(w):
            edges[cell(hi, wi)] = []

            if maze[hi][wi] == "
                continue
            if 0 <= hi - 1:
                if maze[hi - 1][wi] == '.':
                    edges[cell(hi, wi)].append(cell(hi - 1, wi))
            if hi + 1 < h:
                if maze[hi + 1][wi] == '.':
                    edges[cell(hi, wi)].append(cell(hi + 1, wi))
            if 0 <= wi - 1:
                if maze[hi][wi - 1] == '.':
                    edges[cell(hi, wi)].append(cell(hi, wi - 1))
            if wi + 1 < w:
                if maze[hi][wi + 1] == '.':
                    edges[cell(hi, wi)].append(cell(hi, wi + 1))

    return h, w, edges, maze


def warshall_floyd(h, w, edges):
    v = h * w
    d = [[v + 1 for _ in range(v)] for _ in range(v)]

    for i in range(v):
        d[i][i] = 0

    for f, tlist in edges.items():
        for t in tlist:
            d[f][t] = 1

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

def submit():
    h, w, edges, maze = read_input()
    dist = warshall_floyd(h, w, edges)

    max_dist = 0
    v = h * w
    for i in range(v):
        for j in range(v):
            d = dist[i][j]
            if d > v:
                continue
            if d > max_dist:
                max_dist = d
    print(max_dist)


if __name__ == "__main__":
    submit()

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

def next(pos):
    x, y = pos
    ret = []
    for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        i = x + dx
        j = y + dy
        if 0 <= i < h and 0 <= j < w and f[i][j] != '
            ret.append((i, j))
    return ret

ans = 0
for i in range(h):
    for j in range(w):
        if f[i][j] != '
            s = {(i, j)}
            ng = set()
            dis = 0
            while s:
                t = set()
                for p in s:
                    ng.add(p)
                    for x, y in next(p):
                        if (x, y) not in ng:
                            t.add((x, y))
                s = t
                dis += 1
            ans = max(ans, dis - 1)
print(ans)

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

def dfs(sy, sx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "." and dist[h2][w2] == -1:
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist
ans = 0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == '
            continue
        d = dfs(sy,sx)
        for i in range(H):
            for k in range(W):
                ans = max(ans,d[i][k])
print(ans)

Solution (Python):
from collections import deque
import sys
buf = sys.stdin.buffer

h, w = map(int, buf.readline().split())
map = ""
for _ in range(h):
    map += input() + "


n = h * (w + 1)
periods = [[] for _ in range(n)]
dir = [-w - 1, 1, -1, w + 1]
for i in range(n):
    if map[i] == "
        continue
    for d in dir:
        next_i = i + d
        if next_i < 0 or next_i >= n or map[next_i] == "
            continue
        periods[i].append(next_i)


q = deque()
def bfs(now_i):
    for next_i in periods[now_i]:
        if con_cnt[next_i] == -1:
            con_cnt[next_i] = con_cnt[now_i] + 1
            q.append(next_i)
    
    if q:
        bfs(q.popleft())

start_points = [i for i, j in enumerate(periods) if len(j) > 0]
ans = 0
for start_point in start_points:
    con_cnt = [-1] * n
    con_cnt[start_point] = 0
    bfs(start_point)
    
    ans = max(ans, max(con_cnt))

print(ans)

Solution (Python):
import queue

def bfs(h,w,sx,sy,maze):
    dx = (1,0,-1,0)
    dy = (0,1,0,-1)
    fal = -1
    mx = -1
    
    d = [[fal for i in range(w)] for j in range(h)]
    que = queue.Queue()
    
    que.put((sx,sy))
    d[sx][sy] = 0
    
    while que.empty() == False:
        p = que.get()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < h and 0 <= ny and ny < w:
                if maze[nx][ny] != "
                    que.put((nx,ny))
                    d[nx][ny] = d[p[0]][p[1]] + 1
                    if d[nx][ny] > mx:
                        mx = d[nx][ny]
    return mx

def main():
    h,w = map(int,input().split())
    maze = []
    mx = -1
    for i in range(h):
        maze.append(list(input()))
    for i in range(h):
        for j in range(w):
            if maze[i][j] != "
                ans = bfs(h,w,i,j,maze)
                if ans > mx:
                    mx = ans
    print(mx)

if __name__ == "__main__":
    main()

Solution (Python):

import queue
h, w = map(int, input().split())
c = [input() for _ in range(h)]
inf = 10 ** 4
 
def bfs(sx,sy):
    d = [[-inf]*w for _ in range(h)]
    que = queue.Queue()
    que.put([sx,sy])
    d[sx][sy] = 0
    res = 0
    while not que.empty():
        qx, qy = que.get()
        for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            px, py = qx+dx, qy+dy
            if 0<=px<h and 0<=py<w and c[px][py]=='.' and d[px][py]== -inf:
                que.put([px,py])
                d[px][py] = d[qx][qy]+1
                res = max(d[px][py], res)
    return res            

ans = 0
for i in range(h):
    for j in range(w):
        if c[i][j] == '.':
            ans = max(ans, bfs(i, j))
            
print(ans)

Solution (Python):
import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
INF=-1

def bfs(sx,sy):
  
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  
  P=[]
  
  d=np.ones((H, W))*INF
  
  P.append([sx, sy])
  d[sx,sy]=0
    
  
  while len(P)>0:
    
    p=P.pop(0)
    
    """
    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 and nx<H and 0<=ny and ny<W and S[nx, ny]!="
        
        P.append([nx, ny])
        d[nx, ny]=d[p[0], p[1]]+1
  """
  
  if d[gx,gy]!=INF:
    result=d[gx, gy]
  else:
    result=0
  """
  result=d.max()
  return result
ans=0
Tlen=H*W
for sx in range(H):
  for sy in range(W):
    if S[sx,sy]=="
      continue
    res=bfs(sx,sy)
    ans=max(ans, res)
"""
for i in range(Tlen):
  for j in range(i,Tlen):
    sx,sy=i%H, int(i//H)
    gx,gy=j%H, int(j//H)
    
    if S[sx,sy]=="
      continue
    res=bfs(sx,sy,gx,gy)
    ans=max(ans, res)
"""
"""
for sx in range(H):
  for sy in range(W):
    for gx in range(H):
      for gy in range(W):
        if S[sx,sy]=="
          continue
        res=bfs(sx,sy,gx,gy)
        ans=max(ans, res)
"""
print(int(ans))