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):
from collections import deque

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

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

ans = 0

for a in range(h):
    for b in range(w):
        if maze[a][b] == ".":
            DQ = deque([(a, b)])
            visit = [[-1] * w for _ in range(h)]
            visit[a][b] = 0
            tmp = 0
            while DQ:
                px, py = DQ.popleft()
                for i in range(4):
                    nx = px + dx[i]
                    ny = py + dy[i]
                    if 0<=nx<=h-1 and 0<=ny<=w-1 and maze[nx][ny]=="." and visit[nx][ny]==-1:
                        visit[nx][ny] = visit[px][py] + 1
                        tmp = visit[nx][ny]
                        DQ.append((nx, ny))
            ans = max(ans, tmp)

print(ans)

Solution (Python):
import collections 









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

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

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

cnt = 0

for j in range(H):
    for k in range(W):
            if maze[j][k]=='
                continue
            else:
                sy = j
                sx = k

                seen = [[-1 for _ in range(W)] for _ in range(H)]
                seen[sy][sx] = 0

                que  = collections.deque()  
                que.append([sy,sx])

                while(len(que)!=0):
                    p = que.popleft()
                    for i in range(4):
                        ny = p[0] + dy[i]
                        nx = p[1] + dx[i]
                        if (ny >= 0 and nx >=0 and ny < H and nx < W and seen[ny][nx] == -1 and maze[ny][nx] != '
                            seen[ny][nx] = seen[p[0]][p[1]] + 1
                            que.append([ny,nx])

                cnt = max(cnt, max([x for row in seen for x in row]))

print(cnt)

Solution (Python):
import sys
import itertools
import collections


def search(H, W, S, start):
    wall_i = ord(b'
    used = [[-1 for h in range(W)] for w in range(H)]

    qu = collections.deque()
    qu.append(start)
    used[start[0]][start[1]] = 0

    while qu:
        h, w = qu.popleft()
        cost = used[h][w]
        for h0, w0 in ((h - 1, w), (h + 1, w), (h, w - 1), (h, w + 1)):
            if not (0 <= h0 < H and 0 <= w0 < W):
                continue
            if used[h0][w0] != -1:
                continue
            if S[h0][w0] == wall_i:
                continue

            used[h0][w0] = cost + 1
            qu.append((h0, w0))

    return max(cost for costs in used for cost in costs)


def resolve(in_):
    H, W = map(int, next(in_).split())
    S = tuple(s.strip() for s in itertools.islice(in_, H))

    road_i = ord(b'.')

    roads = []
    for h in range(H):
        for w in range(W):
            if S[h][w] == road_i:
                roads.append((h, w))
    
    ans = max(search(H, W, S, start) for start in roads)
    
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import copy

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

def Maze(_x, _y):
  MAP2=copy.deepcopy(MAP)
  q=deque([[_x,_y]])
  MAP2[_y][_x]=0
  while q:
    xy=q.popleft()
    for d in [(0,-1),(-1,0),(0,1),(1,0)]:
      x2,y2=xy[0]+d[0],xy[1]+d[1]
      if x2<0 or y2<0 or x2>=W or y2>=H:
        continue
      if MAP2[y2][x2]=='.':
        q.append([x2,y2])
        MAP2[y2][x2]=MAP2[xy[1]][xy[0]]+1
  
  maxM=0
  for y in range(H):
    for x in range(W):
      if type(MAP2[y][x])==int:
        maxM=max(maxM, MAP2[y][x])
  return maxM
  

ans=0
for y in range(H):
  for x in range(W):
    if MAP[y][x]=='.':
      ans=max(ans, Maze(x,y))
print(ans)

Solution (Python):





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



visited = [[0 for i in range(w)] for j in range(h)]
quene = []
ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            quene.append([i,j])
            visited[i][j]=1




            dy_dx=[[1,0],[-1,0],[0,1],[0,-1]]

            while len(quene)>=1:
                now=quene.pop(0)

                for k in range(4):
                    y=now[0]+dy_dx[k][0]
                    x=now[1]+dy_dx[k][1]
                    if 0<=y<h and 0<=x<w:
                        if s[y][x]!="
                            visited[y][x]=visited[now[0]][now[1]]+1
                            quene.append([y,x])


        for l in range(h):
            for m in range(w):
                ans = max(ans,visited[l][m])
        visited = [[0 for i in range(w)] for j in range(h)]
print(ans-1)

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

ans = 0  
for i in range(H):
  for j in range(W):
    if maze[i][j] != "
      visited = [[float("inf")] * W for _ in range(H)]
      visited[i][j] = 0
      queue = [[i, j]]
      while queue:
        x, y = queue.pop()
        for p, q in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
          if (0 <= x + p < H) and (0 <= y + q < W):
            if (maze[x+p][y+q] !="
              if visited[x+p][y+q] > visited[x][y] + 1:
                queue.append([x+p, y+q])
                visited[x+p][y+q] = visited[x][y] + 1
      
      now = 0
      for k in range(H):
        for k2 in range(W):
          if visited[k][k2] < 10 ** 10:
            now = max(now, visited[k][k2])
      ans = max(ans, now)
      
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
R = [[0 for j in range(W)] for i in range(H)]
ans = 0
dx = [[-1, 0], [1, 0], [0, -1], [0, 1]]
for i in range(H):
  inp = input()
  for j in range(W):
  	if inp[j] == "
  	  R[i][j] = 1
for s in range(H * W):
  sh = s // W
  sw = s % W
  if R[sh][sw] == 1:
    continue
  D = [[-1 for j in range(W)] for i in range(H)]
  D[sh][sw] = 0
  d = deque([(sh, sw)])
  while len(d):
    a = d.pop()
    for k in range(4):
      hn = a[0] + dx[k][0]
      wn = a[1] + dx[k][1]
      if 0 <= hn < H and 0 <= wn < W and R[hn][wn] == 0 and D[hn][wn] == -1:
        D[hn][wn] = D[a[0]][a[1]] + 1
        ans = max(ans, D[hn][wn])
        d.appendleft((hn, wn))
print(ans)

Solution (Python):
from collections import deque

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

field = []
for i in range(H):
    field.append(input())

conn = [[[] for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            for e in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                h, w = i + e[0], j + e[1]
                if 0 <= h < H and 0 <= w < W and field[h][w] == '.':
                    conn[i][j].append([h, w])
d = 0
for i in range(H):
    for j in range(W):
        l = 0
        q = deque([[i, j]])
        dist = [[-1 for _ in range(W)] for _ in range(H)]
        dist[i][j] = 0
        while q:
            v = q.popleft()
            for w in conn[v[0]][v[1]]:
                if dist[w[0]][w[1]] == -1:
                    q.append(w)
                    dist[w[0]][w[1]] = dist[v[0]][v[1]] + 1
                    l = dist[w[0]][w[1]]

        d = max(d, l)

print(d)

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

h,w = map(int,input().split())
s = [list(input()) for i in range(h)]
t = ((0,1),(1,0),(-1,0),(0,-1))
m = 0
for sy in range(h):
    for sx in range(w):
        if s[sy][sx] == "
            continue
        ss = deepcopy(s)
        ss[sy][sx] = "
        q = deque([(0,sy,sx)])
        max_cost = 0
        my,mx = 0,0
        while(q):
            cost,y,x = q.popleft()
            max_cost = max(max_cost,cost)
            cost += 1
            for i,j in t:
                ny = y+i
                nx = x+j
                if 0 <= ny < h and 0 <= nx < w:
                    if ss[ny][nx] == ".":
                        q.append((cost,ny,nx))
                        ss[ny][nx] = "
        m = max(m,max_cost)
print(m)

Solution (Python):
import math

H, W = map(int, input().split())
S = [list(map(lambda x:x == '.', input())) for _ in range(H)]

d = [[math.inf] * (H * W) for _ in range(H * W)]

def node2pos(i):
    h = i // W
    w = i % W
    return h, w

for i in range(H * W):
    for j in range(H * W):
        h1, w1 = node2pos(i)
        h2, w2 = node2pos(j)
        if (abs(h1-h2) == 1 and w1 == w2) or (abs(w1-w2) == 1 and h1 == h2):
            if S[h1][w1] and S[h2][w2]:
                d[i][j] = 1
            if S[h1][w1]:
                d[i][i] = 1

for k in range(H * W):
    for i in range(H * W):
        for j in range(H * W):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0
for i in range(H * W):
    for j in range(H * W):
        if d[i][j] != math.inf:
            ans = max(ans, d[i][j])

print(ans)

Solution (Python):
import heapq


def abc151d_maze_master():
    h, w = map(int, input().split())
    s = []
    max_val = 0
    for i in range(h):
        s.append(input())
    for hi in range(h):
        for wi in range(w):
            if s[hi][wi] == '
            flg = [[-1] * w for _ in range(h)]
            flg[hi][wi] = 0
            q = [(0, hi, wi)]
            heapq.heapify(q)
            while len(q) > 0:
                d, hj, wj = heapq.heappop(q)
                for dh, dw in zip([0, 0, 1, -1], [1, -1, 0, 0]):
                    if 0 <= hj + dh < h and 0 <= wj + dw < w and s[hj + dh][wj + dw] != '
                            (flg[hj + dh][wj + dw] == -1 or flg[hj + dh][wj + dw] > flg[hj][wj] + 1):
                        heapq.heappush(q, (d + 1, hj + dh, wj + dw))
                        flg[hj + dh][wj + dw] = flg[hj][wj] + 1
                
            max_val = max(max_val, max([max(v) for v in flg]))
    print(max_val)


abc151d_maze_master()

Solution (Python):
from collections import deque

def input_bordered_grid(h, w, wall):
    grid = [wall * (w + 2)]
    for _ in range(1, h+1):
        grid.append(wall + input() + wall)
    grid.append(wall * (w + 2))
    return grid

h, w = map(int, input().split())
grid = input_bordered_grid(h, w, '

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

longest = 0
for sy in range(1, h+1):
    for sx in range(1, w+1):
        if grid[sy][sx] == '
            continue
        dist = [[-1] * (w+2) for _ in range(h+2)]
        dist[sy][sx] = 0
        q = deque()
        q.append((sy, sx))
        while q:
            y, x = q.popleft()
            longest = max(longest, dist[y][x])
            for dy, dx in move:
                yy = y + dy
                xx = x + dx
                if dist[yy][xx] == -1 and grid[yy][xx] == '.':
                    q.append((yy, xx))
                    dist[yy][xx] = dist[y][x] + 1
print(longest)

Solution (Python):
from collections import deque

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

maze=[list(input()) for i in range(h)]

ans=0

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


for i in range(h):
  for j in range(w):
        Q=deque()
        Q.append((i,j,0))
        
        if maze[i][j]=='
          continue

        dp=[[-1]*w for i in range(h)]

        dp[i][j]=0

        while Q:
          p=Q.popleft()
          ans=max(ans,p[2])
          for k in range(4):
            nx=p[0]+dx[k]
            ny=p[1]+dy[k]

            if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and dp[nx][ny]==-1:
              Q.append((nx,ny,p[2]+1))
              dp[nx][ny]=p[2]+1


print(ans)

Solution (Python):
from collections import deque


def bfs(i, j):
    dist = [[0] * w for _ in range(h)]
    q = deque()
    q.append((i, j))
    dist[i][j] = 1
    while q:
        nx, ny = q.pop()
        for dx, dy in D:
            X, Y = nx + dx, ny + dy
            if X < 0 or Y < 0 or X >= h or Y >= w:
                continue
            if m[X][Y] == "
                continue
            if dist[X][Y] != 0:
                continue

            q.appendleft((X, Y))
            dist[X][Y] = 1 + dist[nx][ny]
    mx = 0
    for i in dist:
        mx = max(mx, max(i))
    return mx


h, w = map(int, input().split())
m = [input() for _ in range(h)]
D = [(-1, 0), (0, -1), (1, 0), (0, 1)]
ans = 0
for i in range(h):
    for j in range(w):
        if m[i][j] == ".":
            ans = max(ans, bfs(i, j))

print(ans - 1)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
m = [list(input()) for _ in range(h)]
D = [(-1, 0), (0, -1), (1, 0), (0, 1)]


def bfs(i, j):
    dist = [[0] * w for _ in range(h)]
    que = deque()
    que.append((i, j))
    dist[i][j] = 1

    while que:
        nx, ny = que.pop()
        for dx, dy in D:
            if nx + dx < 0 or ny + dy < 0 or nx + dx >= h or ny + dy >= w:
                continue
            if m[nx + dx][ny + dy] == "
                continue
            if dist[nx + dx][ny + dy] != 0:
                continue

            que.appendleft((nx + dx, ny + dy))
            dist[nx + dx][ny + dy] = 1 + dist[nx][ny]
    mx = 0
    for i in dist:
        mx = max(mx, max(i))
    return mx


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

print(ans - 1)

Solution (Python):



import sys
import copy
import queue


sys.setrecursionlimit(10 ** 6)








def answer_sheet(meiro):
    return copy.deepcopy(meiro)





def get_around_point(point, h, w):
    around_points = []

    for ij in [(-1,0),(0,1),(1,0),(0,-1)]:
        i,j=ij
        new_i = point[0] + i
        new_j = point[1] + j
        if 0 <= new_i < h and 0 <= new_j < w:
            around_points.append([new_i, new_j])
    return around_points



def walkable(point, meiro):
    i = point[0]
    j = point[1]
    if meiro[i][j] == ".":
        return True
    return False



def never_had_been(point, sheet):
    if sheet[point[0]][point[1]] == ".":
        return True
    else:
        return False



def add_load_2_queue(point, h, w, meiro, sheet, que):
    around_points = get_around_point(point, h, w)
    for around_point in around_points:
        if walkable(around_point, meiro) and never_had_been(around_point, sheet):
            que.put(around_point)
            sheet[around_point[0]][around_point[1]] = sheet[point[0]][point[1]] + 1
    return sheet, que



def step(point, h, w, meiro, sheet, que):
    sheet, que = add_load_2_queue(point, h, w, meiro, sheet, que)
    if que.empty():
        return sheet
    next_point = que.get()
    return step(next_point, h, w, meiro, sheet, que)



def hash2minus(sheet):
    new_sheet = []
    for gyou in sheet:
        new_gyou = []
        for item in gyou:
            if item == "
                new_gyou.append(-1)
            else:
                new_gyou.append(item)
        new_sheet.append(new_gyou)
    return new_sheet










def min_dis(start, h, w, meiro):
    sheet = answer_sheet(meiro)
    que = queue.Queue()
    sheet[start[0]][start[1]] = 0
    return hash2minus(step(start, h, w, meiro, sheet, que))


import numpy as np

h, w = [int(i) for i in input().split()]
meiro = []

for i in range(h):
    meiro.append(list(input()))

ans = 0
for i in range(h):
    for j in range(w):
        if meiro[i][j] == ".":
            ans = max(ans, np.max(np.array(min_dis([i,j], h, w, meiro))))

print(ans)

Solution (Python):
H, W = list(map(int, input().split()))
S =[list(input()) for _ in range(H)]
N=H*W
INF=float('inf')
L=[[INF]*N for _ in range(N)]
for i in range(N):
    h=i//W
    w=i%W
    
    if S[h][w]=='.':
        L[i][i]=0
    if w>0 and S[h][w-1]=='.':
        L[i][i-1]=1
    if w<W-1 and S[h][w+1]=='.':
        L[i][i+1]=1
    if h>0 and S[h-1][w]=='.':
        L[i][i-W]=1
    if h<H-1 and S[h+1][w]=='.':
        L[i][i+W]=1


for i in range(N):
    via=L[i]
    if via[i]==INF:
        continue
    for j in range(N):
        st=L[j]
        if st[j]==INF:
            continue
        for k in range(N):
            L[j][k]=min(st[i]+via[k], st[k])

ans=0
for i in range(N):
    for j in range(N):
        if L[i][j]!=INF:
            ans=max(ans,L[i][j])
print(ans)

Solution (Python):
import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

@njit(cache=True)
def pos(W,h,w):
    return h*W+w

def solve(H,W,G):
    N = H*W+W
    INF=10**18

    dp = np.full((N,N),INF)
    for i in range(N):
        dp[i][i] = 0

    for h in range(H):
        for w in range(W):
            if G[h][w]: continue

            for i in range(4):
                dh = [0,1,0,-1][i]
                dw = [1,0,-1,0][i]
                if 0<=h+dh<H and 0<=w+dw<W:
                    if G[h+dh][w+dw]: continue
                    dp[pos(W,h,w)][pos(W,h+dh,w+dw)] = 1
                    dp[pos(W,h+dh,w+dw)][pos(W,h,w)] = 1


    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])


    for i in range(N):
        for j in range(N):
            if dp[i][j] != INF:
                ans = max(ans,dp[i][j])
    

    return ans





def main():
    H,W=mi()
    G = [[0] * W for _ in range(H)]
    for h in range(H):
        S = list(input())
        for w in range(W):
            G[h][w] = S[w] == "

    print(solve(H,W,np.array(G,bool)))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    
    cc.export('pos', '(i8,i8,i8,)')(pos)
    cc.export('solve', '(i8,i8,b1[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    try:
        from my_module import solve
        from my_module import pos
    except:
        cc_export()
        exit()

    main()

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

from collections import deque
def bfs(h,w,sy,sx,S):
    maze=[[10**9]*(W)for _ in range(H)]
    maze[sy-1][sx-1]=0
    que=deque([[sy-1,sx-1]])
    count=0
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<h and 0<=nextx<w:
                dist1=S[nexty][nextx]
                dist2=maze[nexty][nextx]
            else:
                continue
            if dist1!='
                if dist2>maze[y][x]+1:
                    maze[nexty][nextx]=maze[y][x]+1
                    count=max(count,maze[nexty][nextx])
                    que.append([nexty,nextx])
    return count

ans=0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx]=='.':
            now=bfs(H,W,sy+1,sx+1,S)
            ans=max(ans,now)

print(ans)

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

from collections import deque
import math


def bfs(h,w,sy,sx,S):
    maze=[[10**9]*(W)for _ in range(H)]

    maze[sy-1][sx-1]=0
    que=deque([[sy-1,sx-1]])
    count=0
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<h and 0<=nextx<w:
                dist1=S[nexty][nextx]
                dist2=maze[nexty][nextx]
            else:
                continue
            if dist1!='
                if dist2>maze[y][x]+1:
                    maze[nexty][nextx]=maze[y][x]+1
                    count=max(count,maze[nexty][nextx])
                    que.append([nexty,nextx])
    return count

ans=0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx]=='.':
            now=bfs(H,W,sy+1,sx+1,S)
            ans=max(ans,now)

print(ans)

Solution (Python):
import queue

def bfs(maze,h,w,sy,sx):
    dist=[[-1 for _ in range(w)] for _ in range(h)]
    q=queue.deque([[sy,sx]])
    dist[sy][sx]=0
    while q:
        y,x=q.popleft()
        for dy,dx in d:
            ny,nx=y+dy,x+dx
            if 0<=ny<h and 0<=nx<w and dist[ny][nx]==-1 and maze[ny][nx]!='
                dist[ny][nx]=dist[y][x]+1
                q.append([ny,nx])
    return max([max(i) for i in dist])

h,w=map(int,input().split())
a=[input() for _ in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
for sy in range(h):
    for sx in range(w):
        if a[sy][sx]!='
            ans=max(ans,bfs(a,h,w,sy,sx))
print(ans)

Solution (Python):
from collections import defaultdict, deque

h, w = map(int, input().split())
tizu = [input() for _ in range(h)]
ans = 0
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for i in range(h):
    for j in range(w):
        if tizu[i][j] == "
            continue
        check = [[False for _ in range(w)] for _ in range(h)]
        check[i][j] = True
        queue = deque()
        queue.append([i, j])
        queue.append(0)
        while queue:
            pos = queue.popleft()
            ans_sub = queue.popleft()
            for dh, dw in directions:
                nh = pos[0] + dh
                nw = pos[1] + dw
                if nh == -1 or nh == h or nw == -1 or nw == w:
                    continue
                if tizu[nh][nw] == "
                    continue
                if check[nh][nw]:
                    continue
                check[nh][nw] = True
                queue.append([nh, nw])
                queue.append(ans_sub + 1)
        ans = max(ans, ans_sub)
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
yudlr = [-1, 1, 0, 0]
xudlr = [0, 0, -1, 1]
D = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue
        d = [[-1] * W for _ in range(H)]
        d[i][j] = 0
        Q = deque()
        Q.append([i, j])
        while len(Q) > 0:
            q = Q.popleft()
            y, x = q[0], q[1]
            for k in range(4):
                y1 = y + yudlr[k]
                x1 = x + xudlr[k]
                if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
                    continue
                if S[y1][x1] == '
                    continue
                if d[y1][x1] != -1:
                    continue
                d[y1][x1] = d[y][x] + 1
                Q.append([y1, x1])
        Dij = max(list(map(lambda x: max(x), d)))
        D = max(D, Dij)
print(D)

Solution (Python):
import copy
H, W = map(int, input().split())
s = []
wall=[]
maze = [0] * (H * W)
path = dict()
leaf = []

for i in range(H):
  temp = list(input())
  for j, var in enumerate(temp):
    idx = i*W + j
    maze[idx] = var
    if var == ".":
      s.append(idx)

for i in range(H):
  for j in range(W):
    idx = i*W + j
    temp = []
    if j != 0 and maze[idx-1] != "
      temp.append(idx - 1)
    if j != W - 1 and maze[idx+1] != "
      temp.append(idx + 1)
    if i != 0 and maze[idx-W] != "
      temp.append(idx - W)
    if i != H - 1 and maze[idx + W] != "
      temp.append(idx + W)
    path[idx] = temp

ans = 0
start = copy.copy(s)

for st in start:
  dp = [float('inf')] * (H * W)
  prev = [-1] * (H*W)
  dp[st] = 0
  s2 = copy.copy(s)
  while len(s2) > 0:
    dpmin = float('inf')
    idx = 0
    for i in s2:
      if dpmin > dp[i]:
        idx = i
        dpmin = dp[i]
    now = s2.pop(s2.index(idx))
    flag = 0
    for i in path[now]:
      if dp[i] > 1 + dp[now]:
        dp[i] = 1 + dp[now]
        prev[i] = now
        flag = 1
    if flag == 0:
      leaf.append(now)
  dp = [i for i in dp if i != float('inf')]
  if ans < max(dp):
    ans = max(dp)
print(ans)

Solution (Python):
import collections
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

H, W, *S = open(0).read().split()
H, W = [int(_) for _ in [H, W]]
A = []
B = []
C = []
for i in range(H * W):
    x, y = divmod(i, W)
    if S[x][y] == '.':
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '.':
                A += [i]
                B += [nx * W + ny]
                C += [1]
F = floyd_warshall(csr_matrix((C, (A, B)), shape=(H*W, H*W)))
print(int(np.max(F[F!=np.inf])))

Solution (Python):
from collections import deque


def LI():
    return list(map(int, input().split()))


def LSH(h):
    return [input() for _ in range(h)]


H, W = LI()
Fi = LSH(H)
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for sh in range(H):  
    for sw in range(W):
        if Fi[sh][sw] == "
            continue
        d = deque()
        d.append([sh, sw])
        looked = [[0 for i in range(W)]for j in range(H)]
        looked[sh][sw] = 1
        while d:
            h, w = d.popleft()
            for i in move:
                a = h+i[0]
                b = w+i[1]
                if not(0 <= a < H) or not(0 <= b < W) or Fi[a][b] == "
                    continue
                d.append([a, b])
                looked[a][b] = looked[h][w]+1
            if len(d) == 0:
                ans = max(ans, looked[h][w]-1)
print(ans)

Solution (Python):
from collections import deque
import copy

h,w=map(int,input().split())
Inf=float('inf')
maze1=[]
for _ in range(h):
  s=list(input())
  for u in range(w):
    if s[u]=='.':
      s[u]=Inf
  maze1.append(s)
  
def maze_solve(maze,sy,sx):
  qu=deque([[sy,sx]])
  maze[sy][sx]=0
  
  while qu:
    y,x=qu.popleft()
    
    T=maze[y][x]
    for i in ([1,0],[-1,0],[0,1],[0,-1]):
      ny=y+i[0]
      nx=x+i[1]
      if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='
        
        if maze[ny][nx]>T+1:
          maze[ny][nx]=T+1
          qu.append([ny,nx])
          
  ans=-Inf
  for i in range(h):
    for j in range(w):
      if maze[i][j]!='
        ans=max(ans,maze[i][j])
  return ans
  

ans=-Inf
for i in range(h):
  for j in range(w):
    if maze1[i][j]!='
      maze2=copy.deepcopy(maze1)
      ans=max(ans,maze_solve(maze2,i,j))
            
            
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)] 
vi=[ [-1 for _ in range(w)] for _ in range(h)]
st=deque()

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

mx=0

for i in range(h):
  for j in range(w):
    vi=[ [-1 for _ in range(w)] for _ in range(h)]
    st.append([i,j,0])
    
    while st:
      h1,w1,k=st.popleft()

      if 0<=h1<h and 0<=w1<w and vi[h1][w1]==-1 and s[h1][w1]==".":
        vi[h1][w1]=k
        for m in d:
          st.append([h1+m[0],w1+m[1],k+1])
    for m in vi:
      mx=max(mx,max(m))

print(mx)

Solution (Python):
H,W=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
l_count=[[0]*W for i in range(H)]
from collections import deque
def answer(st_X,st_Y):
   tmp_X,tmp_Y=st_X,st_Y
   que=deque([[tmp_X,tmp_Y]])
   after=set()
   while que:
      tmp_X,tmp_Y=que.popleft()
      nu=l_count[tmp_Y][tmp_X]
      after.add((tmp_X,tmp_Y))
      if tmp_X>0 and l[tmp_Y][tmp_X-1]=="." and (tmp_X-1,tmp_Y) not in after and [tmp_X-1,tmp_Y] not in que:
         l_count[tmp_Y][tmp_X-1]=nu+1
         que.append([tmp_X-1,tmp_Y])
      if tmp_Y>0 and l[tmp_Y-1][tmp_X]=="." and (tmp_X,tmp_Y-1) not in after and [tmp_X,tmp_Y-1] not in que:
         l_count[tmp_Y-1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y-1])
      if tmp_X<W-1 and l[tmp_Y][tmp_X+1]=="." and (tmp_X+1,tmp_Y) not in after and [tmp_X+1,tmp_Y] not in que:
         l_count[tmp_Y][tmp_X+1]=nu+1
         que.append([tmp_X+1,tmp_Y])
      if tmp_Y<H-1 and l[tmp_Y+1][tmp_X]=="." and (tmp_X,tmp_Y+1) not in after and [tmp_X,tmp_Y+1] not in que:
         l_count[tmp_Y+1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y+1])
