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 math
from queue import Queue
import copy

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

q = Queue()
ans = 0

for y in range(h):
    for x in range(w):
        li = copy.deepcopy(ili)
        if li[y][x] == "
        q.put([x, y])
        li[y][x] = 0
        while not q.empty():
            c = q.get()
            
            for dr in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
                nX = c[0] + dr[0]
                nY = c[1] + dr[1]

                if not (0 <= nX <= w - 1): continue
                if not (0 <= nY <= h - 1): continue

                if li[nY][nX] == ".":
                    li[nY][nX] = li[c[1]][c[0]] + 1
                    q.put([nX, nY])

        li = list(
            map(lambda item: 0 if item == "
                sum(li, [])))
        ans = max(li + [ans])

print(ans)

Solution (Python):
from collections import deque

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

maze = []
for _ in range(H):
    maze.append(list(input()))


def bfs(i, j):
    q = deque([(i, j, 0)])
    seen = set([(i, j)])
    ans = 0
    while q:
        i, j, d = q.popleft()
        ans = max(ans ,d)
        for dx, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            x = i + dx
            y = j + dj
            if 0 <= x < H and 0 <= y < W and maze[x][y] == "." :
                if (x, y) not in seen:
                    seen.add((x, y))
                    q.append((x, y, d + 1))           
    return ans


res = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            res = max(res, bfs(i, j))
print(res)

Solution (Python):









'''
3 5
...
.
.
'''

import sys
from collections import deque

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

H, W = na()


