Problem:
 Score : 400 points    Problem Statement Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i -th row from the top and the j -th column is a "wall" square if S_{ij} is # , and a "road" square if S_{ij} is . .  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.      Constraints  1 \leq H,W \leq 20  S_{ij} is . or # .  S contains at least two occurrences of . .  Any road square can be reached from any road square in zero or more moves.         Input Input is given from Standard Input in the following format:  H  W  S_{11} ... S_{1W}  :  S_{H1} ... S_{HW}       Output Print the maximum possible number of moves Aoki has to make.        Sample Input 1 3 3
...
...
...      Sample Output 1 4  If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.       Sample Input 2 3 5
...#.
.#.#.
.#...      Sample Output 2 10  If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.

Solution (Python):
from collections import deque


def bfs(maze, x, y):
    m = [1, 0, -1, 0]
    n = [0, 1, 0, -1]
    queue = deque([[x, y]])
    dist = [[-1] * (w + 2) for _ in range(h + 2)]
    dist[x][y] = 0

    while queue:
        sx, sy = queue.popleft()

        for dx, dy in zip(m, n):
            nx = sx + dx
            ny = sy + dy
            if maze[nx][ny] != '
                queue.append([nx, ny])
                dist[nx][ny] = dist[sx][sy] + 1

    return max(max(x) for x in dist)


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

