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 copy import deepcopy
from collections import deque
from itertools import product
import numpy as np
inputs = open(0).readlines()
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val
        
h, w = map(int, inputs[0].split())
grid_origin = Grid(inputs[1:], function=lambda x: int(x == '.'))

def bfs(root):
    x, y, _ = root
    grid[y, x] = 0
    queue = deque([root])
    while queue:
        x, y, d = queue.popleft()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            if grid.is_valid_xy(x+dx, y+dy) and grid[y+dy, x+dx]:
                queue.append((x+dx, y+dy, d+1))
                grid[y+dy, x+dx] = 0
    return d
    
ans = 0
for i, j in product(range(h), range(w)):
    if grid_origin[i, j]:
        grid = deepcopy(grid_origin)
        ans = max(ans, bfs((j, i, 0)))
print(ans)

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

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



            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '
                    
                    queue.insert(0, (ny, nx))  
                    dist[ny][nx] = dist[y][x] + 1
                    
                    if dist_max < dist[ny][nx]:
                        dist_max = dist[ny][nx]
        return dist_max


    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]

    ans = bfs(maze, R, C, sy, sx, gy, gx)
    return ans

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


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

Solution (Python):

from collections import deque
def bfs(i,j):
    q=deque()
    q.append((i,j))
    log=[[-1]*w for i in range(h)]
    log[i][j]=0
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    long=0
    while q:
        
        p=q.popleft()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]

            if not(0<=nx<h and 0<=ny<w):continue
            if maze[nx][ny]=='
            if log[nx][ny]!=-1:continue
            log[nx][ny]=log[p[0]][p[1]]+1
            q.append((nx,ny))
            if long<=log[nx][ny]:long=log[nx][ny]
    return long

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

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

