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

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return max(map(max, distance))


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

        tmp = bfs(S, (i, j))
        if tmp > answer:
            answer = tmp

print(answer)

Solution (Python):
from collections import deque
import copy
H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
S = []
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      maze[i][j] = float("inf")
      S.append([i, j])
    else:
      maze[i][j] = -1
def bfs(H, W, maze, S):
  ans = 0
  for sy, sx in S:
    maze1 = copy.deepcopy(maze)
    maze1[sy][sx] = 0
    q = deque()
    q.append([sy,sx])
    while len(q)>0:
      y, x = q.popleft()
      for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        nexty = y+i
        nextx = x+j
        if nexty < 0 or nexty>=H or nextx < 0 or nextx>=W:
          continue
        if maze1[nexty][nextx] != -1:
          if maze1[nexty][nextx] > maze1[y][x]+1:
            maze1[nexty][nextx] = maze1[y][x] + 1
            q.append([nexty, nextx])
            ans = max(ans, maze1[nexty][nextx])
  print(ans)
bfs(H, W, maze, S)

Solution (Python):
from collections import deque
import copy
def bfs():
  H, W = map(int, input().split())
  maze = [list(input()) for i in range(H)]
  S = []
  for i in range(H):
    for j in range(W):
      if maze[i][j] == ".":
        maze[i][j] = float("inf")
        S.append([i, j])
      else:
        maze[i][j] = -1
  ans = 0
  for k in range(len(S)):
    maze1 = copy.deepcopy(maze)
    maze1[S[k][0]][S[k][1]] = 0
    q = deque([[S[k][0],S[k][1]]])
    while q:
      y, x = q.popleft()
      for i, j in [(1, 0), (0, 1), (0, -1), (-1, 0)]:
        nexty, nextx = y+i, x+j
        if nexty < 0 or nexty>=H or nextx < 0 or nextx>=W:
          continue
        dist1 = maze1[nexty][nextx]
        if dist1 != -1:
          if dist1 > maze1[y][x]+1:
            maze1[nexty][nextx] = maze1[y][x] + 1
            q.append([nexty, nextx])
            ans = max(ans, maze1[nexty][nextx])
  print(ans)
bfs()

Solution (Python):
import queue
import copy
 
H,W= map(int,input().split())
 
dy = [1,0,-1,0]
dx = [0,1,0,-1]

MAX_N = 0


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

for k in range(1,H+1):
    for l in range(1,W+1): 
        sy = k
        sx = l
        A = copy.deepcopy(L)
        
        
        
        

        if A[sy-1][sx-1] == '.':

            
            q = queue.Queue()
            q.put([sy-1,sx-1])
            
            
            A[sy-1][sx-1] = 0
            
            while not q.empty():
                
                tem = q.get()

                for i in range(4):
                    
                    ny = tem[0] + dy[i]
                    nx = tem[1] + dx[i]
            
                    if (0<= ny < H) and (0<= nx < W) and A[ny][nx] == '.':
                        A[ny][nx] = A[tem[0]][tem[1]] + 1
                        if A[ny][nx] > MAX_N:
                            MAX_N = A[ny][nx]
                        q.put([ny,nx])

print(MAX_N)

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

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

def bfs(sy, sx):
    visited = [[-1]*w for i in range(h)]
    visited[sy][sx] = 0
    que = deque([[sy, sx]])
    while que:
        
        y,x = que.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_y, next_x = y+i, x+j
            
            if next_y < 0 or next_x < 0 or next_y > h-1 or next_x > w-1:
                continue
            if SHWs[next_y][next_x] == '.' and (visited[next_y][next_x] == -1 or visited[next_y][next_x] > visited[y][x]+1):
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])
    
    return np.amax(np.array(visited))

            
ans = 0
for sy in range(h):
    for sx in range(w):
        if SHWs[sy][sx] == '
            continue
        count = bfs(sy=sy, sx=sx)

        if count > ans:
            ans = count


print(ans)

Solution (Python):
from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()

Solution (Python):
from collections import deque


