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):
H, W = map(int, input().split())
N = H * W
S = [input() for _ in range(H)]


def idx(i, j):
    return i * W + j


adj = [[float('inf')] * N for _ in range(N)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue
        index = idx(i, j)
        if i > 0 and S[i - 1][j] == '.':
            adj[index][idx(i - 1, j)] = 1
            adj[idx(i - 1, j)][index] = 1
        if j < W - 1 and S[i][j + 1] == '.':
            adj[index][idx(i, j + 1)] = 1
            adj[idx(i, j + 1)][index] = 1
        if i < H - 1 and S[i + 1][j] == '.':
            adj[index][idx(i + 1, j)] = 1
            adj[idx(i + 1, j)][index] = 1
        if j > 0 and S[i][j - 1] == '.':
            adj[index][idx(i, j - 1)] = 1
            adj[idx(i, j - 1)][index] = 1

class WarshallFloyd(object):

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._dist)
        for i in range(v_len):  
            for j in range(v_len):  
                for k in range(v_len):  
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


from math import isinf

wf = WarshallFloyd(adj)
ans = 0
for r in wf._dist:
    m = max(filter(lambda x: not isinf(x), r))
    ans = max(ans, m)
print(ans)

Solution (Python):
from collections import deque

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

ans = 0

def bfs(sx, sy):
    global ans
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque()
    q.append((sx, sy))
    dist[sy][sx] = 0

    while q:
        v = q.popleft()
        x, y = v[0], v[1]
        for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            newx, newy = x+dx, y+dy
            if not (0 <= newx < W):
                continue
            if not (0 <= newy < H):
                continue
            if M[newy][newx] == '
                continue
            if dist[newy][newx] != -1:
                continue
            q.append((newx, newy))
            d = dist[y][x] + 1
            dist[newy][newx] = dist[y][x] + 1
            ans = max(ans, d)

for y in range(H):
    for x in range(W):
        if M[y][x] == '
            continue
        bfs(x, y)

