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 queue
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

d = [[-1,0],[1,0],[0,-1],[0,1]]

H,W = LI()
S = [list(input()) for _ in range(H)]

def bfs(s):
    dist = [[-1]*W for _ in range(H)]
    h,w = s
    dist[h][w] = 0
    que = queue.Queue()
    que.put(s)
    while(not(que.empty())):
        h,w = que.get_nowait()
        for dh,dw in d:
            nh,nw = h+dh,w+dw
            if 0<=nh<H and 0<=nw<W and dist[nh][nw]==-1 and S[nh][nw]=='.':
                dist[nh][nw] = dist[h][w] + 1
                que.put([nh,nw])
    return dist[h][w]

def main():
    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                ans = max(ans,bfs([h,w]))



    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]


ans = 0
for i in range(h):
    maze[i] = input()

INF = 1000
ans = 0


for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] == '
            continue
        else:
            distance = [[-1 for i in range(w)] for j in range(h)]


        queue = []

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

        distance[sy][sx] = 0

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

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

                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != '
                        queue.insert(0, (ny, nx))
                        distance[ny][nx] = distance[y][x] + 1

                        ans = max(ans, distance[ny][nx])

print(ans)

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

def clear_maze(sx, sy, maze):
    INF = -1
    field_x_length = len(maze[0])
    field_y_length = len(maze)
    distance = [[INF for i in range(field_x_length)]
                for j in range(field_y_length)]
    for i in range(field_y_length):
        for j in range(field_x_length):
            if maze[i][j] == '
                distance[i][j] = -100

    def bfs():
        queue = []
        queue.insert(0, (sx, sy))
        distance[sy][sx] = 0

        while len(queue):
            x, y = queue.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '
                    queue.insert(0, (nx, ny))
                    distance[ny][nx] = distance[y][x] + 1
        
        return distance
    return bfs()


S = [list(input()) for _ in range(h)]
ans = 0
cnt = 1
for i in range(h):
    for j in range(w):
        start = S[i][j]
        if start == '
            continue
            
        num = clear_maze(j, i, S)
        
        cnt += 1
        for k in range(h):
            ans = max(ans, max(num[k]))
print(ans)

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret



H, W = read_ints()
S = read_map(H)



mvx = (1, 0, -1, 0)
mvy = (0, 1, 0, -1)

from itertools import product, combinations
from collections import deque


def ret_shortest(si, sj):
    visited = [[False] * W for _ in range(H)]
    que = deque([(si, sj, 0)])
    visited[si][sj] = True

    ans = 0
    while que:
        i, j, cost = que.popleft()
        ans = max(ans, cost)
        for di, dj in zip(mvy, mvx):
            ni, nj = i + di, j + dj
            if not (-1 < ni < H) or not (-1 < nj < W):
                continue
            if S[ni][nj] == '.' and not visited[ni][nj]:
                que.append((ni, nj, cost + 1))
                visited[ni][nj] = True

    return ans


ans = 0

ans = 0
for i, j in product(range(H), range(W)):
    if S[i][j] == '.':
        ans = max(ret_shortest(i, j), ans)
print(ans)

Solution (Python):

from itertools import chain

H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
inf = float('inf')

def flatten(list_of_lists):
    "Flatten one level of nesting"
    return chain.from_iterable(list_of_lists)


def bfs(start, end):
    distance = [[inf for i in range(W)] for j in range(H)]
    queue = [(end, start)]
    distance[end][start] = 0

    while queue:
        y, x = queue.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if 0 <= nx < W and 0 <= ny < H and M[ny][nx] != '
                queue.insert(0, (ny, nx))
                distance[ny][nx] = distance[y][x] + 1
    return distance


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

            for length in list(flatten(bfs(i, j))):
                if length != inf and m < length:
                    m = length

print(m)

Solution (Python):
H,W = map(int,input().split())
maze = []
for i in range(H):
    s = input()
    m = []
    for j in range(W):
        m.append(s[j])
    maze.append(m)