def solve(S, s):
    if S[s[0]][s[1]] != ".":
        return -1
    queue = deque([s])
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    visited[s[0]][s[1]] = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1,0], [-1,0], [0,1], [0,-1]):
            new_y, new_x = y+j, x+k
            if new_x in range(W) and new_y in range(H) and S[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    res = -1
    for v in visited:
        for u in v:
            res = max(res, u)
    return res


H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = -1
for i in range(H):
    for l in range(W):
        ans = max(ans, solve(S, [i, l]))
print(ans)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    visited[start[0]][start[1]] = True
    while queue:
        x, y = queue.popleft()

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    visited[new_x][new_y] = True
                    queue.append((new_x, new_y))
    return distance


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

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp

print(answer)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    visited[start[0]][start[1]] = True
    while queue:
        x, y = queue.popleft()

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    visited[new_x][new_y] = True
                    queue.append((new_x, new_y))
    return distance


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

        cnt = 0
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = dy + j, dx + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if S[new_x][new_y] == '.':
                    cnt += 1

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp

print(answer)

Solution (Python):
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='
          A[h][w]=0
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
        
    A = [a for b in A for a in b if a!=inf]
    ans = max(ans,max(A))
    
print(ans)

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

for i in range(h):
  for j in range(w):
    if l[i][j]=='.':
      if i!=0:
        if l[i-1][j]!='
          connection[i*w+j].append((i-1)*w+j)
      if i!=h-1:
        if l[i+1][j]!='
          connection[i*w+j].append((i+1)*w+j)
      if j!=0:
        if l[i][j-1]!='
          connection[i*w+j].append(i*w+j-1)
      if j!=w-1:
        if l[i][j+1]!='
          connection[i*w+j].append(i*w+j+1)

n=h*w
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

ans=[]
for i in range(h*w):
  ans.append(max(bfs(i)))
print(max(ans))

Solution (Python):
def d_maze_master(INF=float('inf')):
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    def bfs(start_row, start_col):
        """迷路の (start_row, start_col) マスから最も遠いマスへの移動回数"""
        diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

        def is_inside(row, col):
            return 0 <= row < H and 0 <= col < W

        queue = deque([(start_row, start_col)])
        dist = [[INF for _ in range(W)] for _ in range(H)]
        dist[start_row][start_col] = 0
        while queue:
            row, col = queue.pop()
            for dr, dc in diff:
                nr, nc = row + dr, col + dc
                if is_inside(nr, nc) and Maze[nr][nc] != '
                    queue.appendleft((nr, nc))
                    dist[nr][nc] = dist[row][col] + 1
        ret = -1
        for row in range(H):
            for col in range(W):
                if dist[row][col] != INF:
                    ret = max(ret, dist[row][col])
        return ret

    ans = 0
    for start_row in range(H):
        for start_col in range(W):
            if Maze[start_row][start_col] != '
                ans = max(ans, bfs(start_row, start_col))
    return ans

print(d_maze_master())

Solution (Python):
from collections import deque


def adjacents(r, c):
    if r > 0:
        yield r - 1, c
    if r < h - 1:
        yield r + 1, c
    if c > 0:
        yield r, c - 1
    if c < w - 1:
        yield r, c + 1


def is_road(r, c):
    return s[r][c] == '.'


def bfs(r, c):
    inf = h * w

    q = deque()
    q.append((r, c))

    dist = [[inf] * w for _ in range(h)]
    dist[r][c] = 0

    while q:
        r, c = q.popleft()
        d = dist[r][c]
        for nr, nc in ((nr, nc) for nr, nc in adjacents(r, c) if is_road(nr, nc)):
            if dist[nr][nc] < inf:
                continue
            nd = d + 1
            dist[nr][nc] = nd
            q.append((nr, nc))

    return d


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

print(max(bfs(r, c) for r in range(h) for c in range(w) if is_road(r, c)))

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

def bfs(h,w):
  checked = [[False for i in range(W)] for j in range(H)]
  q = [(h,w,0)] if maze[h][w]=="." else []
  checked[h][w] = True
  g_n = 0
  while q:
    h_,w_,n = q.pop(0)
    g_n = max(n, g_n)
    for i,j in zip([0,0,-1,1],[-1,1,0,0]):
      if (0<=h_+i<H) and (0<=w_+j<W):
        if checked[h_+i][w_+j]: continue
        checked[h_+i][w_+j] = True
        if maze[h_+i][w_+j]==".": q.append((h_+i,w_+j,n+1))
  return g_n

n = 0
for i in range(H):
  for j in range(W):
    n = max(n, bfs(i,j))
print(n)

Solution (Python):

from collections import deque
H, W = map(int, input().split())
INF = -1
maze = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp[:])