print(ans)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
grid = ["
grid += ["
grid += ["
move = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0
for i, j in enumerate(grid):
    for k, l in enumerate(j):
        if l == ".":
            done = [[-1 for _ in range(w + 2)] for _ in range(h + 2)]
            done[i][k] = 0
            todo = deque([(i, k)])
            while todo:
                n, m = todo.popleft()
                d = done[n][m]
                for dn, dm in move:
                    if grid[n + dn][m + dm] == "
                        pass
                    elif done[n + dn][m + dm] >= 0:
                        pass
                    elif grid[n + dn][m + dm] == ".":
                        todo.append((n + dn, m + dm))
                        done[n + dn][m + dm] = d + 1
            for x in done:
                for y in x:
                    ans = max(ans, y)
print(ans)

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


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


for h in range(H):
    for w in range(W):
        
        if field[h][w] == "
            continue
        dist = [[-1] * W for _ in range(H)]
        que_x = deque()
        que_y = deque()
        dist[h][w] = 0
        que_x.append(h)
        que_y.append(w)

        
        while que_x and que_y:
            x = que_x[0]
            y = que_y[0]
            que_x.popleft()
            que_y.popleft()
            tmp_max = 0
            for direct in range(4):
                nx = x + dx[direct]
                ny = y + dy[direct]
                if nx < 0 or H <= nx or ny < 0 or W <= ny:      
                    continue
                if field[nx][ny] == "
                    continue
                if dist[nx][ny] == -1:          
                    que_x.append(nx)
                    que_y.append(ny)
                    dist[nx][ny] = dist[x][y] + 1   
        for i in range(H):
            for k in range(W):
                tmp_max = max(dist[i][k], tmp_max)
        ans = max(tmp_max, ans)
print(ans)

Solution (Python):
from collections import deque


def solve():
    H, W = map(int, input().split())
    S = [[0 for i in range(W)] for j in range(H)]
    visited = [[-1 for i in range(W)] for j in range(H)]
    

    for h in range(H):
        a = input()
        for w in range(W):
            if a[w] == '
                S[h][w] = -1

    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    ans = -1

    for h in range(H):
        for w in range(W):
            if S[h][w] == -1:
                continue

            visited[h][w] = 0
            queue = deque([[h, w]])
            while queue:
                y, x = queue.popleft()
                for dir in directions:
                    next_y = y + dir[0]
                    next_x = x + dir[1]
                    if next_y >= 0 and next_x >= 0 and next_y < H and next_x < W and S[next_y][next_x] == 0 and visited[next_y][next_x] == -1:
                        visited[next_y][next_x] = visited[y][x] + 1
                        queue.append([next_y, next_x])

            for row in visited:
                ma = max(row)
                ans = max(ans, ma)

            visited = [[-1 for i in range(W)] for j in range(H)]

    print(ans)


solve()

Solution (Python):
H,W=map(int,input().split())
S=[[1 if c=='
from collections import deque
r=0
for i in range(H):
    for j in range(W):
        if S[i][j]==1:
            continue
        d=[[-1]*W for x in range(H)]
        q=deque([(i,j,0)])
        d[i][j]=0
        while q:
            x,y,d0=q.popleft()
            if x>0 and S[x-1][y]==0 and d[x-1][y]==-1:
                q.append((x-1,y,d0+1))
                d[x-1][y]=d0+1
            if y>0 and S[x][y-1]==0 and d[x][y-1]==-1:
                q.append((x,y-1,d0+1))
                d[x][y-1]=d0+1
            if x<H-1 and S[x+1][y]==0 and d[x+1][y]==-1:
                q.append((x+1,y,d0+1))
                d[x+1][y]=d0+1
            if y<W-1 and S[x][y+1]==0 and d[x][y+1]==-1:
                q.append((x,y+1,d0+1))
                d[x][y+1]=d0+1
        r=max(r,d0)
print(r)

Solution (Python):
from collections import deque

def bfs(grid, start, wall, h, w):
    visited = [[False for _ in range(w+2)] for _ in range(h+2)]
    visited[start[0]][start[1]] = True

    queue = deque([])
    queue.append([start[0], start[1], 0])
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    cost = 0
    while queue:
        y,x,cnt = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall or visited[y_][x_]:
                continue
            queue.append([y_,x_,cnt+1])
            if cnt+1 > cost:
                cost = cnt+1
            visited[y_][x_] = True
    return cost

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)


cand = {2:[], 3:[], 4:[]}
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
        wl = 0
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                wl += 1
        if wl > 1:
            cand[wl].append((y,x))

ans = 0
starts = []
for i in [4,3,2]:
    if cand[i] != []:
        starts = cand[i]
        break
for start in starts:
    cnt = bfs(grid, start, wall, h, w)
    if cnt > ans:
        ans = cnt
print(ans)

Solution (Python):
import collections

H,W=map(int,input().split())
S=[input() for i in range(H)]
cl=set()
for sy,sx in [[h,w] for h in range(H) for w in range(W)]:
    if S[sy][sx]!="
        stack=collections.deque([[sy,sx,0]])
        itta=set([sy*100+sx])
        
        while stack:
            y,x,m=stack.popleft()
            cl.add(m)
            lst=[]

            if y>0:lst.append([-1,0])
            if y<H-1:lst.append([1,0])
            if x>0:lst.append([0,-1])
            if x<W-1:lst.append([0,1])

            for a,b in lst:
                Y=y+a
                X=x+b
                
                if S[Y][X]=="." and not Y*100+X in itta:
                    stack.append([Y,X,m+1])
                    itta.add(Y*100+X)
print(max(cl))

Solution (Python):
def dijkstra(g,st):
    from heapq import heappush, heappop, heapify
    inf=10**18
    dist=[inf for i in range(len(g))]
    visited=[False for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st))
    while que:
        c,v=heappop(que)
        if visited[v]:
            continue
        visited[v]=True
        for x in g[v]:
            tmp=x[0]+c
            if tmp<dist[x[1]] and not visited[x[1]]:
                dist[x[1]]=tmp
                heappush(que,(tmp,x[1]))
    return dist

h,w=map(int,input().split())
field=[[]for i in range(h)]
num=0
st=-1
for i in range(h):
    s=input()
    for j in range(w):
        field[i].append((s[j],num))
        if s[j]=='.' and st==-1:
            st=num
        num+=1
dx=[1,0,-1,0]
dy=[0,1,0,-1]

g=[[]for i in range(h*w)]
for i in range(h):
    for j in range(w):
        if field[i][j][0]!='.':
            continue
        for x,y in zip(dx,dy):
            if 0<=i+x<h and 0<=j+y<w and field[i+x][j+y][0]!='
                g[field[i][j][1]].append((1,field[i+x][j+y][1]))

mxx=0
for i in range(h):
    for j in range(w):
        if field[i][j][0]=='
            continue
        for ans in dijkstra(g,field[i][j][1]):
            if ans!=10**18:
                mxx=max(mxx,ans)
print(mxx)

Solution (Python):
from collections import deque, defaultdict


def bfs():
    adjacent = [(1, 0), (0, 1), (-1, 0), (0, -1)]  
    cnt = defaultdict(int)
    hoge = 0
    while len(q):
        cx, cy = q.popleft()  
        for a, b in adjacent:
            if 0 > cx+a or 0 > cy+b:
                continue
            if abs(cx+a) >= H or abs(cy+b) >= W:
                continue
            if visited[cx+a][cy+b]:
                continue
            if gridgraph[cx+a][cy+b] == "
                continue
            cnt[(cx+a, cy+b)] = cnt[(cx, cy)] + 1
            hoge = max(hoge, cnt[(cx+a, cy+b)])
            q.append((cx+a, cy+b))
            visited[cx+a][cy+b] = True
    return hoge


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


ans = 0
for i in range(H):
    for j in range(W):
        visited = [[False]*W for _ in range(H)]
        tmp = 0
        
        if gridgraph[i][j] == "
            continue
        q = deque()
        q.append((i, j))
        visited[i][j] = True
        ans = max(ans, bfs())

print(ans)

Solution (Python):
import heapq


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


def dfs(y, x):
    dist = [[-1]*w for _ in range(h)]
    if meiro[y][x] == '
        return 0
    dist[y][x] = 0

    pattern = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    todo = []
    for dy, dx in pattern:
        ny, nx = y + dy, x + dx
        if 0 <= ny <= h-1 and 0 <= nx <= w-1:
            if meiro[ny][nx] == '.':
                heapq.heappush(todo, [1, ny, nx])

    while todo:
        d, y, x = heapq.heappop(todo)
        if meiro[y][x] == '
            continue
        if dist[y][x] != -1:
                continue

        dist[y][x] = d
        for dy, dx in pattern:
            ny, nx = y + dy, x + dx
            if 0 <= ny <= h - 1 and 0 <= nx <= w - 1:
                if dist[ny][nx] == -1 and meiro[ny][nx] == '.':
                    heapq.heappush(todo, [d+1, ny, nx])

    res = 0
    for line in dist:
        res = max(max(line), res)

    return res


ans = []
for y in range(h):
    for x in range(w):
        ans.append(dfs(y, x))

print(max(ans))

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


def solve():
    H, W = map(int, input().split())
    maze = [[-2 for _ in range(W)] for _ in range(H)]
    s_point = []
    for i in range(H):
        line = input()
        for j in range(W):
            if line[j] == '
                maze[i][j] = -1
            else:
                s_point.append((i, j))

    dyx = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    N = len(s_point)
    ans = 0
    for i in range(N):
        ans_tmp = 0
        maze_tmp = deepcopy(maze)
        sy, sx = s_point[i]
        maze_tmp[sy][sx] = 0
        que = deque([[sy, sx]])
        while que:
            cy, cx = que.popleft()
            for j in range(4):
                ny, nx = cy + dyx[j][0], cx + dyx[j][1]
                if 0 <= ny <= H - 1 and 0 <= nx <= W - 1:
                    if maze_tmp[ny][nx] == -2:
                        maze_tmp[ny][nx] = maze_tmp[cy][cx] + 1
                        ans_tmp = max(ans_tmp, maze_tmp[ny][nx])
                        que.append([ny, nx])
        ans = max(ans, ans_tmp)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import copy
from collections import deque
H,W=map(int, input().split())
Abase=[[None]*W for _ in range(H)]
starts=deque()
for h in range(H):
  s=input()
  for w in range(W):
    if s[w]=='.':
      starts.append((h,w))
    else:
      Abase[h][w]=-1
 
DIF=[(1,0),(0,1),(-1,0),(0,-1)]
answers=[]
while starts:
  A=copy.deepcopy(Abase)
  st=starts.popleft()
  A[st[0]][st[1]]=0
  d=deque()
  d.append(st)
  while d:
    point=d.popleft()
    for dif in DIF:
      x=point[0]+dif[0]
      y=point[1]+dif[1]
      if 0<=x<H and 0<=y<W and A[x][y]==None:
        d.append((x,y))
        A[x][y]=A[point[0]][point[1]]+1
  ans=0    
  for h in range(H):
    Amax=max(A[h])
    ans=max(ans,Amax)
  answers.append(ans)
print(max(answers))

Solution (Python):
import sys
sys.setrecursionlimit(4100000)

import math
from collections import deque

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

I_MIN = 0
I_MAX = 0
J_MIN = 0
J_MAX = 0
I_DELTA = [1, 0, -1, 0]
J_DELTA = [0, -1, 0, 1]
visited_set = set()
grid = None


def resolve():
    global visited_set, I_MAX, J_MAX, grid

    H, W = [int(x) for x in sys.stdin.readline().split()]
    grid = [list(sys.stdin.readline().split()[0]) for _ in range(H)]

    

    I_MAX = H - 1
    J_MAX = W - 1
    queue = deque()

    max_dist = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':
                queue.append((i, j, 0))
                visited_set.add((i, j))
                while (len(queue) > 0):
                    i, j, dist = queue.popleft()
                    if max_dist < dist:
                        max_dist = dist
                    for d in range(4):
                        i_next = i + I_DELTA[d]
                        j_next = j + J_DELTA[d]
                        if (
                                i_next, j_next
                        ) not in visited_set and I_MIN <= i_next <= I_MAX and J_MIN <= j_next <= J_MAX:
                            visited_set.add((i_next, j_next))
                            s = grid[i_next][j_next]
                            if s == '.':
                                queue.append((i_next, j_next, dist + 1))
                else:
                    visited_set.clear()
    print(max_dist)


if __name__ == "__main__":
    resolve()





import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3
...
...
..."""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 5
...
.
.
        output = """10"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """1 2
.."""
        output = """1"""
        self.assertIO(input, output)

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

s = [list(input()) for _ in range(h)]

n = h * w
m = [[float('inf') for _ in range(n)] for _ in range(n)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            m[i * w + j][i * w + j] = 0


for i in range(h):
    for j in range(w-1):
        if s[i][j] == '.':
            if s[i][j+1] == '.':
                m[i * w + j][i * w + j + 1] = 1
                m[i * w + j + 1][i * w + j] = 1

for i in range(h-1):
    for j in range(w):
        if s[i][j] == '.':
            if s[i+1][j] == '.':
                m[i*w+j][(i+1)*w+j] = 1
                m[(i+1)*w+j][i*w+j] = 1

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

m = warshall_floyd(m)
ans = 0
for i in range(n):
    for j in range(n):
        if m[i][j] != float('inf'):
            ans = max(ans, m[i][j])

print(ans)

Solution (Python):
from collections import deque 
h,w=map(int,input().split())
S=[input() for _ in range(h)]
def long(S,start):
    tbl=[[-1]*w for _ in range(h)]
    tbl[start[0]][start[1]]=0
    todo=deque([start])
    while todo:
        a,b=todo.popleft()
        c=tbl[a][b]
        if a!=0 and S[a-1][b]=="." and tbl[a-1][b]==-1:
            tbl[a-1][b]=c+1
            todo.append([a-1,b])
        if a!=h-1 and S[a+1][b]=="." and tbl[a+1][b]==-1:
            tbl[a+1][b]=c+1
            todo.append([a+1,b])
        if b!=0 and S[a][b-1]=="." and tbl[a][b-1]==-1:
            tbl[a][b-1]=c+1
            todo.append([a,b-1])
        if b!=w-1 and S[a][b+1]=="." and tbl[a][b+1]==-1:
            tbl[a][b+1]=c+1
            todo.append([a,b+1])
    m=0
    for i in range(h):
        for j in range(w):
            m=max(m,tbl[i][j])
    return m
ans=0
for x in range(h):
    for y in range(w):
        if S[x][y]==".":
            ans=max(ans,long(S,[x,y]))
print(ans)

Solution (Python):
h,w = map(int,input().split())
s = []
ans = 0
for _ in range(h):
  si = str(input())
  s.append(si)
for i in range(h):
  for j in range(w):
    if s[i][j] == ".":
      t = [[-1 for _ in range(w)] for _ in range(h)]
      t[i][j] = 0
      stack = [[i,j]]
      while stack:
        ni,nj = stack.pop(0)
        tn = t[ni][nj]
        for p,q in [[-1,0],[1,0],[0,-1],[0,1]]:
          x = ni+p
          y = nj+q
          if 0 <= x and x <= h-1 and 0 <= y and y <= w-1:
            if t[x][y] == -1:
              if s[x][y] == ".":
                t[x][y] = tn+1
                stack.append([x,y])
      mx = max(max(t[xx]) for xx in range(h))
      if mx > ans:
        ans = mx
print(ans)

Solution (Python):
from collections import deque
import sys

input = sys.stdin.readline
H,W = map(int, input().split())
table = []
dist = []
dx = [1,0,-1,0]
dy = [0,-1,0,1]
ans = 0

for i in range(H):
    S = list(input())
    table.append(S)

for sy in range(H):
    for sx in range(W):
        if table[sy][sx] == "
            continue
        Q = deque()
        Q.append((sy,sx))
        temp = [[-1]*W for i in range(H)]
        temp[sy][sx] = 0
        max_d = 0
        while Q:
            y,x = Q.popleft()
            for i in range(4):
                ny = y+dy[i]
                nx = x+dx[i]
                if 0<=ny<H and 0<=nx<W and temp[ny][nx]==-1 and table[ny][nx]==".":
                    Q.append((ny,nx))
                    temp[ny][nx]=temp[y][x]+1
                    max_d = max(max_d,temp[y][x]+1)
        ans = max(ans,max_d)
print(ans)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
l = []
for i in range(n):
    a = list(input())
    l.append(a)

ans = 0
for i in range(n):
    for j in range(m):
        if l[i][j] == ".":
            bfs = [[-1]*m for k in range(n)]
            bfs[i][j] = 0
            q = deque([])
            q.append((i,j))
            dx = [0,0,-1,1]
            dy = [-1,1,0,0]
            while q:
                x,y = q.popleft()

                for t in range(4):
                    nx = x+dx[t]
                    ny = y + dy[t]

                    if 0 <= nx < n and 0 <= ny < m and bfs[nx][ny] == -1 and l[nx][ny] != "
                        q.append((nx,ny))
                        bfs[nx][ny] = bfs[x][y] +1

            for bf in bfs:
                ans = max(ans,max(bf))
            
print(ans)

Solution (Python):
import sys
h, w = [int(i) for i in sys.stdin.readline().split()]
s_ls = []
target = []
for i in range(h):
    s = sys.stdin.readline().strip()
    for j, _s in enumerate(s):
        if _s == ".":
            target.append(i * h + j)
    s_ls.append(s)

len_target = len(target)
already = set()
def wfs(x, y):
    res = 0
    for plus_x, plus_y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        next_x = max(0, min(w - 1, x + plus_x))
        next_y = max(0, min(h - 1, y + plus_y))
        if (next_y, next_x) not in already and s_ls[next_y][next_x] == ".":
            already.add((next_y, next_x))
            res = max(res, wfs(next_x, next_y) + 1)
    return res

best = 0
for start in range(h * w):
    start_x, start_y = start % w, start // w
    if s_ls[start_y][start_x] == "
        continue
    already = {(start_y, start_x)}
    ls = {start_y * w + start_x : 0}
    que = [(start_y, start_x, 0)]
    res = 0
    while len(que) > 0:
        y, x, dis = que.pop(0)
        for plus_x, plus_y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            next_x = max(0, min(w - 1, x + plus_x))
            next_y = max(0, min(h - 1, y + plus_y))
            if (next_y, next_x) not in already and s_ls[next_y][next_x] == ".":
                already.add((next_y, next_x))
                que.append((next_y, next_x, dis+1))
                ls[next_y * w + next_x] = dis + 1
                res = max(res, dis + 1)
        if len(already) == len_target:
            break
    best = max(best, res)
print(best)

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

N = W * H
E = [[0] * N  for _ in range(N)]
for i, e in enumerate(E):
    e[i] = 1

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

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

INF = float("inf")

A = floyd_warshall(E)
print(int(max(max(a if a != INF else 0 for a in a) for a in A)))

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



H,W = II()
S = [list(map(str, input())) for _ in range(H)]

def bfs(c,s):
    X=[[-1]*W for i in range(H)]
    if c[s[0]][s[1]]=='
        return X
    X[s[0]][s[1]]=0
    q=[s]
    counter=1
    d = [(0,1),(0,-1),(1,0),(-1,0)]
    
    while q:
        q1=[]
        for i in q:
            for d0 in d:
                j = (i[0]+d0[0],i[1]+d0[1])
                if 0<=j[0]<=H-1 and 0<=j[1]<=W-1:
                    if c[j[0]][j[1]]=='.':
                        
                        
                        if X[j[0]][j[1]]==-1:
                            X[j[0]][j[1]]=counter
                            q1.append(j)
        q=q1
        counter+=1
    return X

ans = 0
for si in range(H):
    for sj in range(W):
        d = bfs(S,(si,sj))
        
        now = 0
        for i in range(len(d)):
            for j in range(len(d[0])):
                if d[i][j]>now:
                    now = d[i][j]
        if now==-1:
            continue
        if now>ans:
            ans = now
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

H,W=map(int,input().split())
S=[list(input().strip()) for _ in range(H)]
G=[[float("inf")]*H*W for _ in range(H*W)]
for i in range(H*W):
    G[i][i]=0

for h in range(H):
    for w in range(W-1):
        if S[h][w]=="." and S[h][w+1]==".":
            G[W*h+w][W*h+w+1]=1
            G[W*h+w+1][W*h+w]=1

for h in range(H-1):
    for w in range(W):
        if S[h][w]=="." and S[h+1][w]==".":
            G[W*h+w][W*(h+1)+w]=1
            G[W*(h+1)+w][W*h+w]=1


n=H*W
G=warshall_floyd(G)

ans=0
for h in range(H*W):
    for w in range(H*W):
        if G[h][w]!=float("inf"):
            ans=max(ans,G[h][w])
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def bfs(H, W, grid, src):
    """ BFS(グリッド、重みなし) """
    from collections import deque

    h, w = src
    directions = ((1,0),(-1,0),(0,1),(0,-1))
    que = deque([(h, w, 0)])
    dist = list2d(H+2, W+2, -1)
    while que:
        h, w, c = que.popleft()
        if dist[h][w] != -1:
            continue
        dist[h][w] = c
        for dh, dw in directions:
            h2 = h + dh
            w2 = w + dw
            if grid[h2][w2] == '
                continue
            que.append((h2, w2, c+1))
    return dist

H, W = MAP()
grid = build_grid(H, W, '

ans = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if grid[i][j] != '
            res = bfs(H, W, grid, (i, j))
            for k in range(1, H+1):
                for l in range(1, W+1):
                    ans = max(ans, res[k][l])
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
field=[["
field=[["
def bfs(a,b):
  Q=deque([(a,b)])
  s=[[0 for i in range(w+2)] for j in range(h+2)]
  visited=[[False for i in range(w+2)] for j in range(h+2)]
  visited[a][b]=True
  while Q:
    v=Q.popleft()
    for i in [(1,0),(0,-1),(-1,0),(0,1)]:
      if visited[v[0]+i[0]][v[1]+i[1]]:continue
      if field[v[0]+i[0]][v[1]+i[1]]=="
      visited[v[0]+i[0]][v[1]+i[1]]=True
      s[v[0]+i[0]][v[1]+i[1]]=s[v[0]][v[1]]+1
      Q.append([v[0]+i[0],v[1]+i[1]])
  return max([max(s[i]) for i in range(h+2)])
ans=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if field[i][j]=="
    if bfs(i,j)>ans:ans=bfs(i,j)
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from collections import deque

h, w = [int(item) for item in input().split()]
field = []
field.append("
for i in range(h):
    field.append("
field.append("


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if field[i][j] == "
            continue
        dist = [[-1] * (w + 2) for _ in range(h + 2)]
        dist[i][j] = 0
        dq = deque()
        dq.append((i, j, 0))
        while dq:
            x, y, d = dq.popleft()
            if field[x+1][y] == "." and dist[x+1][y] == -1:
                dist[x+1][y] = d+1
                dq.append((x+1, y, d+1))
            if field[x][y+1] == "." and dist[x][y+1] == -1:
                dist[x][y+1] = d+1
                dq.append((x, y+1, d+1))
            if field[x-1][y] == "." and dist[x-1][y] == -1:
                dist[x-1][y] = d+1
                dq.append((x-1, y, d+1))
            if field[x][y-1] == "." and dist[x][y-1] == -1:
                dist[x][y-1] = d+1
                dq.append((x, y-1, d+1))
        for line in dist:
            ans = max(ans, max(line))
        
print(ans)