data = [list("

for _ in range(H):
    data.append(["
data += [list("


def bfs(h, w):
    dist = [[-1] * (W+2) for _ in range(H+2)]
    q = deque()

    max_dist = 0
    dist[h][w] = 0
    q.append((h, w, 0))

    
    while len(q) > 0:
        h, w, val = q.popleft()

        m = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for dx, dy in m:
            h_new, w_new = h + dx, w + dy
            if data[h_new][w_new] == '.' and dist[h_new][w_new] == -1:
                q.append((h_new, w_new, val+1))
                dist[h_new][w_new] = val + 1
                max_dist = max(max_dist, val + 1)

    return max_dist


ans = 0
for h in range(H+2):
    for w in range(W+2):
        if data[h][w] == '.':
            res = bfs(h, w)
            if ans < res:
                ans = res

print(ans)

Solution (Python):
from collections import deque
que = deque([])

def bfs(sy,sx):
    d = [[float("inf")] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que.append((sy,sx))
    d[sy][sx] = 0
    route = []
    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0<=ny<H and 0<=nx<W and maze[ny][nx] != "
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
                route.append(d[ny][nx])
    return max(route)

H,W = map(int,input().split())
maze = []
for _ in range(H):
    line = list(input())
    maze.append(line)

M = 0
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] != "
            num = bfs(sy,sx)
            if M <= num:
                M = num
print(M)

Solution (Python):
from collections import deque
  

H,W = map(int, input().split())
s = ["
def bfs(sh,sw):
  if s[sh][sw] == "
    return 0
  queue = deque([(sh,sw)])
  dist = [[-1] * (W+1) for i in range(H+1)]
  dist[sh][sw] = 0
  while queue:
    h,w = queue.popleft()
    d = dist[h][w]
    for i in [h-1,h+1]:
      if s[i][w] == "." and dist[i][w] == -1:
        dist[i][w] = d + 1
        queue.append((i,w))
    for j in [w-1,w+1]:
      if s[h][j] == "." and dist[h][j] == -1:
        dist[h][j] = d + 1
        queue.append((h,j))
          
  max_dist = 0
  for i in dist:
    max_dist = max(max_dist,max(i))
  return max_dist
      

ans = 0          
for i in range(1,H+1):
  for j in range(1,W+1):
    now = bfs(i,j)
    ans = max(ans, now)
print(ans)

Solution (Python):
from collections import deque
from copy import deepcopy
def dfs(world,i,j):
  c=0
  mc=-1
  pos=deque()
  pos.append((i,j,c))
  while pos:
    i,j,c=pos.popleft()
    if world[i][j]=="
      continue
    if world[i+1][j]!="
      pos.append((i+1,j,c+1))
    if world[i-1][j]!="
      pos.append((i-1,j,c+1))
    if world[i][j+1]!="
      pos.append((i,j+1,c+1))
    if world[i][j-1]!="
      pos.append((i,j-1,c+1))
    world[i][j]="
    if mc<c:
      mc=c
  return mc
ans=0
H,W=map(int,input().split())

world=[]
world.append(["
for i in range(H):
  world.append(["
world.append(["


for i in range(H+2):
  for j in range(W+2):
    if world[i][j]==".":
      mc=dfs(deepcopy(world),i,j)
      if ans<mc:
        ans=mc
print(ans)

Solution (Python):
from collections import deque

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


def bfs(maze, visited, sh, sw, H, W):
    q = deque([(sh, sw)])
    visited[sh][sw] = 0
    M = 0
    while q:
        h, w = q.popleft()
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if maze[nh][nw] == "." and visited[nh][nw] == -1:
                    visited[nh][nw] = visited[h][w] + 1
                    q.append((nh, nw))
                    if visited[nh][nw] > M:
                        M = visited[nh][nw]

    return M


ans = 0
for h in range(H):
    for w in range(W):
        if maze[h][w] == "
            continue
        visited = [[-1] * W for _ in range(H)]
        tmp = bfs(maze, visited, h, w, H, W)
        if tmp > ans:
            ans = tmp
print(ans)

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


ans = []
d = [(1,0), (0,1), (-1,0), (0,-1)]
from collections import deque
for i in range(1, h+1):
    for j in range(1, w+1): 
        if s[i][j] == '
            continue
        seen = [[-1 for _ in range(w+2)] for __ in range(h+2)]
        seen[i][j] = 0
        todo = deque([(i, j)])
        num = 0
        while todo != deque([]):
            x, y = todo.popleft()
            for k in d:
                xk = x + k[0]
                yk = y + k[1]
                if seen[xk][yk] == -1 and s[xk][yk] == '.':
                    num = seen[x][y] + 1
                    seen[xk][yk] = num
                    todo.append((xk,yk))
        ans.append(num)
print(max(ans))

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


ans = []
d = [(1,0), (0,1), (-1,0), (0,-1)]
from collections import deque
for i in range(1, h+1):
    for j in range(1, w+1): 
        if s[i][j] == '
            continue
        seen = [[-1 for _ in range(w+2)] for __ in range(h+2)]
        seen[i][j] = 0
        todo = deque([(i, j)])
        num = 0
        while todo != deque([]):
            x, y = todo.popleft()
            for k in d:
                xk = x + k[0]
                yk = y + k[1]
                if seen[xk][yk] == -1 and s[xk][yk] == '.':
                    num = seen[x][y] + 1
                    seen[xk][yk] = num
                    todo.append((xk,yk))
        ans.append(num)
print(max(ans))

Solution (Python):
import copy
from collections import deque

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


def check(tup):
    global H
    global W
    global S

    tup_x=tup[0]
    tup_y=tup[1]
    if 0<=tup_x<H and 0<=tup_y<W:
        if S[tup_x][tup_y]=='.':
            return True
    else:
        return False

def neighbor(tup):
    x=tup[0]
    y=tup[1]
    cand=[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
    List=[]
    for c in cand:
        if check(c):
            List.append(c)
    return List

def bfs(start):
    global H
    global W

    if check(start):
        deq=deque()
        Dict=[]
        component=[]
        for i in range(W):
            component.append(-1)
        for j in range(H):
            Dict.append(copy.copy(component))

        deq.append(start)
        Dict[start[0]][start[1]]=0
        while deq:
            now=deq.popleft()
            nexts=neighbor(now)
            for next in nexts:
                next_x=next[0]
                next_y=next[1]
                if Dict[next_x][next_y]>=0:
                    continue
                
                    
                deq.append(next)
                Dict[next_x][next_y]=Dict[now[0]][now[1]]+1

        M=[]
        for d in Dict:
            M.append(max(d))
        return max(M)
    
    else:
        return 0

Ans=[]
for k in range(H):
    for l in range(W):
        Ans.append(bfs((k,l)))

print(max(Ans))

Solution (Python):
import copy
from collections import deque

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


def check(tup):
    global H
    global W
    global S

    tup_x=tup[0]
    tup_y=tup[1]
    if 0<=tup_x<H and 0<=tup_y<W:
        if S[tup_x][tup_y]=='.':
            return True
    else:
        return False

def neighbor(tup):
    x=tup[0]
    y=tup[1]
    cand=[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
    List=[]
    for c in cand:
        if check(c):
            List.append(c)
    return List

def bfs(start):
    global H
    global W

    if check(start):
        deq=deque()
        Dict=[]
        component=[]
        for i in range(W):
            component.append(-1)
        for j in range(H):
            Dict.append(copy.copy(component))

        deq.append(start)
        Dict[start[0]][start[1]]=0
        while deq:
            now=deq.popleft()
            nexts=neighbor(now)
            for next in nexts:
                next_x=next[0]
                next_y=next[1]
                if Dict[next_x][next_y]>=0:
                    continue
                if next in deq:
                    continue
                deq.append(next)
                Dict[next_x][next_y]=Dict[now[0]][now[1]]+1

        M=[]
        for d in Dict:
            M.append(max(d))
        return max(M)
    
    else:
        return 0

Ans=[]
for k in range(H):
    for l in range(W):
        Ans.append(bfs((k,l)))

print(max(Ans))

Solution (Python):
H, W = map(int, input().split())
maze = []
for _ in range(H):
    maze.append(input())
nodes = []
nodedict = {}
for r in range(H):
    for c in range(W):
        if maze[r][c] == '.':
            node_id = len(nodes)
            nodedict[(r,c)] = node_id
            nodes.append((r,c))
N = len(nodes)
INF = H*W+100
dist = [[INF] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

def connect(r1, c1, r2, c2):
    n1 = nodedict[(r1, c1)]
    n2 = nodedict[(r2, c2)]
    dist[n1][n2] = 1
    dist[n2][n1] = 1

def solve():
    for i in range(N):
        r, c = nodes[i]
        if r > 0 and maze[r-1][c] == '.':
            connect(r, c, r-1, c)
        if r < H-1 and maze[r+1][c] == '.':
            connect(r, c, r+1, c)
        if c > 0 and maze[r][c-1] == '.':
            connect(r, c, r, c-1)
        if c < W-1 and maze[r][c+1] == '.':
            connect(r, c, r, c+1)

    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    maxd = 0
    di, dj = None, None
    for i in range(N):
        for j in range(N):
            d = dist[i][j]
            if d < INF and maxd < d:
                maxd = d
                di = nodes[i]
                dj = nodes[j]
    return maxd  


print(solve())

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

queue = []
visited = [[0 for i in range(w)] for i in range(h)] 
ans = 0

for i in range(h): 
    for j in range(w):
        if C[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            dy_dx = [[1,0],[0,1],[-1,0],[0,-1]] 

            while len(queue) > 0:
                now = queue.pop(0)
                for k in range(4):
                    y = now[0]+dy_dx[k][0]
                    x = now[1]+dy_dx[k][1]
                    if 0 <= y < h and 0 <= x < w:
                        if C[y][x] == '.' and visited[y][x] == 0:
                            visited[y][x] = visited[now[0]][now[1]]+1 
                            queue.append([y,x])
                    
        for l in range(h):
            for m in range(w):
                ans = max(ans,visited[l][m])
            
        queue = []
        visited = [[0 for i in range(w)] for i in range(h)]              
        
print(ans-1)

Solution (Python):
from collections import deque

h,w=map(int,input().split())
maze=[input() for _ in range(h)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
res=0
for sx in range(w):
  for sy in range(h):
    if maze[sy][sx]==".":
      d=[[-1 for _ in range(w)] for _ in range(h)]
      que=deque([[sx,sy]])
      d[sy][sx]=0
      while que:
        x,y=que.popleft()
        for i in range(4):
          nx=x+dx[i]
          ny=y+dy[i]
          if 0<=nx<w and 0<=ny<h and d[ny][nx]==-1 and maze[ny][nx]==".": 
            que.append([nx,ny])
            d[ny][nx]=d[y][x]+1
            if res<d[ny][nx]:
              res=d[ny][nx] 
print(res)

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

h, w = map(int, input().split())
maze = [['*']*(w+2) for j in range(h+2)]
for i in range(1,h+1):
    maze[i][1:] = map(str,list(input()))
    maze[i].append('*')

score = []
def bfs(maze):
    for i in range(1,h+1):
        for l in range(1,w+1):
            if maze[i][l] == '
                continue
            visited = [[-1]*(w+1) for j in range(h+1)]
            queue = deque()
            queue.append([i, l])
            visited[i][l] = 0
            while(queue):
                y, x = queue.popleft()
                for j,k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                    new_x, new_y = x+j, y+k
                    if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
                        queue.append([new_y, new_x])
                        visited[new_y][new_x] = visited[y][x] + 1
            idx = np.unravel_index(np.argmax(np.array(visited)), np.array(visited).shape)
            score.append(np.array(visited)[idx])
    return (max(score))

print(bfs(maze))

Solution (Python):


from queue import Queue

def main():
     h, w = map(int, input().split())
     maze = list()
     ans = -1

     for i in range(h):
          maze.append(list(input()))
     

     for i in range(h):
          for j in range(w):
               ans = max(ans, solver(maze, h, w, i, j))
     
     print(ans)

def solver(maze, h, w, i, j):
     
     if maze[i][j] == '
          return -1

     
     solve = [['inf' for x in range(w)] for y in range(h)]
     check = [[False for x in range(w)] for y in range(h)]
     q = Queue()

     
     solve[i][j] = 0
     q.put((i, j))
     check[i][j] = True

     
     while(not q.empty()):
          
          point = q.get()
          
          
          if point[0] - 1 >= 0:
               target = (point[0] - 1, point[1])
               if maze[target[0]][target[1]] == '.':
                    solve[target[0]][target[1]] = checker(solve[target[0]][target[1]], solve[point[0]][point[1]] + 1)
                    if not check[target[0]][target[1]]:
                         q.put(target)
                         check[target[0]][target[1]] = True

          
          if point[0] + 1 < h:
               target = (point[0] + 1, point[1])
               if maze[target[0]][target[1]] == '.':
                    solve[target[0]][target[1]] = checker(solve[target[0]][target[1]], solve[point[0]][point[1]] + 1)
                    if not check[target[0]][target[1]]:
                         q.put(target)
                         check[target[0]][target[1]] = True

          
          if point[1] - 1 >= 0:
               target = (point[0], point[1] - 1)
               if maze[target[0]][target[1]] == '.':
                    solve[target[0]][target[1]] = checker(solve[target[0]][target[1]], solve[point[0]][point[1]] + 1)
                    if not check[target[0]][target[1]]:
                         q.put(target)
                         check[target[0]][target[1]] = True

          
          if point[1] + 1 < w:
               target = (point[0], point[1] + 1)
               if maze[target[0]][target[1]] == '.':
                    solve[target[0]][target[1]] = checker(solve[target[0]][target[1]], solve[point[0]][point[1]] + 1)
                    if not check[target[0]][target[1]]:
                         q.put(target)
                         check[target[0]][target[1]] = True

     
     

     ret = 0
     for i in range(h):
          line = [x for x in solve[i] if type(x) == int]
          if not len(line) == 0:
               ret = max(ret, max(line))

     return ret


def checker(now, new):
     if now == 'inf':
          return new
     else:
          return min(now, new)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
from copy import deepcopy
def dfs(world,i,j):
  c=0
  mc=-1
  pos=deque()
  pos.append((i,j,c))
  while pos:
    i,j,c=pos.popleft()
    if world[i][j]=="
      continue
    if world[i+1][j]!="
      pos.append((i+1,j,c+1))
    if world[i-1][j]!="
      pos.append((i-1,j,c+1))
    if world[i][j+1]!="
      pos.append((i,j+1,c+1))
    if world[i][j-1]!="
      pos.append((i,j-1,c+1))
    world[i][j]="
    if mc<c:
      mc=c
  return mc
ans=0
H,W=map(int,input().split())

world=[]
world.append(["
for i in range(H):
  world.append(["
world.append(["


for i in range(H+2):
  for j in range(W+2):
    if world[i][j]==".":
      mc=dfs(deepcopy(world),i,j)
      if ans<mc:
        ans=mc
print(ans)

Solution (Python):
from collections import deque

H,W  = [int(v) for v in input().split()]
S = ['
S.insert(0,"
S.append("

ans = 0

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == "
        queue = deque([[x,y,0]])
        visited = [[False] * (W+2) for _ in range(H+2)]
        visited[y][x] = True

        while queue:
            x,y,c = queue.pop()
            for ny,nx in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
                if visited[ny][nx] or S[ny][nx] == '
                visited[ny][nx] = True
                queue.appendleft([nx,ny,c+1])
            ans = max(ans,c)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

h,w = l_in()
S = [s_in() for _ in range(h)]
    
from collections import deque

res = 0
for i in range(h):
    for j in range(w):
        q = deque()
        s = set()
        check = lambda x,y: (not (x,y) in s) and x >= 0 and x < h and y >=0 and y < w and S[x][y] == '.'
        
        if S[i][j] == '.':
            q.append((i,j,0))

        while len(q) > 0:
            i,j,d = q.popleft()
            s.add((i,j))
            res = max(d,res)
            
            if check(i+1,j):
                s.add((i+1,j))
                q.append((i+1,j,d+1))
            if check(i-1,j):
                s.add((i-1,j))                
                q.append((i-1,j,d+1))
            if check(i,j+1):
                s.add((i,j+1))            
                q.append((i,j+1,d+1))
            if check(i,j-1):
                s.add((i,j-1))            
                q.append((i,j-1,d+1))

print(res)

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

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

ans = 0
for h in range(H):
  for w in range(W):
    if maze[h][w] == '
      continue
    d_maze = [[-1]*W for _ in range(H)]
    d_maze[h][w] = 0
    p = deque([[h, w]])
    while p:
      rh, rw =  p.popleft()
      for i, j in dxy:
        nh = rh + i
        nw = rw + j
        if 0 <= nh < H and 0 <= nw < W and maze[nh][nw] == '.' and d_maze[nh][nw] == -1:
          d_maze[nh][nw] = d_maze[rh][rw] + 1
          p.append([nh, nw])
    ans = max(ans, max([max(l) for l in d_maze]))
print(ans)

Solution (Python):
import copy as cp
import sys
from collections import deque


def func(s,i,j):
  dot = 0
  for c in s:
    dot += len(c.replace('
    
  d = deque()
  d.append((i,j,0))
  h = len(s)
  w = len(s[0])
  m = [[-1 for i in range(w)] for j in range(h)]
  
  count = 0
  while True:
    i,j,n = d.popleft()
    if i < 0 or j < 0 or i >= h or j >= w or s[i][j] == '
      continue
    
    m[i][j] = n
    
    d.append((i+1,j,n+1))
    d.append((i,j+1,n+1))
    d.append((i-1,j,n+1))
    d.append((i,j-1,n+1))
    count += 1
    
    if count == dot:
      break
      
  
  ans = 0
  for i in range(len(m)):
    ans = max(ans,max(m[i]))

  return ans

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] == '
      continue
      
    tmp = func(s,i,j)
    ans = max(ans, func(s,i,j))

print(ans)

Solution (Python):
def dfs(h, w): 
    m = -1
    visited = [[-1] * W for _ in range(H)]
    stack = []
    visited[h][w] = 0
    stack.append([h, w])
    while stack:
        h, w = stack.pop()
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if nh >= H or nh < 0 or nw >= W or nw < 0:
                continue
            if s[nh][nw] == "." and visited[nh][nw] == -1:
                visited[nh][nw] = visited[h][w] + 1
                stack.append([nh, nw])
            if s[nh][nw] == "." and visited[nh][nw] != -1:
                if visited[nh][nw] > (visited[h][w]+1):
                    visited[nh][nw] = visited[h][w] + 1
                    stack.append([nh, nw])
    for i in range(H):
        if m <= max(visited[i]):
            m = max(visited[i])
    return m

H, W = map(int, input().split())
s = [input() for _ in range(H)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
m = -1
dist = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            dist = dfs(i, j)
            if m <= dist:
                m = dist
print(m)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
from collections import deque


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

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

count = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != '
            count  = max(count, bfs(i,j))
print(count)

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]
    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    ans = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '
                continue

            goal_dists = [[-1] * W for _ in range(H)]
            goal_dists[h][w] = 0
            d = deque([[h, w]])

            while d:
                ht, wt = d.popleft()
                for dh, dw in directions:
                    if not (0 <= ht+dh < H and 0 <= wt+dw < W):
                        continue
                    if maze[ht+dh][wt+dw] == '
                        continue
                    if goal_dists[ht+dh][wt+dw] == -1:
                        goal_dists[ht+dh][wt+dw] = goal_dists[ht][wt] + 1
                        d.append([ht+dh, wt+dw])
            
            ans = max(ans, max([max(l) for l in goal_dists]))

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def bfs(start, maze, H, W):
    max_step = 0
    used = [[False for _ in range(W)] for _ in range(H)]
    start_x, start_y = start
    used[start_x][start_y] = True
    stack = deque([[start, 0]])
    while stack:
        (i, j), step = stack.popleft()
        if maze[i][j] == '
            continue
        max_step = max(max_step, step)
        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if 0 <= x < H and 0 <= y < W and not used[x][y]:
                stack.append([(x, y), step + 1])
                used[x][y] = True
    return max_step

if __name__ == '__main__':
    H, W = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(input()))
    ret = 0
    for i in range(H):
        for j in range(W):
            ret = max(ret, bfs((i, j), S, H, W))
    print(ret)

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]
    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    ans = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '
                continue

            goal_dists = [[-1] * W for _ in range(H)]
            goal_dists[h][w] = 0
            d = deque([[h, w]])

            while d:
                ht, wt = d.popleft()
                for dh, dw in directions:
                    if not (0 <= ht+dh < H and 0 <= wt+dw < W):
                        continue
                    if maze[ht+dh][wt+dw] == '
                        continue
                    if goal_dists[ht+dh][wt+dw] == -1:
                        goal_dists[ht+dh][wt+dw] = goal_dists[ht][wt] + 1
                        d.append([ht+dh, wt+dw])
            
            ans = max(ans, max([max(l) for l in goal_dists]))

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]

    ans = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '
                continue

            goal_dists = [[-1] * W for _ in range(H)]
            goal_dists[h][w] = 0
            d = deque([[h, w]])

            while d:
                ht, wt = d.popleft()
                for dh, dw in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    if not (0 <= ht+dh < H and 0 <= wt+dw < W):
                        continue
                    if maze[ht+dh][wt+dw] == '
                        continue
                    if goal_dists[ht+dh][wt+dw] == -1:
                        goal_dists[ht+dh][wt+dw] = goal_dists[ht][wt] + 1
                        d.append([ht+dh, wt+dw])
            
            ans = max(ans, max([max(l) for l in goal_dists]))

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]

    ans = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '
                continue
            goal_dists = [[-1] * W for _ in range(H)]
            goal_dists[h][w] = 0
            d = deque([[h, w]])

            while d:
                ht, wt = d.popleft()
                for dh, dw in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    if not (0 <= ht+dh < H and 0 <= wt+dw < W):
                        continue
                    if maze[ht+dh][wt+dw] == '
                        continue
                    if goal_dists[ht+dh][wt+dw] == -1:
                        goal_dists[ht+dh][wt+dw] = goal_dists[ht][wt] + 1
                        d.append([ht+dh, wt+dw])
            
            max_dist = [max(goal_dists[h]) for h in range(H)]
            ans = max(ans, max(max_dist))

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
import copy
INF = 20 * 20 + 1

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]

    ans = 0
    goal_base = [[-1 for _ in range(W+2)] for _ in range(H)]
    goal_base = [[-1 for _ in range(W+2)]] + goal_base + [[-1 for _ in range(W+2)]]
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '
                goal_base[h+1][w+1] = -1
            else:
                goal_base[h+1][w+1] = INF

    for hs in range(H):
        for ws in range(W):
            if maze[hs][ws] == '
                continue

            goal_dists = copy.deepcopy(goal_base)
            goal_dists[hs+1][ws+1] = 0
            d = deque([[hs+1, ws+1]])
            while len(d) > 0:
                ht, wt = d.popleft()
                dist = goal_dists[ht][wt]
                for dh, dw in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    if goal_dists[ht+dh][wt+dw] == INF:
                        goal_dists[ht+dh][wt+dw] = dist + 1
                        d.append([ht+dh, wt+dw])
            
            max_dist = [goal_dists[h][w] for w in range(1, W+2) for h in range(1, H+2) if goal_dists[h][w] != INF]
            ans = max(ans, max(max_dist))

    print(ans)

if __name__ == "__main__":
    main()