def bfs(sx, sy):
    visited = [[INF for _ in range(W)] for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    visited[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W:
                if maze[nx][ny] != "
                    q.append([nx, ny])
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
        dist = -1
        for i in range(H):
            dist = max(dist, max(visited[i]))
    return dist
ans = -1
for x in range(H):
    for y in range(W):
        if maze[x][y] == "
            continue
        ans = max(ans, bfs(x, y))
print(ans)

Solution (Python):
def d_maze_master():
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    def bfs(start_row, start_col):
        diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

        def is_inside(row, col):
            return 0 <= row < H and 0 <= col < W

        queue = deque([(start_row, start_col)])
        dist = [[-1 for _ in range(W)] for _ in range(H)]
        dist[start_row][start_col] = 0
        while queue:
            row, col = queue.pop()
            for dr, dc in diff:
                nr, nc = row + dr, col + dc
                if is_inside(nr, nc) and Maze[nr][nc] != '
                    queue.appendleft((nr, nc))
                    dist[nr][nc] = dist[row][col] + 1
        return dist

    ans = 0
    for start_row in range(H):
        for start_col in range(W):
            if Maze[start_row][start_col] == '
                continue
            dist = bfs(start_row, start_col)
            for row in range(H):
                for col in range(W):
                    if Maze[row][col] != '
                        ans = max(ans, dist[row][col])
    return ans

print(d_maze_master())

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    visited[start[0]][start[1]] = True
    while queue:
        x, y = queue.popleft()

        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    visited[new_x][new_y] = True
                    queue.append((new_x, new_y))
    return distance


answer = 0
limit = H - 1 + W - 1
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue

        cnt = 0
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = dy + j, dx + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if S[new_x][new_y] == '.':
                    cnt += 1

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp
        if answer == limit:
            print(answer)
            exit()

print(answer)

Solution (Python):
def d_maze_master(INF=float('inf')):
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    def bfs(start_row, start_col):
        diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

        def is_inside(row, col):
            return 0 <= row < H and 0 <= col < W

        queue = deque([(start_row, start_col)])
        dist = [[INF for _ in range(W)] for _ in range(H)]
        dist[start_row][start_col] = 0
        while queue:
            row, col = queue.pop()
            for dr, dc in diff:
                nr, nc = row + dr, col + dc
                if is_inside(nr, nc) and Maze[nr][nc] != '
                    queue.appendleft((nr, nc))
                    dist[nr][nc] = dist[row][col] + 1
        return dist

    ans = 0
    for start_row in range(H):
        for start_col in range(W):
            if Maze[start_row][start_col] == '
                continue
            dist = bfs(start_row, start_col)
            for row in range(H):
                for col in range(W):
                    if Maze[row][col] != '
                        ans = max(ans, dist[row][col])
    return ans

print(d_maze_master())

Solution (Python):
import math
import sys

def f(s):
    return -2 \
        if s=='


def dfs(s_x,s_y):
    tmp=[[s[i][j] for j in range(w)] for i in range(h)]
    tmp[s_x][s_y]=0
    que=[[s_x,s_y]]
    que_next=[]
    level=-1
    while que!=[]:
        level+=1
        for p in que:

            px,py=p[0],p[1]

            for q in [[px+1,py],[px-1,py],[px,py+1],[px,py-1]]:
                qx,qy=q[0],q[1]
                if (qx>=0 and qx<h) and (qy>=0 and qy<w) and tmp[qx][qy]==-1:
                    tmp[qx][qy]=0
                    que_next.append(q)


        que=[que_next[i] for i in range(len(que_next))]
        que_next=[]
    return level



h,w=map(int,input().split())
s=[[] for i in range(h)]
for i in range(h):
    p=input()
    s[i]=[f(p[j]) for j in range(w)]

ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==-1:
            ans=max(ans,dfs(i,j))

print(ans)

Solution (Python):
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
import numpy as np
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
      
    A = np.array(A)
    ans = max(ans,max(A[A<10**5]))
    
print(ans)

Solution (Python):

from collections import deque
H, W = map(int, input().split())
INF = -1
maze = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp[:])

def bfs(sx, sy):
    visited = [[INF for _ in range(W)] for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    visited[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W:
                if maze[nx][ny] != "
                    q.append([nx, ny])
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
        dist = -1
        for i in range(H):
            dist = max(dist, max(visited[i]))
    return dist
ans = -1
for i in range(H):
    for j in range(W):
        x, y = i, j
        if maze[x][y] == "
            continue
        ans = max(ans, bfs(x, y))
print(ans)

Solution (Python):
import sys
import numpy as np
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, W = map(int, readline().split())
S = [list(readline().decode('utf-8').rstrip()) for _ in range(H)]


def adjacent_4(h, w):
    ret = []
    for (dh, dw) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        h_ = h + dh
        w_ = w + dw

        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


def bfs(S, h, w):

    visited = [[10**9] * W for _ in range(H)]
    visited[h][w] = 1

    que = deque()
    que.append((h, w))

    while len(que) != 0:
        h_, w_ = que.popleft()
        acc = visited[h_][w_]

        for adj_h, adj_w in adjacent_4(h_, w_):
            if S[adj_h][adj_w] == '
                continue
            acc_ = acc + 1
            if acc_ >= visited[adj_h][adj_w]:
                continue
            visited[adj_h][adj_w] = acc_
            que.append((adj_h, adj_w))

    return max(visited[h][w] for h in range(H)
               for w in range(W) if visited[h][w] != 10**9) - 1


"""
ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '
            continue
        ans = max(ans, bfs(S, h, w))
"""
ans = max(bfs(S, h, w) for h in range(H) for w in range(W) if S[h][w] != '
print(int(ans))

Solution (Python):
from collections import deque
H,W = map(int,input().split())
maze = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ls = []
count = 0
for i in range(H):
    tmp = list(input())
    maze.append(tmp)
    for j in range(W):
        if tmp[j] != "
            ls.append([i,j])
            count += 1
def bfs(sx,sy):
    INF = -1
    cost = [[INF]*W for _ in range(H)]
    P = deque()
    P.append([sx,sy])
    cost[sx][sy] = 0
    while len(P) != 0:
        p = P.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] != "
                P.append([nx,ny])
                cost[nx][ny] = cost[p[0]][p[1]]+1
    return cost
def solve():
    ans = 0
    for i in ls:
        sx,sy = i[0],i[1]
        cs = bfs(sx,sy)
        for k in range(len(cs)):
            if ans == count:
                break
            if max(cs[k]) > ans:
                ans = max(cs[k])
    return ans
print(solve())

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

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

ANS = 0

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

import queue
q = queue.Queue()

for i in range(H):
    for j in range(W):
        st = MAP[i][j]
        if st=='
        dist = [[0]*W for i in range(H)]
        visited = [[0]*W for i in range(H)]
        visited[i][j] = 1
        q.put([i,j])
        while not q.empty():
            y,x = q.get()
            for dy,dx in dxy:
                ny,nx = y+dy,x+dx
                if not (0<=nx<W): continue
                if not (0<=ny<H): continue
                if visited[ny][nx]: continue
                if MAP[ny][nx] == '
                visited[ny][nx] = 1
                dist[ny][nx] = dist[y][x] + 1
                q.put([ny,nx])
        ANS = max(ANS, max(max(row) for row in dist))
print(ANS)

Solution (Python):


from collections import deque

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


def not_investigated_positions(current_position):
    output = []
    for udrl in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        y = current_position[0]+udrl[0]
        x = current_position[1]+udrl[1]
        if 0 <= y <= H-1 and 0 <= x <= W-1:
            if S[y][x] == "." and distance[y][x] == -1:
                output.append([y, x])
    return output

ans = 0

for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == "
            continue
        distance = [[-1]*W for _ in range(H)]
        current_position = [sy, sx]
        distance[sy][sx] = 0
        next_positions = deque()
        next_positions.append(current_position)

        while next_positions:
            current_position = next_positions.popleft()
            for q in not_investigated_positions(current_position):
                distance[q[0]][q[1]] = distance[current_position[0]][current_position[1]] + 1
                next_positions.append(q)

        ans = max(ans, max(map(max,distance)))

print(ans)

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

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

ANS = 0

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

import queue
q = queue.Queue()

for i in range(H):
    for j in range(W):
        st = MAP[i][j]
        if st=='
        dist = [[0]*W for i in range(H)]
        visited = [[0]*W for i in range(H)]
        visited[i][j] = 1
        q.put([i,j])
        while not q.empty():
            y,x = q.get()
            for dy,dx in dxy:
                ny,nx = y+dy,x+dx
                if not (0<=nx<W): continue
                if not (0<=ny<H): continue
                if visited[ny][nx]: continue
                if MAP[ny][nx] == '
                visited[ny][nx] = 1
                dist[ny][nx] = dist[y][x] + 1
                q.put([ny,nx])
        ANS = max(ANS, max(max(row) for row in dist))
print(ANS)

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

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

ANS = 0

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

import queue
q = queue.Queue()

for i in range(H):
    for j in range(W):
        st = MAP[i][j]
        if st=='
        dist = [[0]*W for i in range(H)]
        visited = [[0]*W for i in range(H)]
        visited[i][j] = 1
        q.put([i,j])
        while not q.empty():
            y,x = q.get()
            for dy,dx in dxy:
                ny,nx = y+dy,x+dx
                if not (0<=nx<W): continue
                if not (0<=ny<H): continue
                if visited[ny][nx]: continue
                if MAP[ny][nx] == '
                visited[ny][nx] = 1
                dist[ny][nx] = dist[y][x] + 1
                q.put([ny,nx])
        ANS = max(ANS, max(max(row) for row in dist))
print(ANS)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
maze = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ls = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp)
    for j in range(W):
        if tmp[j] != "
            ls.append([i,j])
def bfs(sx,sy):
    INF = -1
    cost = [[INF]*W for _ in range(H)]
    P = deque()
    P.append([sx,sy])
    cost[sx][sy] = 0
    while len(P) != 0:
        p = P.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] != "
                P.append([nx,ny])
                cost[nx][ny] = cost[p[0]][p[1]]+1
    return cost
def solve():
    ans = 0
    for i in ls:
        sx,sy = i[0],i[1]
        cs = bfs(sx,sy)
        for k in range(len(cs)):
            if max(cs[k]) > ans:
                ans = max(cs[k])
    return ans
print(solve())

Solution (Python):
import collections
import numpy as np
import sys
input = sys.stdin.readline

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
inf = float('inf')


def bfs(sx, sy):
    
    
    d = [[-inf]*W for _ in range(H)]
    que = collections.deque()
    que.append([sx, sy])
    d[sx][sy] = 0
    while (len(que) > 0):
        p = que.popleft()
        
        
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W and f[nx][ny] != "
                que.append([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
        if len(p)==0:
            break
    return np.max(d)


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

res = 0
for h1 in range(H):
    for w1 in range(W):
        
        
        if f[h1][w1] == ".":
            
            res = max(res, bfs(h1,w1))
        else:
            continue
print(int(res))

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

inputs = sys.stdin.readlines()
h, w = map(int, inputs[0].split())
S = deque(deque(map(lambda x: int(x=='.'), x)) for x in inputs[1:])
S.appendleft(deque([0]*w))
S.append(deque([0]*w))
for row in S:
    row.appendleft(0)
    row.append(0)

max_dist = 0
for y in range(1, h+1):
    for x in range(1, w+1):
        if S[y][x]:
            maze = deepcopy(S)
            queue = deque([(x, y, 0)])
            while queue:
                x, y, d = queue.popleft()
                d += 1
                maze[y][x] = 0
                for dx, dy in zip([0, 1, 0, -1], [-1, 0, 1, 0]):
                    if maze[y+dy][x+dx]:
                        queue.append((x+dx, y+dy, d))
                        maze[y+dy][x+dx] = 0
                        max_dist = max(max_dist, d)
print(max_dist)