maze = [['
for i in range(h):
    maze.append(['

maze.append(['

ans = 0
for sy in range(1, w + 1):
    for sx in range(1, h + 1):
        if maze[sx][sy] != '
            ans = max(ans, bfs(maze, sx, sy))

print(ans)

Solution (Python):
import queue


class Solution:

    def solve(self, H: int, W: int, S) -> int:

        def onEdge(pos):
            i = pos[0]
            j = pos[1]
            if 0 < i and i < H - 1 and 0 < j and j < W - 1:
                return False
            else:
                return True

        def bfs(start):
            INF = H*W+1
            dist = {}
            for i in range(H):
                for j in range(W):
                    dist[(i, j)] = INF

            max_dist = 0

            dist[start] = 0
            nexts = queue.Queue()
            nexts.put(start)

            while not nexts.empty():
                __next = nexts.get()

                
                max_dist = max(dist[__next], max_dist)

                for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    h = __next[0] + delta[0]
                    w = __next[1] + delta[1]

                    if h < 0 or h > H - 1 or w < 0 or w > W - 1:
                        continue

                    if S[h][w] != "
                        if dist[(h, w)] == INF:
                            nexts.put((h, w))
                            dist[(h, w)] = dist[__next] + 1

            return max_dist

        ans = 0
        for i in range(H):
            for j in range(W):

                
                
                

                
                if S[i][j] == "
                    continue

                ans = max(bfs((i, j)), ans)

        return ans


if __name__ == '__main__':

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

    
    solution = Solution()
    print(solution.solve(H, W, S))

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


def bfs(maze, sx, sy):
    H = len(maze)
    W = len(maze[0])

    dist = np.zeros((H, W), dtype=int)
    dist[:, :] = -1

    q = deque([(sx, sy)])
    dist[sx, sy] = 0

    while q:
        x, y = q.popleft()
        d = dist[x, y]
        for dx, dy in [[1,0],[0,1],[-1,0],[0,-1]]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny]=="." and dist[nx, ny] == -1:
                q.append((nx, ny))
                dist[nx, ny] = d+1
    return dist.max()


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

    maze = [input() for _ in range(H)]

    ans = 0
    for sx, sy in [(x, y) for x in range(H) for y in range(W) if maze[x][y] == "."]:
        ans = max(ans, bfs(maze, sx, sy))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
h,w=map(int,input().split())
h += 2
w += 2
s="
for _ in range(h-2):
    s += "
s += "
def bfs(start):
    que=deque([start])
    INF=10**9
    dis=[INF]*(w*h)
    dis[start]=0
    move=(1,-1,w,-w)
    while que:
        v=que.popleft()
        for i in move:
            n=v+i
            if s[n]=="
                continue
            dv=dis[v]
            dn=dv+1
            if dis[n] <= dv+1:
                continue
            dis[n]=dn
            que.append(n)
    return max(i for i in dis if i<INF)
ans=max(bfs(v) for v in range(h*w) if s[v] != "
print(ans)

Solution (Python):
from collections import deque
import copy


def bfs(start, s):
    h = len(s)
    w = len(s[0])
    distance = 0
    maze = [[-1] * w for _ in range(h)]
    maze[start[0]][start[1]] = 0
    s[start[0]][start[1]] = "
    drcs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    q = deque()
    q.append(start)
    while(q):
        cr, cc = q.popleft()
        for dr, dc in drcs:
            nr, nc = cr + dr, cc + dc
            if nr < 0 or nc < 0 or nr >= h or nc >= w:
                continue
            if s[nr][nc] == ".":
                q.append([nr, nc])
                s[nr][nc] = "
                maze[nr][nc] = maze[cr][cc] + 1
                if maze[nr][nc] > distance:
                    distance = maze[nr][nc]
                    goal = [nr, nc]
    return goal, distance
    


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    for r in range(h):
        if "." in s[r]:
            start = [r, s[r].index(".")]
    goal, distance = bfs(start, copy.deepcopy(s))
    _, res = bfs(goal, s)
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
S = [list(input()) for i in range(h)]

ans = 0

for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            d = [[-1 for i in range(w)] for j in range(h)]
            que = []
            que.append([i, j])
            d[i][j] = 0

            while len(que) != 0:
                p = que.pop(0)
                for dx, dy in zip((1, 0, -1, 0), (0, 1, 0, -1)):
                    nx = p[0] + dx
                    ny = p[1] + dy
                    if 0 <= nx < h and 0 <= ny < w and S[nx][ny] != '
                        que.append([nx, ny])
                        d[nx][ny] = d[p[0]][p[1]] + 1

            for _ in d:
                ans = max(ans, max(_))

print(ans)

Solution (Python):
h, w = map(int, input().split())
field = [list(input()) for _ in range(h)]

from collections import deque

def bfs(sx, sy):  
    
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    
    d = [[-1]*w for _ in range(h)]
    d[sx][sy] = 0  
    
    
    que = deque([])
    que.append([sx, sy])  
    
    while que:
        
        x, y = que.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            
            
            if (0 <= nx < h) and (0 <= ny < w) and \
                (field[nx][ny] != '
                
                d[nx][ny] = d[x][y] + 1
                
                que.append([nx, ny])
                
    return d
  
  
import itertools

ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '
            continue
        d = bfs(i, j)
        ans = max(ans, max(itertools.chain(*d)))
        
print(ans)

Solution (Python):
import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='
        continue
      q.append((i,j))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      visited[i][j]=0
      _ans=0
      while q:
        y,x=q.popleft()

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='
            continue
          if visited[ny][nx]!=-1:
            continue
          _ans=visited[y][x]+1
          visited[ny][nx]=_ans
          q.append((ny,nx))
      ans=max(ans,_ans)
  return ans


print(main())

Solution (Python):
from collections import deque

def bfs():
    d = [[-1] * C for i in range(R)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()

        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            if 0<=nx<C and 0<=ny<R and maze[ny][nx] != '
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
    
    Max_d = 0
    for d1 in d:
        Max_d = max(Max_d, max(d1))

    return Max_d



R, C = map(int, input().split())
maze = [list(input()) for _ in range(R)]
ans = 0

for i in range(R):
    for j in range(C):
        if maze[i][j] == ".":
            sy = i
            sx = j
            ans = max(ans, bfs())

print(ans)

Solution (Python):
from collections import deque
inf = 401
H,W=map(int,input().split(' '))
maze=[list(input()) for i in range(H)]
ans = 0
def short_long(a,b):
    q=deque()
    q.append((a,b))
    d=[[inf for i in range(W)] for j in range(H)]
    d[a][b]=0
    tmp = 0
    while q:
        x,y=q.popleft()
        for i,j in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx,ny=x+i,y+j
            if 0<=nx<H and 0<=ny<W and maze[nx][ny]!='
                q.append((nx,ny))
                d[nx][ny]=d[x][y]+1
                tmp = max(d[nx][ny],tmp)
    return tmp
for i in range(H):
    for j in range(W):
        if maze[i][j] =='.':
            ans =max(ans,short_long(i,j))
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	H, W = MAP()
	maze = [list(input()) for _ in range(H)]
	dp = [[INF]*W*H for _ in range(W*H)]

	for i in range(H*W):
		for j in range(H*W):
			if maze[i//W][i%W] == "
				continue
			if maze[j//W][j%W] == "
				continue
			if i == j:
				dp[i][j] = 0
			if i + W == j:
				dp[i][j] = 1
			if i + 1 == j:
				if i%W == W - 1:
					continue
				dp[i][j] = 1
			if i - W == j:
				dp[i][j] = 1
			if i - 1 == j:
				if i%W == 0:
					continue
				dp[i][j] = 1

	for i in range(W*H):
	    for j, c2 in enumerate(row[i] for row in dp):
	           for k, (c1, c3) in enumerate(zip(dp[j], dp[i])):
	               if c1 > c2+c3:
	                   dp[j][k] = c2+c3

	ma = 0
	for i in range(len(dp)):
		for j in range(len(dp[i])):
			if dp[i][j] == INF:
				continue
			ma = ma if ma > dp[i][j] else dp[i][j]

	print(int(ma))

if __name__ == "__main__":
	main()

Solution (Python):
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0
for i in range(h):
    for j in range(w):
        if S[i][j]=="
            continue
        else:
            D=[[inf for _ in range(w)] for _ in range(h)]
            D[i][j]=0
            que=deque([(i,j)])
            while que:
                si,sj=que.popleft()
                for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                    if 0<=ni<h and 0<=nj<w and S[ni][nj]!="
                        if D[ni][nj]>D[si][sj]+1:
                            D[ni][nj]=D[si][sj]+1
                            ans=max(ans,D[si][sj]+1)
                            que.append((ni,nj))
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0
for i in range(h):
    for j in range(w):
        if S[i][j]=="
            continue
        else:
            dist=[[inf for _ in range(w)] for _ in range(h)]
            dist[i][j]=0
            que=deque([(i,j)])
            while que:
                si,sj=que.popleft()
                for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                    if 0<=ni<h and 0<=nj<w and S[ni][nj]!="
                        if dist[ni][nj]>dist[si][sj]+1:
                            dist[ni][nj]=dist[si][sj]+1
                            ans=max(ans,dist[si][sj]+1)
                            que.append((ni,nj))
print(ans)

Solution (Python):
from collections import deque

h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0

for i in range(h):
    for j in range(w):
        if S[i][j]=="
            continue
        else:
            dist=[[inf for _ in range(w)] for _ in range(h)]
            dist[i][j]=0
            que=deque([(i,j)])
            while que:
                si,sj=que.popleft()
                for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                    if 0<=ni<=h-1 and 0<=nj<=w-1 and S[ni][nj]!="
                        if dist[ni][nj]>dist[si][sj]+1:
                            dist[ni][nj]=dist[si][sj]+1
                            ans=max(ans,dist[si][sj]+1)
                            que.append((ni,nj))

print(ans)

Solution (Python):

import numpy as np
H, W = map(int, input().split())

M = np.ones((H+2,W+2),dtype=int)
for i in range(H):
  s = input()
  for j in range(W):
    M[i+1,j+1] = int(s[j] == "

ans = []
for i in range(1,H+1):
  for j in range(1,W+1):
    if M[i,j] == 1:
      continue
    Q = [(i,j)]
    dist = np.ones_like(M,dtype=int)*(-1)
    dist[i,j] = 0
    while len(Q) > 0:
      x,y = Q.pop(0)
      for k,l in [(1,0),(-1,0),(0,1),(0,-1),]:
        if M[x+k,y+l] == 0 and dist[x+k,y+l] == -1:
          Q.append((x+k,y+l))
          dist[x+k,y+l] = 1 + dist[x,y]
    ans.append(dist.max())
    
print(max(ans))

Solution (Python):
import queue
import copy

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

def dist(m, x1, y1):
    q = queue.Queue()
    q.put((x1, y1, 0))
    checked=[[False for _ in range(w)] for __ in range(h)]
    checked[y1][x1] = True
    while not q.empty():
        x, y, count = q.get()
        if x > 0 and m[y][x-1] == "." and checked[y][x-1] == False:
            checked[y][x-1] = True
            q.put((x-1, y, count+1))
        if y > 0 and m[y-1][x] == "." and checked[y-1][x] == False:
            checked[y-1][x] = True
            q.put((x, y-1, count+1))
        if x < w-1 and m[y][x+1] == "." and checked[y][x+1] == False:
            checked[y][x+1] = True
            q.put((x+1, y, count+1))
        if y < h-1 and m[y+1][x] == "." and checked[y+1][x] == False:
            checked[y+1][x] = True
            q.put((x, y+1, count+1))
    return count

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

Solution (Python):
h, w = [int(i) for i in input().split(' ')]

m = []
for i in range(h):
    m.append(input())

def valid(d):
    global h, w
    return 0 <= d[0] and d[0] < h and 0 <= d[1] and d[1] < w

def bfs(i, j):
    global m
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    index = 0
    q = [(i, j)]
    v = {(i, j): 0}
    while index < len(q):
        item = q[index]
        for d in dirs:
            new_item = (d[0] + item[0], d[1] + item[1])
            if valid(new_item) and m[new_item[0]][new_item[1]] == '.' and new_item not in v:
                v[new_item] = v[item] + 1
                q.append(new_item)
        index += 1
    return max(v.values())

answer = 0

for i in range(h):
    for j in range(w):
        if m[i][j] == '.':
            answer = max(answer, bfs(i, j))

print(answer)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
H+=2
W+=2
s="
for _ in range(H-2):
    s+="
s+="

answer=[]

for i in range(W*H):
    if s[i]=="
        continue
    dist=[-1]*(W*H)
    q=deque([i])
    dist[i]=0
    while len(q)>0:
        x=q.popleft()
        for j in [-1,1,W,-W]:
            if s[x+j]=="." and dist[x+j]==-1:
                q.append(x+j)
                dist[x+j]=1+dist[x]
    answer.append(max(dist))
print(max(answer))

Solution (Python):
from collections import deque

H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
direc = [(-1,0), (0,-1), (1,0), (0,1)]
ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '
            continue

        dist = [[-1] * W for i in range(H)]
        dist[y][x] = 0
        que = deque([[y,x]])
        while que:
            nh, nw = que.pop()
            for dh, dw in direc:
                if nh + dh < 0 or nh + dh >= H:
                    continue
                elif nw + dw < 0 or nw + dw >= W:
                    continue
                elif S[nh + dh][nw + dw] == '
                    continue
                elif dist[nh + dh][nw + dw] != -1:
                    continue
                else:
                    dist[nh + dh][nw + dw] = dist[nh][nw] + 1
                    que.appendleft([nh + dh, nw + dw])
        ans = max(ans, max([max(d) for d in dist]))
print(ans)

Solution (Python):
import collections

h, w = map(int, input().split())
s = [[""]*(w+2)]
for _ in range(h):
    _s = list(input())
    _s.insert(0, "")
    _s.append("")
    s.append(_s)
s.append([""]*(w+2))

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

ans = 0

for _h in range(1, h+1):
    for _w in range(1, w+1):
        if s[_h][_w] == "
            continue

        q = collections.deque([[_h, _w]])

        a = [[-1]*(w+2) for _ in range(h+2)]
        a[_h][_w] = 0

        while 0 < len(q):
            cx, cy = q.pop()
            for _dx, _dy in zip(dx, dy):
                x = cx + _dx
                y = cy + _dy

                if s[x][y] == "." and a[x][y] == -1:
                    a[x][y] = a[cx][cy] + 1
                    q.appendleft([x, y])

        for _a in a:
            ans = max(ans, max(_a))

print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
H += 2
W += 2
maze = '
for _ in range(H-2):
  maze += '
maze += '
 
def bfs(root):
  if maze[root] == '
    return -1
  dist = [-1] * (H*W)
  dist[root] = 0
  q = deque([root])
  while q:
    x = q.popleft()
    for d in [1, -1, W, -W]:
      if maze[x+d] == '.' and dist[x+d] == -1:
        q.append(x+d)
        dist[x+d] = dist[x] + 1
  return max(dist)
 
ans = max(bfs(i) for i in range(H*W))
print(ans)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
maze = [[0 if c == '

ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == 0:
            continue
        costs = [[-1 for _ in range(w)] for _ in range(h)]
        costs[i][j] = 0
        q = deque([(i, j)])
        while q:
            y, x = q.popleft()
            for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                nx, ny = x + dx, y + dy
                if (0 <= nx < w) and (0 <= ny < h) and maze[ny][nx] and costs[ny][nx] == -1:
                    costs[ny][nx] = costs[y][x] + 1
                    q.append((ny, nx))
        for row in costs:
            ans = max(ans, max(row))

print(ans)

Solution (Python):
from collections import deque
from itertools import product

def bfs(s,x, y):
    
    INF=400
    DX = [1, 0, -1, 0]
    DY = [0, 1, 0, -1]
    
    que = deque()
    res = 0
    dist = [[INF for _ in range(W)] for _ in range(H)]
 
    que.append((x, y))
    dist[x][y] = 0
    while que:
        x, y = que.pop()
        res = max(res, dist[x][y])
 
        for i in range(4):
            dx, dy = x + DX[i], y + DY[i]
 
            if dx < 0 or dx >= H or dy < 0 or dy >= W:
                continue
            if s[dx][dy] == "
                continue
 
            if dist[dx][dy] == INF:
                dist[dx][dy] = dist[x][y] + 1
                que.appendleft((dx, dy))
    return res

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

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

ans = 0
for x, y in product(range(H), range(W)):
  if S[x][y] == "
    continue
  ans = max(ans, bfs(S,x, y))
print(ans)

Solution (Python):
def main(h,w,s):
    maxStep = 0
    
    for y in range(h):
        for x in range(w):
            
            if s[y][x] == "
                continue
            
            else:
                st = [x,y]
                maxStep = max(maxStep, bfs(st,h,w,s))
    return maxStep


def bfs(st,h,w,s):
    
    maxStep = 0
    seen = [[-1]*w for _ in range(h)]
    seen[st[1]][st[0]] = 0
    todo = [st]
    mov = [(1,0),(-1,0),(0,1),(0,-1)]
    
    while len(todo) > 0:
        
        x,y = todo.pop(0)
        
        for m in mov:
            nx = x + m[0]
            ny = y + m[1]
            
            if nx < 0 or (w-1) < nx or ny < 0 or (h-1) < ny:
                continue
            
            if seen[ny][nx] == -1 and s[ny][nx] == ".":
                todo.append([nx,ny])
                seen[ny][nx] = seen[y][x] + 1
                maxStep = max(maxStep, seen[ny][nx])
    return maxStep

h,w = map(int,input().split())
s = list(list(input()) for _ in range(h))
print(main(h,w,s))

Solution (Python):
import itertools

import copy
    
h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'
    ab.append(list(a))
ab.append(list('
mx = 0

for i in range(h):
    for j in range(w):
        if ab[i][j] == '.':
            dp = [[0 for a in range(w)] for b in range(h)]
            step = [[i, j]]

            while len(step) > 0:
                y, x = step.pop(0)
                if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
                    step.append([y+1, x])
                    dp[y+1][x] = dp[y][x] + 1
                if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
                    step.append([y, x+1])
                    dp[y][x+1] = dp[y][x] + 1
                if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
                    step.append([y-1, x])
                    dp[y-1][x] = dp[y][x] + 1
                if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
                    step.append([y, x-1])
                    dp[y][x-1] = dp[y][x] + 1
            dp[i][j] = 0
            mx = max([mx, max(list(itertools.chain.from_iterable(dp)))])

print(mx)

Solution (Python):
import sys
import socket
from heapq import heappush, heappop

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('d2.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def dijkstra(a, s):
  i0, j0 = s

  debug = i0 == 1 and j0 == 2

  H = len(a)
  W = len(a[0])
  inf = 1000
  d = [[inf]*W for i in range(H)]
  d[i0][j0] = 0
  q = []
  item = (0, i0, j0)
  heappush(q, item)
  for i in range(H):
    for j in range(W):
      if a[i][j] == '
        continue
      v = 0 if (i, j) == s else inf
      item = (v, i, j)
      
  
  

  while q != []:
    v, i, j = heappop(q)
    di = [-1, 1, 0, 0]
    dj = [0, 0, -1, 1]
    for k in range(4):
      ii = i + di[k]
      jj = j + dj[k]
      if not (0 <= ii < H and 0 <= jj < W):
        continue
      if a[ii][jj] == '
        continue
      
      
      

      if d[i][j] + 1 < d[ii][jj]:
        d[ii][jj] = d[i][j] + 1
        item = (d[i][j] + 1, ii, jj)
        heappush(q, item)
      
  return d


def main():
    H, W = read_int_list()
    a = [read_str() for i in range(H)]
    res = 0
    for i in range(H):
      for j in range(W):
        if a[i][j] == '
          continue
        s = (i, j)
        d = dijkstra(a, s)
        
        
        

        for k in range(H):
          for l in range(W):
            if a[k][l] == '
              continue
            if d[k][l] > res:
              res = d[k][l]

    print(res)


def bfs(a, s):
  i0, j0 = s
  H = len(a)
  W = len(a[0])
  inf = 1000
  d = [[inf]*W for i in range(H)]
  d[i0][j0] = 0

  state = [[0] * W for i in range(H)]
  q = []
  q.append(s)
  state[i0][j0] = 1
  while q != []:
    u = q.pop(0)
    i, j = u
    state[i][j] = 2
    di = [-1, 1, 0, 0]
    dj = [0, 0, -1, 1]
    for k in range(4):
      ii = i + di[k]
      jj = j + dj[k]
      if not (0 <= ii < H and 0 <= jj < W):
        continue
      if a[ii][jj] == '
        continue

      
      if state[ii][jj] == 0:
        d[ii][jj] = d[i][j] + 1
        q.append((ii, jj))
        state[ii][jj] = 1


  return d


def main2():
    H, W = read_int_list()
    a = [read_str() for i in range(H)]
    res = 0
    for i in range(H):
      for j in range(W):
        if a[i][j] == '
          continue
        s = (i, j)
        d = bfs(a, s)
        
        
        

        for k in range(H):
          for l in range(W):
            if a[k][l] == '
              continue
            if d[k][l] > res:
              res = d[k][l]

    print(res)

main2()

Solution (Python):
import sys
import socket
from heapq import heappush, heappop

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def dijkstra(a, s):
  i0, j0 = s

  debug = i0 == 1 and j0 == 2

  H = len(a)
  W = len(a[0])
  inf = 1000
  d = [[inf]*W for i in range(H)]
  d[i0][j0] = 0
  q = []
  item = (0, i0, j0)
  heappush(q, item)
  for i in range(H):
    for j in range(W):
      if a[i][j] == '
        continue
      v = 0 if (i, j) == s else inf
      item = (v, i, j)
      
  
  

  while q != []:
    v, i, j = heappop(q)
    di = [-1, 1, 0, 0]
    dj = [0, 0, -1, 1]
    for k in range(4):
      ii = i + di[k]
      jj = j + dj[k]
      if not (0 <= ii < H and 0 <= jj < W):
        continue
      if a[ii][jj] == '
        continue
      
      
      

      if d[i][j] + 1 < d[ii][jj]:
        d[ii][jj] = d[i][j] + 1
        item = (d[i][j] + 1, ii, jj)
        heappush(q, item)
      
  return d


def main():
    H, W = read_int_list()
    a = [read_str() for i in range(H)]
    res = 0
    for i in range(H):
      for j in range(W):
        if a[i][j] == '
          continue
        s = (i, j)
        d = dijkstra(a, s)
        
        
        

        for k in range(H):
          for l in range(W):
            if a[k][l] == '
              continue
            if d[k][l] > res:
              res = d[k][l]

    print(res)


main()

Solution (Python):
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from collections import deque

def solve(x,y):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    start = [x, y]
    dist = [[10**3]*w for i in range(h)]
    dist[y][x] = 0
    Q = deque()
    Q.append(start)
    mx = 0

    while Q:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < w and 0 <= ny < h:
                if l[ny][nx]=="." and dist[ny][nx]==10**3:
                    Q.append([nx, ny])
                    dist[ny][nx] = dist[p[1]][p[0]] + 1
                    if mx < dist[ny][nx]:
                        mx=dist[ny][nx]
    return mx

ans=0
for i in range(h):
    for j in range(w):
        if l[i][j]=="
            continue

        res=solve(j,i)
        if res > ans:
            ans=res

print(ans)

Solution (Python):
from collections import deque

def bfs(x, y):
    Max = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    start = [x, y]
    distance = [[41]*W for i in range(H)]
    distance[y][x] = 0
    Q = deque()
    Q.append(start)

    while len(Q) != 0:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            
            if 0 <= nx < W and 0 <= ny < H:
                if Maze[ny][nx]=="." and distance[ny][nx]==41:
                    Q.append([nx, ny])
                    distance[ny][nx] = distance[p[1]][p[0]] + 1
    
    for i in range(H):
        for j in range(W):
            if distance[i][j]!=41 and  distance[i][j] > Max:
                Max = distance[i][j]
    return Max

H, W = map(int, input().split())
Maze = [None]*H
for i in range(H):
    Maze[i] = list(input())

MaxDistance = 0
for i in range(H):
    for j in range(W):
        if Maze[i][j] == ".":
            d = bfs(j, i)
            if d > MaxDistance:
                MaxDistance = d


print(MaxDistance)

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

    INF=-10**9
    global cnt
    cnt=0
    distance = [[INF for i in range(w+1)] for j in range(h+1)]
    

    def bfs():
        global cnt
        queue = []

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

        distance[sx][sy] = 0

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

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


                if (0 <= nx and  0 <= ny  and maze[nx][ny] != '
                    queue.insert(0, (nx, ny))

                    distance[nx][ny] = distance[x][y] + 1
                    if cnt<distance[nx][ny]:
                        cnt=distance[nx][ny]
        return cnt
    return bfs()


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

for i in range(h):
    maze[i]=['
maze=[['

ans=0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if maze[i][j] == '
            continue
        v = (clear_maze(i, j, maze))

        if ans <= v:
            ans = v
print(ans)