d = [[10**9 for i in range(W*H)] for i in range(W*H)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for i in range(W*H):
    h = i//W
    w = i%W
    if maze[h][w] == '
        continue
    for j in range(4):
        x = w + dx[j]
        y = h + dy[j]
        k = x + y*W
        if 0<=x<=W-1:
            if 0<=y<=H-1:
                if maze[y][x] == '.':
                    d[i][k] = 1
                    d[k][i] = 1
for i in range(W*H):
    d[i][i] = 0
def warshall_floyd(d):
    
    for k in range(W*H):
        for i in range(W*H):
            for j in range(W*H):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
warshall_floyd(d)
ans = 0
for i in range(W*H):
    for j in range(W*H):
        if d[i][j] < 10**9:
            ans = max(ans,d[i][j])
print(ans)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall


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

    def get_index(h, w):
        return h * W + w

    for _ in range(H):
        S.append(input())

    l = [[0 for _ in range(H * W)] for _ in range(H * W)]
    for h in range(H):
        for w in range(W):
            if not S[h][w] == "
                if 0 <= h - 1 and S[h - 1][w] == ".":
                    l[get_index(h, w)][get_index(h - 1, w)] = 1
                if h + 1 < H and S[h + 1][w] == ".":
                    l[get_index(h, w)][get_index(h + 1, w)] = 1
                if 0 <= w - 1 and S[h][w - 1] == ".":
                    l[get_index(h, w)][get_index(h, w - 1)] = 1
                if w + 1 < W and S[h][w + 1] == ".":
                    l[get_index(h, w)][get_index(h, w + 1)] = 1

    

    fw = floyd_warshall(l)
    
    ans = 0
    for i in range(H * W):
        for j in range(H * W):
            ans = max(ans, fw[i][j] if fw[i][j] < float("inf") else 0)
            
            

    print(int(ans))


main()

Solution (Python):


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


def bfs(h,w,n):
    yoyaku=[]
    if h>0:
        if lis[h-1][w]>n+1 and mp[h-1][w]!="
            yoyaku.append([h-1,w,n+1])
    if w>0:
        if lis[h][w-1]>n+1 and mp[h][w-1]!="
            yoyaku.append([h,w-1,n+1])
    if h<H-1:
        if lis[h+1][w]>n+1 and mp[h+1][w]!="
            yoyaku.append([h+1,w,n+1])
    if w<W-1:
        if lis[h][w+1]>n+1 and mp[h][w+1]!="
            yoyaku.append([h,w+1,n+1])
    
    lis[h][w]=min(n,lis[h][w])
    return yoyaku

    

mp=[]
for _ in range(H):
    mp.append(list(input()))

ans=[]

for h in range(H):
    for w in range(W):
        lis=[[1000]*W for i in range(H)]
        que=[[[h,w,0]]] if mp[h][w]!="
        while True:
            if len(que)==0:
                break
            else:
                temp=que.pop(-1)
                
                for tem in temp:
                    
                    que.append(bfs(tem[0],tem[1],tem[2]))
        
        pre=0
        for item in lis:
            for tem in item:
                if tem==1000:
                    continue
                pre=max(pre,tem)    
        ans.append(pre)

    
print(max(ans))

Solution (Python):
import sys
from collections import deque
 
H,W = map(int,input().split())

town = []
visited = [[0 for i in range(W)] for j in range(H)]
 
for i in range(H): 
    c = input().strip()
    w = list(c)
    town.append(w)
            
def bfs(x,y) :
    q = deque()
    q.append([x,y,0])
    max_dist=0
    s=x
    t=y
    while q : 
        tx,ty,dist = q.popleft()
        if visited[ty][tx] == 0 :
            visited[ty][tx] = 1
            if town[ty][tx] == '
                pass
            else :
                
                for r in range (4):
                    nx = tx + dx[r]
                    ny = ty + dy[r]
                    count=0
                    if 0 <= nx < W and 0 <= ny < H and visited[ny][nx] == 0:
                        q.append([nx,ny,dist+1])
                        count+=1
                    if count==0 and dist>max_dist:
                        max_dist=dist
    return max_dist
                        
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
max_dist=0
for k in range(H):
    for l in range(W):
        max_dist=max(max_dist,bfs(l,k))
        visited = [[0 for i in range(W)] for j in range(H)]
print(max_dist)

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

S = list()
for i in range(H):
  S.append(list(map(lambda x: int(x == '.'), input())))

for i in range(H):
  S[i].append(0)
  S[i].append(0)
S.append([0 for _ in range(W + 2)])


def wfs(loc):
  moved = [
    [
      False for w in range(W + 2)
    ]
    for h in range(H + 2)
  ]
  queue = [(loc, 0)]
  ans = 0
  moved[loc[0]][loc[1]] = True
  while (queue):
    (h, w), move = queue.pop(0)
    for i, j in zip((1, -1, 0, 0), (0, 0, -1, 1)):
      _h, _w = h + i, w + j
      if not moved[_h][_w] and S[_h][_w] == 1:
        moved[_h][_w] = True
        queue.append(((_h, _w), move + 1))
    ans = max(ans, move)
  return ans

ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == 1:
      ans = max(ans, wfs((i, j)))
print(ans)

Solution (Python):

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

for i in range(H):
  s = list(map(str, input()))
  for j in range(W):
    edges[i][j] = s[j] 


def find_next(i, j):
  next = []
  if i > 0 and edges[i-1][j] == ".":
    next.append((i-1, j))
  if i < H - 1 and edges[i+1][j] == ".":
    next.append((i+1, j))
  if j > 0 and edges[i][j-1] == ".":
    next.append((i, j-1))
  if j < W - 1 and edges[i][j+1] == ".":
    next.append((i, j+1))
  return next

inf = 9999999999999999999

from collections import deque

def dfs(i, j):
  colors = [["white" for i in range(W)] for j in range(H)]
  queue = deque()
  queue.append((i, j))
  distance = [[inf for i in range(W)] for j in range(H)]
  distance[i][j] = 0

  result = -1
  while queue:
    i, j = map(int, queue.popleft())
    colors[i][j] = "black"
    for (x, y) in find_next(i, j):
      if colors[x][y] == "white":
        colors[x][y] = "gray"
        d = min(distance[i][j] + 1, distance[x][y])
        distance[x][y] = d
        result = max(result, d)
        queue.append((x, y))
  return result


ans = -1
for i in range(H):
  for j in range(W):
    if edges[i][j] == "
      continue
    
    ans = max(ans, dfs(i, j))

print(ans)

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
























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

h, w = map(int, input().split())
maze = [input() for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if (maze[i][j] == '.'):
            sy,sx = i,j
            visited = [[-1]*w for j in range(h)]
            vi = bfs(maze,visited,sy,sx)
            a = np.array(vi).flatten().max()
            ans = max(ans, a)



print(ans)

Solution (Python):
def dijkstra(si, sj):
  d=[[1000 for _ in range(W)] for _ in range(H)]
  d[si][sj]=0
  color=[]
  for i in range(H):
    tmp=[]
    for j in range(W):
      if S[i][j]=="
        tmp.append("BLACK")
      else:
        tmp.append("WHITE")
    color.append(tmp)
  pi, pj=0, 0
  while True:
    mincost=1000
    for i in range(H):
      for j in range(W):
        if color[i][j]!="BLACK" and d[i][j]<mincost:
          mincost=d[i][j]
          pi, pj=i, j
    if mincost==1000:
      break
    color[pi][pj]="BLACK"
    if pi>0 and S[pi-1][pj]=="." and color[pi-1][pj]!="BLACK" and d[pi][pj]+1<d[pi-1][pj]:
      d[pi-1][pj]=d[pi][pj]+1
      color[pi-1][pj]="GRAY"
    if pi<H-1 and S[pi+1][pj]=="." and color[pi+1][pj]!="BLACK" and d[pi][pj]+1<d[pi+1][pj]:
      d[pi+1][pj]=d[pi][pj]+1
      color[pi+1][pj]="GRAY"
    if pj>0 and S[pi][pj-1]=="." and color[pi][pj-1]!="BLACK" and d[pi][pj]+1<d[pi][pj-1]:
      d[pi][pj-1]=d[pi][pj]+1
      color[pi][pj-1]="GRAY"
    if pj<W-1 and S[pi][pj+1]=="." and color[pi][pj+1]!="BLACK" and d[pi][pj]+1<d[pi][pj+1]:
      d[pi][pj+1]=d[pi][pj]+1
      color[pi][pj+1]="GRAY"
  maxV=0
  for i in range(H):
    for j in range(W):
      if d[i][j]<1000:
        maxV=max(maxV, d[i][j])
  return maxV
  
H, W=map(int, input().split())
S=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    if S[i][j]==".":
      ans=max(ans, dijkstra(i, j))
print(ans)

Solution (Python):

from itertools import product
import numpy as np
def solve():
    H, W = map(int, input().split())
    M = np.zeros((H,W), dtype=int)
    for h in range(H):
        M[h] = np.array(list(int(x=='.') for x in input()))

    Dist = float('inf')*np.ones((H*W, H*W))
    
    u = M&np.roll(M, 1, axis=0)&np.concatenate((np.zeros((1,W), dtype=int),np.ones((H-1,W), dtype=int)), axis=0)
    d = M&np.roll(M, -1, axis=0)&np.concatenate((np.ones((H-1,W), dtype=int),np.zeros((1,W), dtype=int)), axis=0)
    l = M&np.roll(M, 1, axis=1)&np.concatenate((np.zeros((H,1), dtype=int),np.ones((H,W-1), dtype=int)), axis=1)
    r = M&np.roll(M, -1, axis=1)&np.concatenate((np.ones((H,W-1), dtype=int),np.zeros((H,1), dtype=int)), axis=1)

    hu, wu = np.where(u)
    Dist[hu*W+wu, (hu-1)*W+wu] = 1
    hd, wd = np.where(d)
    Dist[hd*W+wd, (hd+1)*W+wd] = 1
    hl, wl = np.where(l)
    Dist[hl*W+wl, hl*W+wl-1] = 1
    hr, wr = np.where(r)
    Dist[hr*W+wr, hr*W+wr+1] = 1
    for v3 in range(H*W):
        Dist = np.minimum(Dist, Dist[:,v3:v3+1] + Dist[v3:v3+1,:])
    
    Dist[Dist==float('inf')] = -1
    Dist[np.arange(H*W),np.arange(H*W)] = -1

    return str(int(Dist.max()))

if __name__ == '__main__':
    print(solve())

Solution (Python):
H,W=map(int, input().split())
S = [input() for i in range(H)]
m=H*W
l=[[None]*m for i in range(m)]
L=[0]*m
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            L[i*W+j]=1
for i in range(m):
    for j in range(m):
        if L[i] and L[j]:
            if i==j:
                l[i][j]=0
            elif abs(i-j)==W:
                l[i][j]=1
            elif i-j==1 and i%W!=0:
                l[i][j]=1
            elif j-i==1 and j%W!=0:
                l[i][j]=1
            else:
                l[i][j]=400
for i in range(m):
    if L[i]:
        for j in range(m):
            if L[j]:
                for k in range(m):
                    if L[k]:
                        if l[i][j]+l[i][k]<l[j][k]:
                            l[j][k]=l[i][j]+l[i][k]
M=0
for i in l:
    for j in i:
        if j:
            if M<j:
                M=j
print(M)

Solution (Python):
def C_BFS(R, C, sy, sx, gy, gx, c):
    """
    R:行数
    C:列数
    sy,sx:スタートの座標(sy行sx列)
    gy,gx:ゴールの座標(gy行gx列)
    c:迷路の形状(.:通路,
    """
    INF = float('inf')
    sy -= 1
    sx -= 1
    gy -= 1
    gx -= 1

    def bfs(maze, row, column, sy, sx, gy, gx):
        
        queue = []
        queue.insert(0, (sy, sx))
        dist = [[INF for _ in range(column)] for _ in range(row)]
        dist[sy][sx] = 0  
        dist_max = 0 
        while len(queue):
            y, x = queue.pop()



            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '
                    
                    queue.insert(0, (ny, nx))  
                    dist[ny][nx] = dist[y][x] + 1
                    if dist_max < dist[ny][nx]:
                        dist_max = dist[ny][nx]
        return dist_max
 
    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]
 
    ans = bfs(maze, R, C, sy, sx, gy, gx)
    return ans

R , C = [int(i) for i in input().split()]
c = [input() for _ in range(R)]

ans = 0
for sy in range(1, R+1):
    for sx in range(1, C+1):
        if c[sy-1][sx-1] != '
            count_tmp = C_BFS(R, C, sy, sx, 1, 1, c)
            if ans < count_tmp:
                ans = count_tmp
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    MOD = 10**9+7

    H,W = LMIIS()
    S = [input() for _ in range(H)]
    

    def tansaku(S,V,y,x,length):

        
        if  x >= 1 and S[y][x-1] == '.' and V[y][x-1] > length+1:
            V[y][x-1] = length+1
            tansaku(S,V,y,x-1,length+1)


        if x < W-1 and S[y][x+1] == '.' and V[y][x+1] > length+1:
            V[y][x+1] = length+1
            tansaku(S,V,y,x+1,length+1)


        if y >= 1 and S[y-1][x] == '.' and V[y-1][x] > length+1:
            V[y-1][x] = length+1
            tansaku(S,V,y-1,x,length+1)


        if y < H-1 and S[y+1][x] == '.' and V[y+1][x]> length+1:
            V[y+1][x] = length+1
            tansaku(S,V,y+1,x,length+1)

        return
    
    def getmax():
        max_length = 0
        for h in range(H):
            for w in range(W):
                V = [[MOD] * W for _ in range(H)]
                if S[h][w] == '.':
                    V[h][w] = 0
                    tansaku(S,V,h,w,0) 
                for v in V:
                    v = list(map(lambda x:x%MOD,v))
                    max_length = max(v+[max_length])
                    
        return max_length
    
    print(getmax())
    






if __name__ == '__main__':
    main()

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

sys.setrecursionlimit(410000)

INF = 10**6

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

def solve(sy,sx):
  d = [[INF]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if maze[i][j] == '
        d[i][j] = -INF          
  
  que = deque()
  que.append([sx,sy])
  d[sy][sx]=0

  while len(que)>0:
    px,py = que.popleft()

    for dx,dy in ((-1,0),(0,1),(1,0),(0,-1)):
      nx = px + dx
      ny = py + dy

      if (0 <= nx and nx < w and 0<=ny and ny < h) \
          and maze[ny][nx] != '
          and (d[ny][nx] == INF or d[ny][nx] > d[py][px] +1):              
        que.append((nx,ny))
        d[ny][nx] = d[py][px] +1

  return d

ans = 0
for sy in range(h):
  for sx in range(w):
    maze = copy.deepcopy(org_maze)
    if maze[sy][sx] == '.':      
      f = solve(sy,sx)      
      for i in range(h):        
        ans = max(ans,max(f[i]))
          
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
ans=0
for y in range(h):
    for x in range(w):
        b=[[0]*w for _ in range(h)]
        if a[y][x]==".":
            now=deque([(y,x)])
            while len(now)!=0:
                Y,X=now.popleft()
                for i,j in [[0,1],[0,-1],[1,0],[-1,0]]:
                    if 0<=Y+i<=h-1 and 0<=X+j<=w-1:
                        if a[Y+i][X+j]=="." and b[Y+i][X+j]==0 and (Y+i!=y or X+j!=x):
                            b[Y+i][X+j]=b[Y][X]+1
                            now.append((Y+i,X+j))
            c=0                
            for i in b:
                d=max(i)
                c=max(d,c)
            ans=max(ans,c)     
            
print(ans)

Solution (Python):
def clear_maze(sx, sy, maze):

    INF = float("inf")

    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]
    

    def bfs():
        queue = []

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

        distance[sx][sy] = 0

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


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

                if 0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length:
                    try:
                        if maze[nx][ny] != '
                            queue.insert(0, (nx, ny))
                            distance[nx][ny] = distance[x][y] + 1
                    except Exception as e:
                        print(nx, ny)
                        print(maze)
                        print(maze[nx][ny])
                        print(distance)
                        exit()
        res = 0
        for x in range(field_x_length):
            for y in range(field_y_length):
                if distance[x][y] < float("inf"):
                    res = max(res, distance[x][y])
        return res

    return bfs()


H, W = map(int, input().split())
maze = []
for w in range(H):
    maze.append([x for x in input()])
ans = 0
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            sx, sy = h, w
            ans = max(clear_maze(sx,sy, maze),ans)
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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()

def solve(maze, st_tuple):
    st_row, st_col = st_tuple
    W, H = len(maze[0]), len(maze)
    visited = [[0 for _ in range(W)] for __ in range(H)]
    steps = [[0 for _ in range(W)] for __ in range(H)]
    q = deque()
    q.append((st_row, st_col, 0))
    visited[st_row][st_col] = 1
    steps[st_row][st_col] = 0
    while q:
        cur_row, cur_col, count = q.popleft()
        for dr, dc in zip(DR, DC):
            next_row = cur_row + dr
            next_col = cur_col + dc
            if 0 <= next_row < H and 0 <= next_col < W:
                pass
            else:
                continue
            if maze[next_row][next_col] == '
                continue
            if visited[next_row][next_col]:
                continue
            q.append((next_row, next_col, count + 1))
            visited[next_row][next_col] = 1
            steps[next_row][next_col] = count + 1
    max_count = 0
    for r in range(H):
        for c in range(W):
            max_count = max(max_count, steps[r][c])
    return max_count

def main():
    H, W = LI()
    maze = []
    for _ in range(H):
        maze.append(S())
    num = 0
    axes = [(s_r, s_c) for s_r in range(H) for s_c in range(W)]
    for st_row, st_col in axes:
        if maze[st_row][st_col] == '
            continue
        a = solve(maze, (st_row, st_col))
        num = max(num, a)
    print(num)
main()

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

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

res = 0
inf = 9999999
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            continue
        dist = [[inf]*w for _ in range(h)]
        dist[i][j] = 0
        que = deque([[i, j]])
        while len(que):
            y, x = que.popleft()
            for dx, dy in zip(ddx, ddy):
                if x+dx < 0 or x+dx >= w or y+dy < 0 or y+dy >= h or s[y+dy][x+dx] == '
                    continue
                que.append([y+dy, x+dx])
                dist[y+dy][x+dx] = dist[y][x] + 1
        ma = 0
        for k in range(h):
            for l in range(w):
                if dist[k][l] < inf:
                    ma = max(ma, dist[k][l])
        res = max(ma, res)
print(res)

Solution (Python):

import copy

def display(masu):
    for m in masu:
        string = ''
        for mm in m:
            string += mm
        print(string)

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

S = []
for h in range(H):
    s = input()
    S.append(list(s))


start_position = []
for i in range(len(S)):
    for j in range(len(S[i])):
        if S[i][j] == '.':
            start_position.append((i, j))

max_distance = 0
for (i, j) in start_position:
    masu = copy.deepcopy(S)
    
    masu[i][j] = '*'
    now_position = [(i, j)]
    distance = -1
    while len(now_position) > 0:
        distance += 1
        new_position = []
        for (i, j) in now_position:
            
            if i > 0:
                if masu[i-1][j] == '.':
                    new_position.append((i-1, j))
                    masu[i-1][j] = '*'
            
            if i < H-1:
                if masu[i+1][j] == '.':
                    new_position.append((i+1, j))
                    masu[i+1][j] = '*'
            
            if j > 0:
                if masu[i][j-1] == '.':
                    new_position.append((i, j-1))
                    masu[i][j-1] = '*'
            
            if j < W-1:
                if masu[i][j+1] == '.':
                    new_position.append((i, j+1))
                    masu[i][j+1] = '*'
        now_position = new_position

    
    if distance > max_distance:
        max_distance = distance

print(max_distance)

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

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

M = np.zeros((H * W, H * W))

maiz = []

for _ in range(H):
    maiz.append(input())

move = [
    (1, 0),
    (0, 1),
    (-1, 0),
    (0, -1)
]

def is_valid_move(r, c, dr, dc):
    nr = r + dr
    if not (nr >= 0 and nr < H):
        return False
    
    nc = c + dc

    if not (nc >= 0 and nc < W):
        return False

    if maiz[nr][nc] == '.':
        return True

    return False

for row, row_elem in enumerate(maiz):
    for col, col_elem in enumerate(row_elem):
        if col_elem == "
            continue
        for drow, dcol in move:
            if not (is_valid_move(row, col, drow, dcol)):
                continue

            M[row * W + col][(drow + row) * W + col + dcol] = 1
            M[(drow + row) * W + col + dcol][row * W + col] = 1


res = shortest_path(M)
res[res > 10000000000000000000000000] = 0

print(int(np.max(res)))

Solution (Python):
from sys import stdin

inf = 10**10
h,w = [int(x) for x in stdin.readline().rstrip().split()]

li = [["
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]

def all_pairs_shortest_paths(W):
    
    n = len(W)
    
    res = [[0] * n for i in range(n)]
    
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

a = [[0 for i in range(w)]for j in range(h)]
for i in range(h):
    for j in range(w):
        a[i][j] = i*w + j

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

for i in range(h):
    for j in range(w-1):
        if li[i][j] == "." and li[i][j+1] == ".":
            lin[a[i][j]][a[i][j+1]] = 1
            lin[a[i][j+1]][a[i][j]] = 1

for i in range(h-1):
    for j in range(w):
        if li[i][j] == "." and li[i+1][j] == ".":
            lin[a[i][j]][a[i+1][j]] = 1
            lin[a[i][j]][a[i+1][j]] = 1

lis = all_pairs_shortest_paths(lin)

ma = 0
for i in range(h*w):
    for j in range(h*w):
        if lis[i][j] != 10**10:
            ma = max(lis[i][j],ma)

print(ma)

Solution (Python):


from collections import deque

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

if s==[list('.'*20) for i in range(20)]:
    print(40-2)
else:
    ans=0
    Q=deque()
    vec=[(1,0),(0,1),(-1,0),(0,-1)]
    his=[[0 for i in range(w)] for j in range(h)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=='
                continue
            Q.append([i,j,0])
            his[i][j]=1
            while Q:
                x,y,d=Q.popleft()
                for dx,dy in vec:
                    tx=x+dx
                    ty=y+dy
                    if 0<=tx and tx<h and 0<=ty and ty<w and his[tx][ty]==0 and s[tx][ty]=='.':
                        Q.append([tx,ty,d+1])
                        his[x][y]=1
                        ans=max(d+1,ans)
            his=[[0 for _ in range(w)] for __ in range(h)]
    print(ans)