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 itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce

from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()
 
from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    visited = [False] * (H * W)
    q = deque([(start[0], start[1], 0)])
    max_d = 0
    while q:
        (i, j, d) = q.popleft()
        max_d = max(max_d, d)
        if visited[i * W + j]:
            continue
        visited[i * W + j] = True
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '
                    continue
                if visited[(i + dy) * W + j + dx]:
                    continue
                q.append((i + dy, j + dx, d + 1))
    return max_d
 
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce

from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()
 
from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    visited = [False] * (H * W)
    q = deque([(start[0], start[1], 0)])
    max_d = 0
    while q:
        (i, j, d) = q.popleft()
        max_d = max(max_d, d)
        visited[i * W + j] = True
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '
                    continue
                if visited[(i + dy) * W + j + dx]:
                    continue
                visited[(i + dy) * W + j + dx] = True
                q.append((i + dy, j + dx, d + 1))
    return max_d
 
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce

from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()
 
from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    q = deque([start])
    dist[start[0] * W + start[1]] = 0
    max_d = 0
    while q:
        (i, j) = q.popleft()
        d = dist[i * W + j]
        max_d = max(d, max_d)
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '
                    continue
                if dist[(i + dy) * W + j + dx] != INF:
                    continue
                dist[(i + dy) * W + j + dx] = d + 1
                q.append((i + dy, j + dx))
    return max_d
 
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce

from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()

from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    q = deque([(start[0], start[1], 100)])
    dist[start[0] * W + start[1]] = 0
    while q:
        (i, j, z) = q.popleft()
        d = dist[i * W + j]
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '
                    continue
                if dist[(i + dy) * W + j + dx] != INF:
                    continue
                dist[(i + dy) * W + j + dx] = d + 1
                q.append((i + dy, j + dx, 100))
    return max(x for x in dist if x < INF)

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce

from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()

from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    q = deque([start])
    dist[start[0] * W + start[1]] = 0
    while q:
        (i, j) = q.popleft()
        d = dist[i * W + j]
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '
                    continue
                if dist[(i + dy) * W + j + dx] != INF:
                    continue
                dist[(i + dy) * W + j + dx] = d + 1
                q.append((i + dy, j + dx))
    return max(x for x in dist if x < INF)

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)

Solution (Python):
from collections import deque, defaultdict

inf = 10**15
h, w = map(int, input().split())


G = [[inf]*(h*w) for _ in range(h*w)]


def warshall_floyd(d):
    
    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])
    return d
  
li = []
for j in range(h):
    g = list(input())
    temp = []
    for i in g:
      if i=='.':
        temp.append(0)
      else:
        temp.append(1)
    li.append(temp)
for i in range(h):
    for j in range(w-1):
        if li[i][j]==0 and li[i][j+1]==0:
            G[i*w+j][i*w+j+1] = 1
            G[i*w+j+1][i*w+j] = 1
            G[i*w+j][i*w+j] = 0
            G[i*w+j+1][i*w+j+1] = 0
for i in range(h-1):
    for j in range(w):
        if li[i][j] ==0 and li[i+1][j]==0:
            G[i*w+j][i*w+w+j] = 1
            G[i*w+j+w][i*w+j] = 1
            G[i*w+j+w][i*w+j+w] = 0
            G[i*w+j][i*w+j] = 0
    

d = warshall_floyd(G)
max_ = 0
for i in range(h*w):
  for j in range(h*w):
    if d[i][j] < inf:
      max_ = max(max_, d[i][j])
print(max_)

Solution (Python):
H,W = map(int,input().split())
maze = []
from collections import deque
for _ in range(H):
    s = list(input())
    maze.append(s)