ans=0
for i in range(H):
   for j in range(W):
      if l[i][j]==".":
         l_count=[[0]*W for i in range(H)]
         answer(j,i)
         tmp=max(sum(l_count,[]))
         ans=max(ans,tmp)
print(ans)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
S=[input() for _ in range(H)]
ans=0
d=deque([])
for i in range(H):
  for j in range(W):
    if S[i][j]=='
      continue
    d.append((i,j,0))
    visited=[[-1]*W for _ in range(H)]
    visited[i][j]=0
    while d:
      x,y,c=d.popleft()
      for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and visited[nx][ny]==-1 and S[nx][ny]=='.':
          visited[nx][ny]=c+1
          d.append((nx,ny,c+1))
    ans=max(ans,c)
print(ans)

Solution (Python):
from collections import deque
import numpy as np
def main():
    H,W = map(int,input().split())
    maze = [input() for _ in range(H)]

    ans = 0
    for x in range(H):
        for y in range(W):
            
            if maze[x][y] == "
                continue

            
            distance = [[0]*W for _ in range(H)]
            
            stack = deque([[x,y]])

            while stack:
                h,w = stack.popleft()
                for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                    new_h, new_w = h+i, w+j
                    if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                        continue
                    elif maze[new_h][new_w] != '
                        distance[new_h][new_w] = distance[h][w] + 1
                        stack.append([new_h, new_w])

            distance[x][y] = 0
            ans = max(ans, np.max(distance))

    print(ans)

main()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)





from collections import deque



INF = 1 << 50

def bfs(MAZE, start):
    s = start + (0,)
    queue = deque([s])
    max_count = 0
    seen = set()
    seen.add(start)
    while queue:
        y,x,count = queue.popleft()
        max_count = max(max_count, count)
        for i,j in ((0,1), (0,-1), (1,0), (-1, 0)):
            next_y, next_x = y + i, x + j
            
            if not (next_y, next_x) in seen and MAZE[next_y][next_x] == '.':
                queue.append((next_y, next_x, count+1))
                seen.add((next_y, next_x))
    return max_count


def run():
    H, W = map(int, input().split())
    MAZE = ['
    for _ in range(H):
        s = input()
        s = '
        MAZE.append(s)
    MAZE.append('

    
    

    ways = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if MAZE[i][j] == '.':
                ways.append((i, j))

    max_count = 0
    for s_i, s_j in ways:
        min_count = bfs(MAZE, (s_i, s_j))
        
        
        max_count = max(max_count, min_count)

    print(max_count)

if __name__ == "__main__":
    run()