Solution (Python):
H,W = map(int, input().split())
S = [["
S += [["
S.append(["

DX = [0,0,-1,1]
DY = [-1,1,0,0]

from collections import deque

def bfs(y,x):
    dist = [[-1] * (W + 2) for _ in range(H + 2)] 
    
    que = deque([(y, x)])
    dist[y][x] = 0
    while que:
        y, x = que.popleft()
        d = dist[y][x]
        for dy,dx in zip(DY,DX):
            ny, nx = y + dy, x + dx
            if S[ny][nx] == "
            if dist[ny][nx] < 0:
                dist[ny][nx] = d + 1
                que.append((ny,nx))
    
    ans = -1
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            ans = max(ans, dist[i][j])
    return ans

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

print(ans)

Solution (Python):

h,w = list(map(int,input().split()))
inf=float("inf")
s = [[-1]*(w+2)] + [[-1] + [inf if i=="." else -1 for i in input()] + [-1] for _ in range(h)] + [[-1]*(w+2)]

from copy import deepcopy
from collections import deque

ret = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        temp_s = deepcopy(s)
        if temp_s[i][j]!=-1:
            temp_s[i][j]=-1
            stack_deque = deque([(i,j,0)])
        else:
            stack_deque = []
        max_v=0
        while len(stack_deque)>0:
            hi,wj,v = stack_deque.popleft()
            v+=1
            if temp_s[hi][wj-1]!=-1:
                temp_s[hi][wj-1]=-1
                stack_deque.append([hi,wj-1,v])
                max_v=max(max_v,v)
            if temp_s[hi][wj+1]!=-1:
                temp_s[hi][wj+1]=-1
                stack_deque.append([hi,wj+1,v])
                max_v=max(max_v,v)
            if temp_s[hi-1][wj]!=-1:
                temp_s[hi-1][wj]=-1
                stack_deque.append([hi-1,wj,v])
                max_v=max(max_v,v)
            if temp_s[hi+1][wj]!=-1:
                temp_s[hi+1][wj]=-1
                stack_deque.append([hi+1,wj,v])
                max_v=max(max_v,v)
        ret=max(ret,max_v)
print(ret)

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


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    ans = 0
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "
                continue
            now_grid = deepcopy(grid)
            answer = [[float("inf") for _ in range(w)] for _ in range(h)]
            next = deque([[i, j]])
            answer[i][j] = 0
            while next:
                y, x = next.popleft()
                if now_grid[y][x] == ".":
                    now_grid[y][x] = "
                    for dx, dy in d:
                        if 0 <= x + dx < w and 0 <= y + dy < h and now_grid[y + dy][x + dx] == ".":
                            answer[y + dy][x + dx] = min(answer[y][x] + 1, answer[y + dy][x + dx])
                            next.append([y + dy, x + dx])
            for k in range(h):
                for l in range(w):
                    if grid[k][l] == "
                        continue
                    ans = max(ans, answer[k][l])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def bfs(sx, sy, maze):
    INF = 100000000
    visit = [[-INF for i in range(w + 2)] for j in range(h + 2)]
    queue = deque([])
    queue.append([sx, sy])
    visit[sx][sy] = 0
    res = 0
    while len(queue):
        x, y = queue.popleft()
        for k in range(0, 4):
            nx, ny = x + dx[k], y + dy[k]
            if maze[nx][ny] != '
                queue.append([nx, ny])
                visit[nx][ny] = visit[x][y] + 1
                res = max(res, visit[nx][ny])
    return res


h, w = map(int, input().split())
maze = [list("
for _ in range(h):
    maze.append(["
maze += [list("

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

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

Solution (Python):
from copy import deepcopy
from collections import deque
from itertools import product
import numpy as np
inputs = open(0).readlines()
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, rows in zip(range(h), grid):
            for j, val in zip(range(w), rows):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, rows)) for rows in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val
h, w = map(int, inputs[0].split())
grid_origin = Grid(inputs[1:], function=lambda x: int(x == '.'))

def bfs(root):
    queue = deque([root])
    while queue:
        x, y, d = queue.popleft()
        d += 1
        grid[y, x] = 0
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            if grid.is_valid_xy(x+dx, y+dy) and grid[y+dy, x+dx]:
                queue.append((x+dx, y+dy, d))
                grid[y+dy, x+dx] = 0
    return d-1
    
ans = 0
for i, j in product(range(h), range(w)):
    if grid_origin[i, j]:
        grid = deepcopy(grid_origin)
        ans = max(ans, bfs((j, i, 0)))
print(ans)

Solution (Python):
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def bfs(sy, sx):
    dist = [[-INF] * W for _ in range(H)]
    dist[sy][sx] = 0
    que = deque([(sy, sx)])
    popleft = que.popleft; append = que.append
    while que:
        y, x = popleft()
        cur = dist[y][x]
        for dy, dx in zip([0, 1, 0, -1], [1, 0, -1, 0]):            
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and \
                    grid[ny][nx] != '
                dist[ny][nx] = cur + 1
                append((ny, nx))
    ret = max(max(x for x in di)for di in dist)
    return ret

INF = 10 ** 3
H, W = lr()
grid = [sr() for _ in range(H)]
answer = max(max(bfs(i, j) if grid[i][j] == '.' else 0 for j in range(W)) for i in range(H))
print(answer)

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

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

        
        record = [[[h, w]]]
        count = 0
        while True:
            if record[count] == []:
                break
            li = []
            for p in record[count]:
                h = p[0]
                w = p[1]
                next_to_p = []
                if h > 0 and S[h - 1][w] == "." and [h - 1, w] not in record[count - 1] + li:
                    next_to_p.append([h - 1, w])
                if w > 0 and S[h][w - 1] == "." and [h, w - 1] not in record[count - 1] + li:
                    next_to_p.append([h, w - 1])
                if h < H - 1 and S[h + 1][w] == "." and [h + 1, w] not in record[count - 1] + li:
                    next_to_p.append([h + 1, w])
                if w < W - 1 and S[h][w + 1] == "." and [h, w + 1] not in record[count - 1] + li:
                    next_to_p.append([h, w + 1])
                li = li + next_to_p
            record.append(li)
            count += 1

        ans = max(ans, count - 1)

print(ans)

Solution (Python):





def search(x, y, r):
    
    if x < H - 1 and S[x + 1][y] == "." and r[x + 1][y] == -1:
        r[x + 1][y] = r[x][y] + 1
        search(x + 1, y, r)
    
    if y < W - 1 and S[x][y + 1] == "." and r[x][y + 1] == -1:
        r[x][y + 1] = r[x][y] + 1
        search(x, y + 1, r)
    
    if 0 < x and S[x - 1][y] == "." and r[x - 1][y] == -1:
        r[x - 1][y] = r[x][y] + 1
        search(x - 1, y, r)
    
    if 0 < y and S[x][y - 1] and r[x][y - 1] == -1:
        r[x][y - 1] = r[x][y] + 1
        search(x, y - 1, r)


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

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

        
        record = [[[h, w]]]
        count = 0
        while True:
            if record[count] == []:
                break
            li = []
            for p in record[count]:
                h = p[0]
                w = p[1]
                next_to_p = []
                if h > 0 and S[h - 1][w] == "." and [h - 1, w] not in record[count - 1] + li:
                    next_to_p.append([h - 1, w])
                if w > 0 and S[h][w - 1] == "." and [h, w - 1] not in record[count - 1] + li:
                    next_to_p.append([h, w - 1])
                if h < H - 1 and S[h + 1][w] == "." and [h + 1, w] not in record[count - 1] + li:
                    next_to_p.append([h + 1, w])
                if w < W - 1 and S[h][w + 1] == "." and [h, w + 1] not in record[count - 1] + li:
                    next_to_p.append([h, w + 1])
                li = li + next_to_p
            record.append(li)
            count += 1

        ans = max(ans, count - 1)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
 
def warshal_floyd(d, n):
  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())
m = [str(input()) for _ in range(h)]
d = [[float('inf') for i in range(h*w)] for j in range(h*w)]
for i in range(h*w):
  d[i][i] = 0
  
for i in range(h*w):
  for j in range(h*w):
    py, px = i//w, i%w
    qy, qx = j//w, j%w
    if (px == qx and abs(py-qy) == 1) or (py == qy and abs(px-qx) == 1):
      pm = m[py][px]
      qm = m[qy][qx]
      if qm == '.' and pm == '.':
        d[i][j] = 1
        

d = warshal_floyd(d, h*w)

 
ans = 0
for i in range(h*w):
  for j in range(h*w):
    if d[i][j] != float('inf'):
      ans = max(ans, d[i][j])
print(ans)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
MAZE = ['
for _ in range(h):
    MAZE.append("
else:
    MAZE.append('

INF = 10**3
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def bfs(init_x, init_y):
    dist = [[INF]*(w+2) for _ in range(h+2)]
    q = deque([(init_x, init_y)])
    dist[init_x][init_y] = 0
    MAX = 0
    while q:
        x, y = q.popleft()
        for i, j in directions:
            if MAZE[x+i][y+j] == '
                continue
            if dist[x+i][y+j] <= dist[x][y]+1:
                continue
            dist[x+i][y+j] = dist[x][y]+1
            q.append((x+i, y+j))

        MAX = max(MAX, dist[x][y])
    return MAX


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if MAZE[i][j] == '
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Solution (Python):
from queue import Queue
h, w = map(int, input().split())
MAZE = ['
for _ in range(h):
    MAZE.append("
else:
    MAZE.append('

INF = 10**3
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def bfs(init_x, init_y):
    dist = [[INF]*(w+2) for _ in range(h+2)]
    q = Queue()
    q.put((init_x, init_y))
    dist[init_x][init_y] = 0
    MAX = 0
    while not q.empty():
        x, y = q.get()
        for i, j in directions:
            if MAZE[x+i][y+j] == '
                continue
            if dist[x+i][y+j] <= dist[x][y]+1:
                continue
            dist[x+i][y+j] = dist[x][y]+1
            q.put((x+i, y+j))
        MAX = max(MAX, dist[x][y])
    return MAX


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if MAZE[i][j] == '
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Solution (Python):


from queue import Queue
h, w = map(int, input().split())
MAZE = ['
for _ in range(h):
    MAZE.append("
else:
    MAZE.append('

INF = 10**3
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def bfs(init_x, init_y):
    dp = [[INF]*(w+2) for _ in range(h+2)]
    resisterd = [[0]*(w+2) for _ in range(h+2)]
    q = Queue()
    q.put((init_x, init_y))
    dp[init_x][init_y] = 0
    MAX = 0
    while not q.empty():
        x, y = q.get()
        for i, j in directions:
            if MAZE[x+i][y+j] == '
                continue
            if resisterd[x+i][y+j]:
                continue
            resisterd[x+i][y+j] = 1
            q.put((x+i, y+j))
        dp[x][y] = min(dp[x][y], min(dp[x+v][y+w]+1 for v, w in directions))
        MAX = max(MAX, dp[x][y])
    return MAX


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if MAZE[i][j] == '
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Solution (Python):
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def bfs(sy, sx):
    dist = [[-INF] * W for _ in range(H)]
    dist[sy][sx] = 0
    que = deque([(sy, sx)])
    popleft = que.popleft; append = que.append
    while que:
        y, x = popleft()
        cur = dist[y][x]
        for dy, dx in zip([0, 1, 0, -1], [1, 0, -1, 0]):            
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and \
                    grid[ny][nx] != '
                dist[ny][nx] = cur + 1
                append((ny, nx))
    ret = max(max(x for x in di)for di in dist)
    return ret

INF = 10 ** 3
H, W = lr()
grid = [sr() for _ in range(H)]
answer = max(max(bfs(i, j) if grid[i][j] == '.' else 0 for j in range(W)) for i in range(H))
print(answer)

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]


'''
N = ii()
A = li()
right = 0
flag = [0]*(10**5+1)
ans = 0

for left in range(N):
    
    while right < N and flag[A[right]]!=1:
        flag[A[right]] = 1
        right += 1
    
    ans = max(ans, right-left)
    if left == right:
        right += 1
    else:
        flag[A[left]] = 0

print(ans)
'''

from collections import deque

H, W = mi()
S = [input() for i in range(H)]

d = deque()
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
ans = 0
flag = dp2(0, W, H)

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            flag = dp2(0, W, H)
            d.append([i, j, 0])
            flag[i][j] = 1
            while d!=deque():
                a = d.popleft()
                for k in range(4):
                    x, y = a[0]+dy[k], a[1]+dx[k]
                    if 0 <= x < H and 0 <= y < W:
                        if S[x][y] == '.' and flag[x][y] != 1:
                            d.append([x, y, a[2]+1])
                            flag[x][y] = 1
                            ans = max(ans, a[2]+1)

print(ans)

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


from collections import deque

dj = [1, 0, -1, 0]
di = [0, 1, 0, -1]

sum_sharp = sum([A[i].count('

fin_d_max = 1

for s_i in range(H):
    for s_j in range(W):
        d_max = 0
        q_i = deque()
        q_j = deque()
        D = [[-1]*W for i in range(H)]
        flag = 1

        if A[s_i][s_j] == '.':
            D[s_i][s_j] = 0
            q_i.append(s_i)
            q_j.append(s_j)
            while len(q_i)!=0:
                i = q_i.popleft()
                j = q_j.popleft()
                for x in range(4):
                    ni = i+di[x]
                    nj = j+dj[x]
                    if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '
                        continue
                    else:
                        D[ni][nj] = D[i][j]+1
                        d_max = max(d_max, D[ni][nj])
                        q_i.append(ni)
                        q_j.append(nj)
        fin_d_max = max(fin_d_max, d_max)
                
print(fin_d_max)

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]


'''
N = ii()
A = li()
right = 0
flag = [0]*(10**5+1)
ans = 0

for left in range(N):
    
    while right < N and flag[A[right]]!=1:
        flag[A[right]] = 1
        right += 1
    
    ans = max(ans, right-left)
    if left == right:
        right += 1
    else:
        flag[A[left]] = 0

print(ans)
'''

from collections import deque

H, W = mi()
S = [input() for i in range(H)]

d = deque()
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
ans = 0
flag = dp2(0, W, H)

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            flag = dp2(0, W, H)
            d.append([i, j, 0])
            flag[i][j] = 1
            while len(d)!=0:
                a = d.popleft()
                for k in range(4):
                    x, y = a[0]+dy[k], a[1]+dx[k]
                    if 0 <= x < H and 0 <= y < W:
                        if S[x][y] == '.' and flag[x][y] != 1:
                            d.append([x, y, a[2]+1])
                            flag[x][y] = 1
                            ans = max(ans, a[2]+1)

print(ans)

Solution (Python):
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
grid = [sr() for _ in range(H)]

def bfs(sy, sx):
    d = [[float('inf')] * W for _ in range(H)]
    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    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 <= ny < H and 0 <= nx < W and \
                    grid[ny][nx] != '
                d[ny][nx] = d[p[0]][p[1]] + 1
                que.append((ny, nx))
    max = 0
    for row in d:
        for r in row:
            if r != float('inf') and r > max:
                max = r
    return max

answer = 0    
for i in range(H):
    for j in range(W):
        if grid[i][j] == '
            continue
        result = bfs(i, j)
        if result > answer:
            answer = result

print(answer)

Solution (Python):
from collections import deque

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

def bfs(maze,visited,sx,sy):
    stack = deque([[sy,sx]])
    visited[sy][sx] = 0
    while stack:
        y,x = stack.pop()
        count = visited[y][x]
        
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y,new_x = y+j,x+k
            if new_x < 0 or new_x >= W or new_y < 0 or new_y >= H:
                continue
            
            elif maze[new_y][new_x] != "
                visited[new_y][new_x] = count+1
                stack.appendleft([new_y, new_x])
    return count

inf = float('inf')

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            visited = [[inf]*W for _ in range(H)]
            answer = max(answer,bfs(maze,visited,j,i))
print(answer)

Solution (Python):
def gridbfs(grid,sy,sx):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = [(sy,sx)]
    d = 1

    while q:
        qq = []
        for y,x in q:
            for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
                yy,xx = y+dy, x+dx
                if not (0 <= yy < gridy and 0 <= xx < gridx):
                    continue
                if grid[yy][xx] == '
                    continue
                if dist[yy][xx] != INF:
                    continue
                dist[yy][xx] = d
                qq.append((yy,xx))
        q = qq
        d += 1

    return dist

h,w = map(int,input().split())
s = [input() for i in range(h)]
c = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            continue
        d_list = gridbfs(s,i,j)
        for k in range(h):
            for l in range(w):
                if d_list[k][l] != 10**18:
                    c = max(c,d_list[k][l])
print(c)

Solution (Python):

from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,raw_input().split())
s=[raw_input() for i in range(h)]
n=w*h
e=[[0]*n for i in range(n)]
d=[(1,0),(0,1),(-1,0),(0,-1)]
for i in range(h):
 for j in range(w):
  if s[i][j]=='.':
   for x,y in d:
    ni,nj=i+x,j+y
    if 0<=ni<h and 0<=nj<w and s[ni][nj]=='.':
     e[w*i+j][w*ni+nj]=1
res=floyd_warshall(e)
INF=float("inf")
print int(max(max(a if a!=INF else 0 for a in a) for a in res))

Solution (Python):

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

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

    
    def bfs(i, j):
        dxy = [[0,1],[0,-1],[1,0],[-1,0]]
        q = deque([[i,j]])
        d[i][j] = 0
        while q:
            x, y = q.popleft()
            for dx, dy in dxy:
                nx, ny = x+dx, y+dy
                if 0<=nx<=h-1 and 0<=ny<=w-1:
                    if d[nx][ny]=='.':
                        d[nx][ny] = d[x][y] + 1
                        q.append([nx,ny])
        res = 0
        for a in range(h):
            for b in range(w):
                if d[a][b] != '
                    res = max(res, d[a][b])
        return res

    res = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                d = copy.deepcopy(s)
                res = max(res, bfs(i, j))
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

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

    
    def bfs(i, j):
        dxy = [[0,1],[0,-1],[1,0],[-1,0]]
        q = deque([[i,j]])
        d[i][j] = 0
        while q:
            x, y = q.popleft()
            for dx, dy in dxy:
                nx, ny = x+dx, y+dy
                if 0<=nx<=h-1 and 0<=ny<=w-1:
                    if d[nx][ny]=='.':
                        d[nx][ny] = d[x][y] + 1
                        q.append([nx,ny])
        res = 0
        for a in range(h):
            for b in range(w):
                if d[a][b] != '
                    res = max(res, d[a][b])
        return res

    res = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                d = copy.deepcopy(s)
                res = max(res, bfs(i, j))
    print(res)

if __name__ == '__main__':
    main()