direction = [[1,0],[0,1],[-1,0],[0,-1]]
ans = -1
for row in range(H):
    for col in range(W):
        if maze[row][col] == "
            continue
        distance = [[-1 for _ in range(W)] for _ in range(H)]
        d = deque([[row,col]])
        distance[row][col] = 0
        while(len(d)>0):
            nowrow, nowcol = d.popleft()
            for subrow, subcol in direction:
                subrow += nowrow
                subcol += nowcol
                if subrow < 0 or subrow >= H or subcol < 0 or subcol >= W:
                    continue
                if maze[subrow][subcol] == "
                    continue
                if distance[subrow][subcol] != -1:
                    continue
                d.append([subrow, subcol])
                distance[subrow][subcol] = distance[nowrow][nowcol] + 1
            ans = max(ans,max([max(maxrow) for maxrow in distance]))
print(ans)

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

res = 0
move = [(1,0),(0,1),(0,-1),(-1,0)]
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      visited = [[False]*W for _ in range(H) ]
      q = deque([(i,j)])
      depth = -1
      while q:
        depth += 1
        L = len(q)
        new = deque([])
        for _ in range(L):
          i,j = q.popleft()
          if visited[i][j]: continue
          visited[i][j] = True
          for y,x in move:
            if 0<=i+y<H and 0<=j+x<W and not visited[i+y][j+x]:
              if maze[i+y][j+x] == ".":
                new.append((i+y,j+x))
        q = new
      res = max(res, depth)

print(res)

Solution (Python):
def bfs(x0, y0, maze, dis):
    from collections import deque
    max_x = len(maze[0])
    max_y = len(maze)

    dis[y0][x0] = 0
    dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    q = deque()
    q.append([x0, y0, dis[y0][x0]])

    while len(q) > 0:
        x, y, d = q.popleft()

        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy

            if 0 > nx or max_x <= nx or 0 > ny or max_y <= ny:
                continue
            if maze[ny][nx] == "
                continue
            if dis[ny][nx] != -1:
                continue

            dis[ny][nx] = d + 1
            q.append([nx, ny, dis[ny][nx]])

    return


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

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

for i in range(h):
    s[i] = input()

ans = 0
for i in range(h):
    for j in range(w):
        dis = [[-1] * w for _ in range(h)]

        if s[i][j] != "
            bfs(j, i, s, dis)

        d = 0

        for k in range(h):
            for l in range(w):
                d = max(d, dis[k][l])

        ans = max(ans, d)

print(ans)

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

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

def f(x,y):
  x-=1;y-=1
  dist=[[-1 for j in range(w)] for i in range(h)]
  dist[x][y]=0
  que = deque([(x,y,0)])

  while que:
    r,s,t = que.popleft()
    for i,j in [(-1,0),(0,-1),(1,0),(0,1)]:
      if not (0<=r+i<h and 0<=s+j<w):
        continue
      if dist[r+i][s+j]>=0:
        continue
      if graph[r+i][s+j]=="
        continue
      dist[r+i][s+j]=t+1
      que.append([r+i,s+j,t+1])
  return np.amax(dist)
ans=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if graph[i-1][j-1]=="
      continue
    ans=max(ans,f(i,j))
print(ans)

Solution (Python):
import numpy as np
from scipy.sparse import csgraph
H, W = map(int, input().split())
maze = "".join(input() for _ in range(H))
array = np.zeros((H * W, H * W), dtype=np.bool)
for n in range(H * W):
    if maze[n] == "
        continue
    r, c = divmod(n, W)
    if c and maze[n - 1] == ".":
        array[n][n - 1] = 1
        array[n - 1][n] = 1
    if r and maze[n - W] == ".":
        array[n][n - W] = 1
        array[n - W][n] = 1
dist = csgraph.shortest_path(array)
print(int(dist[dist < 401].max()))

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

from collections import deque

H,W = map(int,readline().split())
H += 2; W += 2
grid = '
for _ in range(H-2):
    grid += '
grid += '

def bfs(start):
    INF = 10 ** 9
    dist = [INF] * (H*W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1,1,W,-W):
            w = v + move
            if grid[w] == '
                continue
            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)
    return max(x for x in dist if x < INF)

