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(sy,sx):
    dist[sy][sx]=0
    q=deque([[sy,sx]])
    while q:
        cy,cx=q.popleft()
        for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx=cy+i,cx+j
            if ny<0 or h-1<ny or nx<0 or w-1<nx or path[ny][nx]=='
            if path[ny][nx]=='.' and dist[ny][nx]==-1:
                dist[ny][nx]=dist[cy][cx]+1
                q.append([ny,nx])
    max_dist=-1
    for i in range(h):
        for j in range(w):
            if path[i][j]=='
            max_dist=max(max_dist,dist[i][j])
    return max_dist

h,w=map(int,input().split())
path=[input() for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        if path[i][j]=='
            continue
        dist=[[-1]*w for i in range(h)]
        t=bfs(i,j)
        ans=max(ans,t)
print(ans)

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


def bfs(maze, sx, sy):
    d = [[-float("inf")] * w for i in range(h)]

    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[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    an = 0
    for i in d:
        an = max(an,max(i))
    return an


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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
def inputS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

from collections import deque

def bfs(grid, start):
  dist = [[-1]*(W+2) for _ in range(H+2)]
  queue = deque([start])
  dist[start[0]][start[1]] = 0
  while queue:
    x, y = queue.popleft()
    
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
      nx, ny = x+i, y+j
      if grid[nx][ny] == "." and dist[nx][ny] == -1:
        dist[nx][ny] = dist[x][y]+1
        queue.append((nx, ny))
    if not queue:
      return dist[x][y]
    
H, W = map(int, input().split())

grid = [["
grid = ["

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

Solution (Python):
from collections import deque

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

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

def bfs(i,j): 
    if S[i][j] == '
        return 0
    
    visited=[[0]*w for _ in range(h)] 
    visited[i][j]=1 
    
    que=deque([(i,j,0)]) 
    
    while len(que)>0:
        ci,cj,d = que.popleft() 

        for mi,mj in move: 
            ni,nj = ci+mi,cj+mj 
            if 0 <= ni < h and 0 <= nj < w and visited[ni][nj]==0:
                if S[ni][nj] == '.':
                    visited[ni][nj] = 1
                    que.append((ni, nj, d+1))
    return d
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(ans)

Solution (Python):

from collections import deque         
INF = int(1e9)
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

def main():
    h, w = map(int, input().split())
    maze = [input() for _ in range(h)]
    ans = -1 
    
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '
                continue
            g = [[INF for _ in range(w)] for _ in range(h)] 
            q = deque()
            q.append((i, j))
            g[i][j] = 0
            while len(q) > 0:
                pi, pj = q.popleft()
                for dx, dy in dd:
                    x = pi + dx
                    y = pj + dy
                    if (x < 0) | (y < 0) | (x >= h) | (y >= w): 
                        continue
                    if maze[x][y] == '
                        continue
                    if g[x][y] != INF:
                        continue
                    q.append((x, y))
                    g[x][y] = g[pi][pj]+1 
            

            for k in range(h):
                for l in range(w):
                    if g[k][l] == INF:
                        continue
                    ans = max(ans, g[k][l])
    print(ans)
main()

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime


H,W = imn()
S = [input() for _ in range(H)]
ans = 0
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

for h in range(H):
    for w in range(W):
        if S[h][w] == '
        d = [[-1 for _ in range(W)] for _ in range(H)]
        d[h][w] = 0
        max_s = 0
        queue = deque([(w, h)])
        while len(queue) > 0:
            p = queue.popleft()
            for i in range(4):
                x = p[0] + dx[i]
                y = p[1] + dy[i]
                if x < 0 or y < 0 or x >= W or y >= H or S[y][x] == '
                d[y][x] = d[p[1]][p[0]] + 1
                queue.append((x,y))
                max_s = max(max_s, d[y][x])
        ans = max(ans, max_s)
print(ans)

Solution (Python):
from collections import deque

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

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


def maxCost(s0, s1):
    """
    (s0, s1)から任意の道に最短経路で移動するとして、その中での最大コストを算出する
    """
    maxCost = 0
    visited = [[10**9 for _ in range(W)] for _ in range(H)] 
    q = deque([(s0, s1, 0)])
    visited[s0][s1] = 0

    while q:
        u0, u1, cost = q.popleft()
        
        if u0 < H - 1 and S[u0+1][u1] == "." and visited[u0+1][u1] > cost+1:
            
            visited[u0+1][u1] = cost+1
            maxCost = max(maxCost, cost+1)
            q.append((u0+1, u1, cost+1))
        if u0 > 0 and S[u0-1][u1] == "." and visited[u0-1][u1] > cost+1:
            
            visited[u0-1][u1] = cost+1
            maxCost = max(maxCost, cost+1)
            q.append((u0-1, u1, cost+1))
        if u1 < W - 1 and S[u0][u1+1] == "." and visited[u0][u1+1] > cost+1:
            
            visited[u0][u1+1] = cost+1
            maxCost = max(maxCost, cost+1)
            q.append((u0, u1+1, cost+1))
        if u1 > 0 and S[u0][u1-1] == "." and visited[u0][u1-1] > cost+1:
            
            visited[u0][u1-1] = cost+1
            maxCost = max(maxCost, cost+1)
            q.append((u0, u1-1, cost+1))

    return maxCost

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ans = max(ans, maxCost(i, j))
print(ans)

Solution (Python):
import sys
import math
from math import sqrt
from collections import deque
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)

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

def bfs(x,y):
    for i,j in [[x+1,y],[x,y+1],[x-1,y],[x,y-1]]:
        if i<0 or h<=i or j<0 or w<=j :continue
        if dist[i][j] != -1:continue
        if miti[i][j]=="
        dist[i][j]=dist[x][y]+1
        queue.append([i,j])
    while queue:
        t,r=queue.popleft()
        bfs(t,r)
ans=0
for i in range(h):
    for j in range(w):
        if miti[i][j]=="
        dist=[[-1 for i in range(w)] for j in range(h)]
        dist[i][j]=0
        queue=deque([])
        bfs(i,j)
        
        
        for s in range(h):
            for t in range(w):
                ans=max(ans,dist[s][t])
print(ans)

Solution (Python):


import sys

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

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

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

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

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

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

Solution (Python):


from collections import deque

H, W = map(int, input().split())
S = []
maxlen = 0

for _ in range(H):
    S.append(input())



for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            queue = deque([[i,j]])
            distance = [[-1]*W for _ in range(H)]
            distance[i][j] = 0
            mazemax = 0
            
            while len(queue): 
                
                x, y = queue.popleft()
                for i2, j2 in ([1, 0], [-1, 0], [0, 1], [0, -1]): 
                    new_x, new_y = x+i2, y+j2
                    if new_x < 0 or new_x >= H or new_y < 0 or new_y >= W: 
                        continue
                    elif S[new_x][new_y] == "." and distance[new_x][new_y] == -1:
                        distance[new_x][new_y] = max(distance[new_x][new_y], distance[x][y] + 1)
                        mazemax = max(mazemax, distance[new_x][new_y])
                        queue.append([new_x, new_y])
                if len(queue) == 0:
                    maxlen = max(maxlen,mazemax)

print(maxlen)

"""
5 5
...
.
...


"""

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]!="
         dp=[[inf for _ in range(w)]for _ in range(h)]
         dp[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 dp[ni][nj]>dp[si][sj]+1:
                     dp[ni][nj]=dp[si][sj]+1
                     que.append((ni,nj))
                     ans=max(ans,dp[si][sj]+1)
print(ans)

Solution (Python):
R,C = map(int,input().split())
graph = [[i for i in input()] for j in range(R)]
visited = [[False for i in range(C)] for j in range(R)]

def dfs(start_y,start_x):
  queue = [[start_y,start_x,0]]
  while queue:
    now = queue.pop(0)
    visited[now[0]][now[1]] = True
    for next in [[1,0],[-1,0],[0,1],[0,-1]]:
      if now[0]+next[0] < 0 or now[1]+next[1] < 0: continue
      if now[0]+next[0] > R-1 or now[1]+next[1] > C-1: continue
      if visited[now[0]+next[0]][now[1]+next[1]]: continue
      if graph[now[0]+next[0]][now[1]+next[1]]=='
      queue.append([now[0]+next[0],now[1]+next[1],now[2]+1])
      visited[now[0]+next[0]][now[1]+next[1]] = True
  return now[2]

ans = 0
for row_s in range(R):
  for column_s in range(C):
      if graph[row_s][column_s]=='
      visited = [[False for i in range(C)] for j in range(R)]
      ans = max(ans,dfs(row_s,column_s))
    
print(ans)

Solution (Python):
from collections import deque
q = deque()

def bfs(i, j):
    q.append((i, j))
    d[i][j] = 0
    c[i][j] = 1
    m = 0
    while len(q) != 0:
        S = q.popleft()
        i, j = S[0], S[1]
        if s[i + 1][j] == "." and c[i + 1][j] == 0:
            q.append((i + 1, j))
            d[i + 1][j] = d[i][j] + 1
            c[i + 1][j] = 1
            if d[i + 1][j] > m:
                m = d[i + 1][j]
        if s[i][j + 1] == "." and c[i][j + 1] == 0:
            q.append((i, j + 1))
            d[i][j + 1] = d[i][j] + 1
            c[i][j + 1] = 1
            if d[i][j + 1] > m:
                m = d[i][j + 1]
        if s[i - 1][j] == "." and c[i - 1][j] == 0:
            q.append((i - 1, j))
            d[i - 1][j] = d[i][j] + 1
            c[i - 1][j] = 1
            if d[i - 1][j] > m:
                m = d[i - 1][j]
        if s[i][j - 1] == "." and c[i][j - 1] == 0:
            q.append((i, j - 1))
            d[i][j - 1] = d[i][j] + 1
            c[i][j - 1] = 1
            if d[i][j - 1] > m:
                m = d[i][j - 1]
        c[i][j] = 2
    return m

h, w = map(int, input().split())
s = [["
s.insert(0, ["
s.append(["
ans = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i][j] == ".":
            d = [[-1 for _ in range(w + 2)] for _ in range(h + 2)]
            c = [[0 for _ in range(w + 2)] for _ in range(h + 2)]
            a = bfs(i, j)
            if a > ans:
                ans = a
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
ans=0
inf=float("inf")
for i in range(h):
   for j in range(w):
      if S[i][j]!="
         dp=[[inf for _ in range(w)]for _ in range(h)]
         dp[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 dp[ni][nj]>dp[si][sj]+1:
                     dp[ni][nj]=dp[si][sj]+1
                     ans=max(ans,dp[si][sj]+1)
                     que.append((ni,nj))
print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

from collections import deque

H, W = input_nums()
H += 2
W += 2
grid = '
for i 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):
            next_v = v + move
            if grid[next_v] == '
                continue
            d_next_v = dv + 1
            if d_next_v >= dist[next_v]:
                continue
            dist[next_v] = d_next_v
            q.append(next_v)
    return max([x for x in dist if x < INF])

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

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

Solution (Python):
from collections import deque

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


ans = 0

def bfs(y,x,m):
    
    graph = [[None] * w for i in range(h)]
    
    graph[y][x] = 0

    q = deque()
    q.append((y,x))

    for i in range(h):
        for j in range(w):
            if l[i][j] == '
                graph[i][j] = -1

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

    while q: 
        
        i, j = q.popleft()

        for di, dj in move:
            
            ni , nj = i + di, j + dj
            
            if 0 <= ni < h and 0 <= nj < w and graph[ni][nj] is None:
                
                
                graph[ni][nj] = graph[i][j] + 1
                
                q.append((ni, nj))

    
    
    return max(max(r) for r in graph)

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

Solution (Python):
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
ans=0
inf=float("inf")
for i in range(h):
   for j in range(w):
      if S[i][j]!="
         dp=[[inf for _ in range(w)]for _ in range(h)]
         dp[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 dp[ni][nj]>dp[si][sj]+1:
                     dp[ni][nj]=dp[si][sj]+1
                     ans=max(ans,dp[si][sj]+1)
                     que.append((ni,nj))
print(ans)

Solution (Python):
H,W = map(int,input().split())
A = []

for i in range(H):
    t = list(input())
    A.append(t)

tate = (-1,1,0,0)
yoko = (0,0,-1,1)
answer = 0

for i in range(H):
    for j in range(W):
        dp = [[10**4 for i in range(W)] for j in range(H)]
        if A[i][j] == '.':
            dp[i][j] = 0
            Q = list()
            Q.append([i,j])
            while(len(Q) > 0 ):
                s = Q[0][0]
                t = Q[0][1]
                for p, q in zip(tate, yoko):
                    m = s + p
                    n = t + q
                    if m >= 0 and m < H:
                        if n >= 0 and n < W:
                            if A[m][n] == '.':
                                if dp[m][n] == 10**4 :
                                    dp[m][n] = dp[s][t] + 1
                                    Q.append([m,n])
                Q.remove(Q[0])

            for k in range(H):
                for l in range(W):
                    if dp[k][l] < 10**4:
                        answer = max(answer,dp[k][l])

print(answer)

Solution (Python):
import queue

class pair:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def getter(self):
        return [self.x, self.y]

def solvmaiz(maze, x ,y):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    q = queue.Queue()
    INF = 10**5
    d = [[INF for x in range(W)]for y in range(H)]
    q.put(pair(x,y))
    d[y][x] = 0
    goal = [0, 0]
    while(not q.empty()):
        p = q.get().getter()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if nx >= 0 and nx < W and ny >= 0 and ny < H and d[ny][nx] == INF and maze[ny][nx] != '
                q.put(pair(nx,ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
        goal[0] = p[1]
        goal[1] = p[0]

    return d[goal[0]][goal[1]]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze =[]
    for i in range(H):
        j = input()
        maze.append([])
        for k in j:
            maze[i].append(k)
    ans = 0
    for y in range(H):
        for x in range(W):
            if maze[y][x] == '
                continue
            ans = max(ans, solvmaiz(maze, x, y))
    print(ans)

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

Solution (Python):
n,m=map(int,input().split())
l=["
l=["
inf=10**7
from queue import Queue as qu
mo=[(1,0),(-1,0),(0,1),(0,-1)]
ret=0
for i in range(1,n+1):
  for j in range(1,m+1):
    if l[i][j]==".":
      q=qu()
      step=[[inf for c in range(m+2)] for x in range(n+2)]
      step[i][j]=0
      q.put((i,j))
      while not q.empty():
        d=q.get()
        for g in mo:
          c,cc=g[0]+d[0],g[1]+d[1]
          if step[c][cc]==inf and l[c][cc]==".":
            q.put((c,cc))
            step[c][cc]=step[d[0]][d[1]]+1
            ret=max(ret,step[c][cc])
print(ret)

Solution (Python):
from collections import deque

def bfs(h, w, s, 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 s[nx][ny] != '
                que.append((nx, ny))
                d[nx][ny] = d[x][y] + 1

    md = 0
    for i in range(h):
        for j in range(w):
          md = max(md, d[i][j])

    return md

h, w = [int(_) for _ in input().split()]
s = [0] * h
for i in range(h):
    s[i] = list(input())

ans = 0

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

print(ans)

Solution (Python):
class BreadthFirstSearch:

    def __init__(self, h, w, maze):
        self.h = h
        self.w = w
        self.maze = maze
        self.visited = [[0] * w for _ in range(h)]
        self.queue = []
        self.dx_dy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        self.ans = 0

    def search(self):
        for i in range(self.h):
            for j in range(self.w):
                if self.maze[i][j] != ".":
                    continue
                self.queue.append((i, j))
                self.visited[i][j] = 1

                while len(self.queue) > 0:
                    now = self.queue.pop(0)
                    for dx, dy in self.dx_dy:
                        x = now[0] + dx
                        y = now[1] + dy
                        if x < 0 or self.h <= x:
                            continue
                        if y < 0 or self.w <= y:
                            continue
                        if self.maze[x][y] == "
                            continue
                        if self.visited[x][y] == 0:
                            self.visited[x][y] = self.visited[now[0]][now[1]] + 1
                            self.queue.append((x, y))
                for l in range(self.h):
                    for m in range(self.w):
                        self.ans = max(self.ans, self.visited[l][m])
                self.queue = []
                self.visited = [[0] * self.w for _ in range(self.h)]


def main():
    h, w = map(int, input().split())
    maze = [list(input()) for _ in range(h)]
    bfs = BreadthFirstSearch(h, w, maze)
    bfs.search()
    print(bfs.ans-1)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque

def dfs(field, s):
    MOVE = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    q = deque([(0, s)])
    dist = [[-1] * w for _ in range(h)]

    d, i, j = -1, -1, -1
    while q:
        d, (i, j) = q.popleft()
        if dist[i][j] != -1:
            continue
        dist[i][j] = d
        for di, dj in MOVE:
            ni, nj = i + di, j + dj
            if not 0 <= ni < h or not 0 <= nj < w:
                continue
            if field[ni][nj] == '
                continue
            if dist[ni][nj] != -1:
                continue
            q.append((d + 1, (ni, nj)))
    return d, i, j

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

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

print(ans)

Solution (Python):


import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False


        lines.append(input())
        (h, w) = [int(e) for e in lines[0].split(" ")]
        for i in range(h):
            lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
        (h, w) = [int(e) for e in lines[0].split(" ")]
    
    s = []
    for i in range(1, h + 1):
        s.append(lines[i])
        

    return (h, w, s)

def solve(h, w, s):


    result = -1
    for i in range(h):
        for j in range(w):

            if s[i][j] == "
                continue
            
            d = 0
            resolved = set() 
            last_resolved = set()
            last_resolved.add((i, j))
            for r in last_resolved:
                resolved.add(r)

            while True:
                neighbors_of_last_resolved = set()
                for (m, n) in last_resolved:

                    for (dm, dn) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:

                        if m+dm < 0 or h - 1 < m+dm:
                            continue

                        if n+dn < 0 or w - 1 < n+dn:
                            continue
                        
                        if s[m+dm][n+dn] == "
                            continue
                        else:
                            r = (m+dm, n+dn)
                            if not r in resolved:
                                neighbors_of_last_resolved.add(r)
                
                last_resolved = neighbors_of_last_resolved
                for r in last_resolved:
                    resolved.add(r)

                if len(last_resolved) == 0:
                    break
                else:
                    d = d + 1

            if d > result:
                result = d

    return result

def main():
    
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r)
    else:
        print("%s" % result)

if __name__ == '__main__':

    main()

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
import copy


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def neighbors4(x, y):
  dxy = (0, 1, 0, -1, 0 )
  for i in range(4):
    yield(x + dxy[i], y + dxy[i+1])

h,w = get_nums_l()

grid_s = [ input() for _ in range(h) ]
grid = [ [-1] * (w+2) for _ in range(h+2) ]

log(grid_s)

def init_grid():
    for y in range(1,h+1):
        for x in range(1, w+1):
            if grid_s[y-1][x-1] == ".":
                grid[y][x] = 999999999999999999

ans = 0
for y in range(1,h+1):
    for x in range(1, w+1):
        if grid_s[y-1][x-1] == ".":
            init_grid()
            grid[y][x] = 0

            que = deque()
            que.append((x, y, 1))

            max_ = 0
            while que:
                x,y,score = que.popleft()

                for nx,ny in neighbors4(x,y):
                    if grid[ny][nx] != -1 and grid[ny][nx] > score:
                        grid[ny][nx] = score
                        max_ = max(max_, score)
                        que.append((nx, ny, score+1))
            ans = max(ans, max_)

print(ans)