answer = max(bfs(v) for v in range(H*W) if grid[v] != '
print(answer)

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


def bfs(a,b):
  maze=copy.deepcopy(maze1)
  dp=[[0 for i in range(w)] for j in range(h)]
  q=deque([[a,b]])
  
  maze[a][b]="
  while len(q)>0:
    i,j=q.popleft()
    if 0<=i+1<=h-1 and 0<=j<=w-1 and maze[i+1][j]==".":
      maze[i+1][j]="
      dp[i+1][j]=dp[i][j]+1
      q.append([i+1,j])
    if 0<=i-1<=h-1 and 0<=j<=w-1 and maze[i-1][j]==".":
      maze[i-1][j]="
      dp[i-1][j]=dp[i][j]+1
      q.append([i-1,j])
    if 0<=i<=h-1 and 0<=j-1<=w-1 and maze[i][j-1]==".":
      maze[i][j-1]="
      dp[i][j-1]=dp[i][j]+1
      q.append([i,j-1])
    if 0<=i<=h-1 and 0<=j+1<=w-1 and maze[i][j+1]==".":
      maze[i][j+1]="
      dp[i][j+1]=dp[i][j]+1
      q.append([i,j+1])
  sum=0
  for i in range(h):
    sum=max(max(dp[i]),sum)
  return sum
  
  
ans=0
for k in range(h):
  for l in range(w):
    if maze1[k][l]==".":
      ans=max(bfs(k,l),ans)

print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
l=list()
l.append('
for i in range(h):
    l.append('
l.append('
p=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if l[i][j]=='
            continue
        s=[[-1 for a in b] for b in l]
        q=deque([[i,j]])
        s[i][j]=0
        while len(q)>0:
            a,b=q.popleft()
            for x,y in [[1,0],[0,1],[-1,0],[0,-1]]:
                if l[a+x][b+y]=='
                    continue
                q.append([a+x,b+y])
                s[a+x][b+y]=s[a][b]+1
        r=0
        for x in s:
            for y in x:
                r=max(y,r)
        p=max(r,p)
print(p)

Solution (Python):
h,w=map(int,input().split())
s=[input() for _ in range(h)]
road = [(i,j) for i in range(h) for j in range(w) if s[i][j]=='.']

from collections import deque

dists = set()
for r in road:
  d = deque()
  d.append(r)
  dist = {r:0}
  while d:
    x,y = d.popleft()
    if s[x][y] == '
    for p in [(x,y+1),(x,y-1),(x-1,y),(x+1,y)]:
      if (0<=p[0]<h and 0<=p[1]<w) == False:continue
      if s[p[0]][p[1]] == '
      if p in dist:continue
      dist[p]=dist[(x,y)]+1
      d.append(p)
  dist_max = max([dist[v] for v in dist])
  dists.add(dist_max)
print(max(dists))

Solution (Python):
from collections import deque

H, W = map(int, input().split())
L = [str(input()) for _ in range(H)]
ans = 0
for h in range(H):
    for w in range(W):
        if L[h][w] == '
            continue
        else:
            flag = [[-1] * W for _ in range(H)]
            depth = [[0] * W for _ in range(H)]
            flag[h][w] = 0
            q = deque([(h, w)])
            while q:
                i, j = q.popleft()
                d = depth[i][j]
                if i != H - 1:
                    if L[i+1][j] == '.' and flag[i+1][j] < 0:
                        flag[i+1][j] = 0
                        depth[i+1][j] = d + 1
                        q.append((i+1, j))
                if i != 0:
                    if L[i-1][j] == '.' and flag[i-1][j] < 0:
                        flag[i-1][j] = 0
                        depth[i-1][j] = d + 1
                        q.append((i-1, j))
                if j != W - 1:
                    if L[i][j+1] == '.' and flag[i][j+1] < 0:
                        flag[i][j+1] = 0
                        depth[i][j+1] = d + 1
                        q.append((i, j+1))
                if j != 0:
                    if L[i][j-1] == '.' and flag[i][j-1] < 0:
                        flag[i][j-1] = 0
                        depth[i][j-1] = d + 1
                        q.append((i, j-1))
                ans = max(ans, d)
print(ans)

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

A=[]
for i in range(h):
  s=input()
  A.append([s[i] for i in range(w)])
g=[[[]for i in range(w)] for _ in range(h)]

for i in range(h):
  for j in range(w):
    if A[i][j]=='.':
      if i-1>=0:
          if A[i-1][j]=='.':
            g[i][j].append((i-1,j))
      if i+1<h:
          if A[i+1][j]=='.':
            g[i][j].append((i+1,j))          
      if j+1<w:
          if A[i][j+1]=='.':
            g[i][j].append((i,j+1))          
      if j-1>=0:
          if A[i][j-1]=='.':
            g[i][j].append((i,j-1))  
        
from collections import deque
def bfs(a,b):
  time=[[-1]*w for _ in range(h)]
  time[a][b]=0
  stack=deque([])
  stack.append((a,b))
  n=1
  while stack:
    d=stack.popleft()
    for v in g[d[0]][d[1]]:
      if time[v[0]][v[1]]==-1:
        time[v[0]][v[1]]=time[d[0]][d[1]]+1
        stack.append(v)
        
      else:
        continue
     
  timem=0
  for i in range(h):
    for j in range(w):
      timem=max(timem,time[i][j])
  return timem
ans=0
for i in range(h):
  for j in range(w):
    bfsm=bfs(i,j)
    ans=max(ans,bfsm)
print(ans)

Solution (Python):
from collections import deque

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

res = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "
            continue
        dist = [[-1] * w for _ in range(h)]
        dist[i][j] = 0
        d = deque()
        d.append([i, j])

        while d:
            pos_x, pos_y = d.popleft()
            dist_max = dist[pos_x][pos_y]
            for k in range(4):
                x, y = pos_x + dx[k], pos_y + dy[k]
                if 0 <= x < h and 0 <= y < w and s[x][y] == "." and dist[x][y] == -1:
                    dist[x][y] = dist[pos_x][pos_y] + 1
                    d.append([x, y])

        res = max(res, dist_max)

print(res)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
s = [0]*(h+2)
s[0]  = ["
s[-1] = ["
for i in range(h):
    s[i+1] = ["
ans = 1
for i in range(h+2):
    for j in range(w+2):
        if s[i][j] != ".":
            pass
        else:
            xs,ys = j,i
            qx = deque([])
            qx.append(xs)
            qy = deque([])
            qy.append(ys)
            reach = [[0 for _1 in range(w+2)] for _2 in range(h+2)]
            reach[ys][xs] = 1
            while qx:
                x = qx.popleft()
                y = qy.popleft()

                if s[y-1][x] == "." and reach[y-1][x] == 0:
                    qx.append(x)
                    qy.append(y-1)
                    reach[y-1][x] = reach[y][x] + 1
                if s[y+1][x] == "." and reach[y+1][x] == 0:
                    qx.append(x)
                    qy.append(y+1)
                    reach[y+1][x] = reach[y][x] + 1
                if s[y][x-1] == "." and reach[y][x-1] == 0:
                    qx.append(x-1)
                    qy.append(y)
                    reach[y][x-1] = reach[y][x] + 1
                if s[y][x+1] == "." and reach[y][x+1] == 0:
                    qx.append(x+1)
                    qy.append(y)
                    reach[y][x+1] = reach[y][x] + 1
            m = 1
            for k in range(h+2):
                m = max(m,max(reach[k][:])-1)
            ans = max(ans,m)
print(ans)

Solution (Python):
from scipy.sparse import*
_,*s=open(0)
M=999
*g,=eval('[0]*M,'*M)
i=0
for t in s:
 i+=1;j=0
 for u in t:k=i*20+j;g[k][k+20]=u>'
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<M])))

Solution (Python):
from scipy.sparse import*
_,*s=open(0)
M=999
*g,=eval('[0]*M,'*M)
i=0
for t in s:
 i+=1;j=0
 for u in t:k=i*20+j;g[k][k+1]=u>'
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<M])))

Solution (Python):
from scipy.sparse import*
_,*s=open(0)
M=999
*g,=eval('[0]*M,'*M)
i=0
for t in s:
 i+=1;j=0
 for u in t:k=~-i*20+j;g[k][k+1]=u>'
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<M])))

Solution (Python):
from scipy.sparse import*
_,*s=open(0)
M=999
*g,=eval('[0]*M,'*M)
i=0
for t in s:
 j=0
 for u in t:k=i*20+j;g[k][k+1]=u>'
 i+=1
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<M])))

Solution (Python):
from scipy.sparse import*
_,*s=open(0)
*g,=eval('[0]*500,'*500)
i=-1
for t in s:
 i+=1;j=0
 for u in t:k=i*20+j;g[k][k+1]=u>'
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<999])))

Solution (Python):
from scipy.sparse import*
_,*s=open(0)
r=s+["
*g,=eval("[0]*500,"*500)
i=-1
for t in s:
 i+=1;j=0
 for u in t:k=i*20+j;g[k][k+1]=u>'
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<999])))

Solution (Python):

from scipy.sparse.csgraph import floyd_warshall
INF = float("inf")

h, w = map(int, input().split())
M = [input() for _ in [0]*h]
E = [[0]*h*w for _ in [0]*h*w]
D = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def point(x, y):
    return w * x + y

for i in range(h):
    for j in range(w):
        if M[i][j] == ".":
            for x, y in D:
                I, J = i + x, j + y
                if w > J >= 0 <= I < h and M[I][J] == ".":
                    E[point(i, j)][point(I, J)] = 1

a = floyd_warshall(E)
print(int(a[a != INF].max()))

Solution (Python):

import queue
H,W=map(int,input().split())
P=[0 for i in range(H)]
for i in range(H):
    P[i]=str(input())
ans=0
for i in range(H*W):
    s=(i//W,i%W)
    if P[s[0]][s[1]]=="
        continue
    st=queue.Queue()
    st.put(s)
    log=[[-1 for i in range(W)] for j in range(H)]
    log[s[0]][s[1]]=0
    while not st.empty():
        y,x=st.get()
        for z,w in [(y+1,x),(y-1,x),(y,x+1),(y,x-1)]:
            if 0>z or 0>w:
                continue
            elif z>=H or w>=W:
                continue
            elif P[z][w]=="." and log[z][w]==-1:
                st.put((z,w))
                log[z][w]=log[y][x]+1
                ans=max(ans,log[z][w])
print(ans)

Solution (Python):

from collections import deque
h, w = map(int, input().split())
s = []
a = 0
for _ in range(h):
    s.append(list(input()))
mx = [1,-1,0,0]
my = [0,0,1,-1]
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            d = [[-1 for a in range(w)] for b in range(h)]
            d[i][j] = 0
            q = deque([(j,i)])
            while q:
                x, y = q.popleft()
                for c in range(4):
                    new_x = x + mx[c]
                    new_y = y + my[c]
                    if 0<=new_x<=w-1 and 0<=new_y<=h-1 and s[new_y][new_x] != "
                        q.append((new_x,new_y))
                        d[new_y][new_x] = d[y][x] + 1
                        a = max(a, d[new_y][new_x])
                        
print(a)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
S = [input() for i in range(H)]
l = []
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            l.append((i, j))

m = -1
N = len(l)
for i in range(N-1):
    for j in range(i+1, N):
        start = l[i]
        goal = l[j]
        visited = [[-1]*W for i in range(H)]
        d = deque()
        d.appendleft(start)
        visited[start[0]][start[1]] = 0
        while d:
            now = d.pop()
            for direction in directions:
                next = (now[0]+direction[0], now[1]+direction[1])
                if not (next[0] in range(H) and next[1] in range(W)):
                    continue
                if visited[next[0]][next[1]] != -1:
                    continue
                if S[next[0]][next[1]] == '.':
                    visited[next[0]][next[1]] = visited[now[0]][now[1]] + 1
                    d.appendleft(next)
                if next == goal:
                    m = max(visited[goal[0]][goal[1]], m)
                    d = deque()

print(m)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0
maze = []
for i in range(h):
    maze.append(list(input()))
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            d = [[-1 for a in range(w)] for b in range(h)]
            dq = deque([(j,i)])
            d[i][j] = 0
            while dq:
                x,y = dq.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "
                        dq.append((nx,ny))
                        d[ny][nx] = d[y][x]+1
                        ans = max(ans,d[ny][nx])
print(ans)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0
maze = []
for i in range(h):
    maze.append(list(input()))
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            d = [[-1 for a in range(w)] for b in range(h)]
            dq = deque([(j,i)])
            d[i][j] = 0
            while dq:
                x,y = dq.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "
                        dq.append((nx,ny))
                        d[ny][nx] = d[y][x]+1
                        ans = max(ans,d[ny][nx])
print(ans)

Solution (Python):
from collections import deque
import copy
h,w = map(int,input().split())
origin = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0
for i in range(h):
    origin.append(list(input()))
for i in range(h):
    if "
        break
else:
    print(h+w-2)
    exit()
for i in range(h):
    for j in range(w):
        if origin[i][j] == ".":
            d = [[0 for j in range(w)] for i in range(h)]
            maze = copy.deepcopy(origin)
            dq = deque([(j,i)])
            while dq:
                x,y = dq.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "
                        dq.append((nx,ny))
                        d[ny][nx] = d[y][x]+1
                        ans = max(ans,d[ny][nx])
                maze[y][x] = "
            
print(ans)

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

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

from collections import deque

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

for sx in range(0,W):
    for sy in range(0,H):
        if M[sy][sx]=="
            continue
        d = [[10**4] * W for i in range(H)]
        que = deque([])
        que.append((sy, sx))
        d[sy][sx] = 0
        while que:
            p = que.popleft()
            for i in range(4):
                ny = p[0] + dy[i]
                nx = p[1] + dx[i]
                if (0<=nx<W)and(0<=ny<H)and(M[ny][nx]!="
                    que.append((ny, nx))
                    d[ny][nx] = d[p[0]][p[1]] + 1
                    out = max(d[ny][nx],out)
print(out)

Solution (Python):
from collections import deque

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

dir = [[1,0], [-1,0], [0,1], [0,-1]]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "
        ls = deque([[i, j]])
        dp = [[float("inf") for k in range(W)] for l in range(H)]
        dp[i][j] = 0
        while len(ls) > 0:
            x, y = ls.popleft()

            for dx, dy in dir:
                if x+dx < 0 or H-1 < x+dx: continue
                if y+dy < 0 or W-1 < y+dy: continue
                if S[x+dx][y+dy] == "
                if dp[x+dx][y+dy] > dp[x][y] + 1:
                    dp[x+dx][y+dy] = dp[x][y] + 1
                    ls.append([x+dx,y+dy])

        for h in range(H):
            for w in range(W):
                if dp[h][w] == float("inf"): continue
                ans = max(ans, dp[h][w])

print(ans)

Solution (Python):
from collections import *

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

ans = 0
INF = float('inf')

for i in range(H):
    for j in range(W):
        if S[i][j] == '

        dist = [[INF for i in range(W)] for j in range(H)]
        visited = [[False for i in range(W)] for j in range(H)]

        q = deque()
        q.append((i, j, 0))
        
        while q:
            i, j, c = q.popleft()

            if visited[i][j]: continue
            visited[i][j] = True
            dist[i][j] = c
            ans = max(ans, c)
            for a, b in [(1,0), (-1,0), (0,1), (0,-1)]:
                x = i+a
                y = j+b

                if 0 <= x < H and 0 <= y < W and S[x][y] == '.' and not visited[x][y]:
                    q.append((x, y, c+1))

print(ans)

Solution (Python):

import sys
input = lambda: sys.stdin.readline().strip()

h, w = [int(x) for x in input().split()]
g = [input() for _ in range(h)]
ans = 0
for si in range(h):
    for sj in range(w):
        if g[si][sj] != '
            d = [[-1 for j in range(w)] for i in range(h)]
            d[si][sj] = 0
            q = [(si, sj)]
            for i, j in q:
                ans = max(ans, d[i][j])
                for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    ni, nj = i + di, j + dj
                    if 0 <= ni < h and 0 <= nj < w and g[ni][nj] != '
                        d[ni][nj] = d[i][j] + 1
                        q.append((ni, nj))
print(ans)