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

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

def f(h,w): 
  if S[h][w] == '
    return 0
  else:
    d = [[-1]*W for i in range(H)]
    d[h][w] = 0
    
    q = deque([[h,w]])
    
    while q:
      nh,nw = q.pop()
      
      for dh,dw in directions:
        if not (0<=nh+dh<H and 0<=nw+dw<W):
          continue
        if S[nh+dh][nw+dw] == '
          continue
        if d[nh+dh][nw+dw] != -1:
          continue
        d[nh+dh][nw+dw] = d[nh][nw]+1
        q.appendleft([nh+dh,nw+dw])
     
    return max([max(i) for i in d])

a = 0
for h in range(H):
  for w in range(W):
    a = max(a,f(h,w))
    
print(a)

Solution (Python):
from collections import deque

h,w=map(int,input().split())
S=[]
pos=[]
for i in range(h):
  l=input()
  L=[]
  for j in range(w):
    if l[j]=='.':
      L.append('.')
      pos.append((i,j))
    else:
      L.append('
  S.append(L)
Maze=[[float('inf')]*w for i in range(h)]
def bfs(h,w,S,Maze,sy,sx):
    maze=Maze
    maze=[[float('inf')]*w for i in range(h)]
    maze[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)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<=h-1 and 0<=nextx<=w-1:
              dist=maze[nexty][nextx]
              if S[nexty][nextx]!='
                if dist>maze[y][x]+1: 
                    maze[nexty][nextx]=maze[y][x]+1
                    que.append([nexty,nextx])
    m=0
    for i in range(h):
      for j in range(w):
        if maze[i][j]!=float('inf'):
          if m<maze[i][j]:
            m=maze[i][j]
            
    return m
        
M=0
for (sy,sx) in pos:
  if bfs(h,w,S,Maze,sy,sx)>M:
    M=bfs(h,w,S,Maze,sy,sx)

print(M)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from itertools import product

h, w = map(int, input().split())
s = np.full((h, w), 'x', dtype='U1')
for i in range(h):
    s[i] = list(input())

d = np.identity(h * w, dtype='i1')
for i, k in product(range(h), range(w)):
    if s[i, k] == '
        continue
    for dy, dx in ((-1, 0), (0, -1), (0, 1), (1, 0)):
        y, x = i + dy, k + dx
        if y < 0 or h <= y or x < 0 or w <= x or s[y, x] == '
            continue
        d[i*w+k, y*w+x] = 1
        d[y*w+x, i*w+k] = 1

print(floyd_warshall(d).astype('i8').max())

Solution (Python):
import queue

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

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if a[i][j]=='.':
            d = [[-1 for j in range(w)] for i in range(h)]
            q = queue.Queue()
            q.put([i,j])
            d[i][j]=0
            while 1:
                y,x = q.get()
                for dy,dx in move:
                    if 0<=y+dy<h and 0<=x+dx<w:
                        if a[y+dy][x+dx]=='.' and d[y+dy][x+dx]==-1:
                            q.put([y+dy,x+dx])
                            d[y+dy][x+dx]=d[y][x]+1
                if q.empty():
                    ans = max(ans,d[y][x])
                    break

print(ans)

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

H, W = map(int, input().split())
S = np.full((H, W), 'x', dtype='U1')
for i in range(H):
    S[i] = list(input())

def bfs(x, y):
    dist = np.full((H, W), -1, dtype='i8')
    que = deque()

    dist[x, y] = 0
    que.append((x, y))

    while que:
        h, w = que.popleft()
        d = dist[h, w]
        for dx, dy in ((0, -1), (-1, 0), (1, 0), (0, 1)):
            hh, ww = h + dx, w + dy
            if hh < 0 or H <= hh or ww < 0 or W <= ww or S[hh, ww] == '
                continue
            dist[hh, ww] = d + 1
            que.append((hh, ww))

    return d

res = 0
for i, k in product(range(H), range(W)):
    if S[i, k] == '
        continue
    d = bfs(i, k)
    if d > res:
        res = d
print(res)

Solution (Python):
import numpy as np
H, W = map(int, input().split())
mp = np.array([list(input()) for _ in range(H)], dtype=str)

import queue
q = queue.Queue()
visit = (mp == "

def can_visit(x, y):
    """訪問可能ならTrue。壁、既訪問、世界外ならFalse"""
    if x < 0 or y < 0 or x >= W or y >= H:
        return False
    return not visit[y, x]

def push_neighbor(x, y, d):
    """隣接マスをキューにpush"""
    lis = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
    for nx, ny in lis:
        if can_visit(nx, ny):
            q.put((nx, ny, d+1))
            visit[ny, nx] = True

def furthest(sx, sy):
    """位置(sx, sy)から見て一番遠い場所までの距離"""
    
    global visit
    visit = (mp == "
    if visit[sy, sx]:
        return 0
    visit[sy, sx] = True
    
    q.put((sx, sy, 0))
    while not q.empty():
        x, y, d = q.get()
        push_neighbor(x, y, d)
    return d

dist = max([furthest(sx, sy) for sx in range(W) for sy in range(H)])
print(dist)

Solution (Python):
from queue import Queue
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

q = Queue()
searched = [[False for _ in range(W)] for __ in range(H)]
dist = [[-1 for _ in range(W)] for __ in range(H)]

def bfs(x, y, d):
    if not (0 <= x < W and 0 <= y < H):
        return
    if S[y][x] == '
        return
    if searched[y][x]:
        return
    searched[y][x] = True
    dist[y][x] = d
    q.put([x, y, d])
    return

ans = 0
for s_y in range(H):
    for s_x in range(W):
        if S[s_y][s_x] == '
            continue
        
        q = Queue()
        searched = [[False for _ in range(W)] for __ in range(H)]
        dist = [[-1 for _ in range(W)] for __ in range(H)]
        
        dist[s_y][s_x] = 0
        searched[s_y][s_x] = True
        
        q.put([s_x, s_y, 0])
        
        while not q.empty():
            x, y, d = q.get()
            bfs(x-1, y, d+1)
            bfs(x+1, y, d+1)
            bfs(x, y-1, d+1)
            bfs(x, y+1, d+1)
        
        dist_max = max(list(map(lambda x: max(x), dist)))
        ans = max(ans, dist_max)

print(ans)

Solution (Python):
from collections import deque

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

S = [['
for _ in range(H):
    tmp = ['
    S.append(tmp)
S.append(['

move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

ans = 0

for X in range(1, H + 1):
    for Y in range(1, W + 1):
        if S[X][Y] == '
            continue
        check = [[-1] * (W + 2) for _ in range(H + 2)]
        check[X][Y] = 0
        que = deque()
        que.append([X, Y])
        while que:
            tmp = que.popleft()
            x = tmp[0]
            y = tmp[1]
            flag = True
            for dx, dy in move:
                nx = x + dx
                ny = y + dy
                if S[nx][ny] == '.' and check[nx][ny] == -1:
                    que.append([nx, ny])
                    check[nx][ny] = check[x][y] + 1
                    flag = False
            if flag:
                ans = max(ans, check[x][y])


print (ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
Maze = [list(input()) for _ in range(H)]
ans = 0
sy = 0
while sy < H:
  sx = 0
  while sx < W:
    if Maze[sy][sx] == ".":
      M_cnt = 0
      q = deque()
      memo = [[-1]*(W) for _ in range((H))]
      memo[sy][sx] = 0
      q.append([sy, sx])
      while q:
        cy, cx = q.popleft()
        for ny, nx in zip((cy, cy, cy+1, cy-1) , (cx+1, cx-1, cx, cx)):
          if ny >= 0 and ny < H and nx >= 0 and nx < W and Maze[ny][nx] == "." and memo[ny][nx] < 0:
            q.append([ny, nx])
            memo[ny][nx] = memo[cy][cx] + 1
      ans = max(ans, max([max(m)  for m in memo]))
    sx += 1
  sy += 1
print(ans)

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


def f(i, j):
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


result = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '
            result = max(result, f(i, j))
print(result)

Solution (Python):
from collections import deque

def bfs():
    d = [[10**3] * w for i in range(h)]

    
    dh = [1, 0, -1, 0]
    dw = [0, 1, 0, -1]

    global sh
    global sw
    que = deque([])
    que.append((sh, sw))
    d[sh][sw] = 0
    chk = []
    
    while que:
        
        p = que.popleft()
        
        for i in range(4):
            
            nh = p[0] + dh[i]
            nw = p[1] + dw[i]

            
            if 0 <= nh < h and 0 <= nw < w and maze[nh][nw] != "
                
                que.append((nh, nw))
                d[nh][nw] = d[p[0]][p[1]] + 1
                
    return d[p[0]][p[1]]

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
maze = tuple(maze)

res = set()

for i in range(h):
  for j in range(w):
      if maze[i][j] == ".":
          sh = i
          sw = j
          res.add(bfs())
          
print(max(res))

Solution (Python):
import numpy as np
H, W = map(int, input().split())
mp = np.array([list(input()) for _ in range(H)], dtype=str)

import queue
q = queue.Queue()
visit = (mp == "

def can_visit(x, y):
    """訪問可能ならTrue。壁、既訪問、世界外ならFalse"""
    if x < 0 or y < 0 or x >= W or y >= H:
        return False
    return not visit[y, x]

def push_neighbor(x, y, d):
    """隣接マスをキューにpush"""
    lis = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
    for nx, ny in lis:
        if can_visit(nx, ny):
            q.put((nx, ny, d+1))
            visit[ny, nx] = True

def furthest(sx, sy):
    """位置(sx, sy)から見て一番遠い場所までの距離"""
    
    global visit
    visit = (mp == "
    if visit[sy, sx]:
        return 0
    visit[sy, sx] = True
    
    q.put((sx, sy, 0))
    while not q.empty():
        x, y, d = q.get()
        push_neighbor(x, y, d)
    return d

dist = max([furthest(sx, sy) for sx in range(W) for sy in range(H)])
print(dist)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy

h, w = map(int, readline().split())
s = [input() for i in range(h)]
q = []
start = []
ans = 0
dist = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] != '
            start.append([i, j])
        else:
            dist[i][j] = True
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while start:
    check = deepcopy(dist)
    s_y, s_x = start.pop()
    check[s_y][s_x] = True
    q = [(s_y, s_x)]
    cnt = -1
    while q:
        cnt += 1
        qq = []
        for y, x in q:
            for dy, dx in test:
                yy, xx = y + dy, x + dx
                if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1 or check[yy][xx]:
                    continue
                else:
                    check[yy][xx] = True
                    qq.append((yy, xx))
        q = qq
    ans = max(ans, cnt)
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy

h, w = map(int, readline().split())
s = [input() for i in range(h)]
q = []
start = []
dist = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] != '
            start.append([i, j])
        else:
            dist[i][j] = True
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
ans = 0
while start:
    check = deepcopy(dist)
    q = [start.pop()]
    check[q[0][0]][q[0][1]] = True
    q[0] = tuple(q[0])
    cnt = -1
    while q:
        cnt += 1
        qq = []
        for y, x in q:
            for dy, dx in test:
                yy, xx = y + dy, x + dx
                if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1 or check[yy][xx]:
                    continue
                else:
                    check[yy][xx] = True
                    qq.append((yy, xx))
        q = qq
    ans = max(ans, cnt)
else:
    print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy

h, w = map(int, readline().split())
s = [input() for i in range(h)]
q = []
start = []
dist = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] != '
            start.append((i, j))
        else:
            dist[i][j] = True
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
ans = []
while start:
    check = deepcopy(dist)
    q = [start.pop()]
    check[list(q)[0][0]][list(q)[0][1]] = True
    cnt = -1
    while q:
        cnt += 1
        qq = []
        memo = len(q)
        memo_cnt = 0
        for y, x in q:
            for dy, dx in test:
                yy, xx = y + dy, x + dx
                if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1 or check[yy][xx]:
                    memo_cnt += 1
                    continue
                else:
                    check[yy][xx] = True
                    qq.append((yy, xx))
        q = qq
    ans.append(cnt)
else:
    print(max(ans))

Solution (Python):
def warshal_floyd(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d


H, W = list(map(int, input().split()))
maze = [[0 for _ in range(W)] for _ in range(H)]
location = []
for i in range(H):
    for j, s in enumerate(list(input())):
        s = 1 if s == '.' else 0
        maze[i][j] = s
        location.append((i,j))


d = [[float('inf') for _ in range(H*W)] for _ in range(H*W)]


for i in range(H*W):
    for j in range(H*W):
        
                 
        
        if i == j:
            d[i][j] = 0

        
        x_i, y_i = location[i]
        x_j, y_j = location[j]
        
        if abs(x_i - x_j) + abs(y_i - y_j) == 1 and abs(x_i - x_j) * abs(y_i - y_j) == 0:
            
            if maze[x_i][y_i] == 1 and maze[x_j][y_j] == 1:
                d[i][j] = 1

d = warshal_floyd(d, H*W)

m = 0
for i in range(H * W):
    for j in range(H * W):
        if d[i][j] != float('inf'):
            m = max(m, d[i][j])

print(m)

Solution (Python):
from collections import deque
d = [(-1,0),(1,0),(0,1),(0,-1)]

def bfs(y,x,c):
    q =  deque()
    q.append((y,x,c))
    ma = 0
    visit[y][x] = 1
    while q:
        y,x,c = q.popleft()
        ma = max(ma,c)
        for dy,dx in d:
            if 0<=y+dy<h and 0<=x+dx<w:
                if area[y+dy][x+dx] =="." and visit[y+dy][x+dx] == 0:
                    q.append((y+dy,x+dx,c+1))
                    visit[y+dy][x+dx] = 1
    return ma

h,w = map(int,input().split())
area = []
for i in range(h):
    area.append(list(input()))
ans = 0
for i in range(h):
    for j in range(w):
        if area[i][j] ==".":
            visit = [[0]*w for i in range(h)]
            ans = max(ans,bfs(i,j,0))
print(ans)

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


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = -np.ones((H+2, W+2), dtype=np.int64)
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if depth[ny][nx] == -1 and S[ny][nx] == '.':
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['
    for _ in range(H):
        buf = input()
        S.append(list('
    S.append(['

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

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


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = np.full((H+2, W+2), -1, dtype=np.int)
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if depth[ny][nx] == -1 and S[ny][nx] == '.':
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['
    for _ in range(H):
        buf = input()
        S.append(list('
    S.append(['

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['
    for _ in range(H):
        buf = input()
        S.append(list('
    S.append(['

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Solution (Python):
n,m = map(int,input().split())
maze = [list(input()) for i in range(n)]

from collections import deque



def bfs(i,k):
    
    d = [[float("inf")] * m for i in range(n)]

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












    
    que = deque([])
    que.append((i, k))
    d[i][k] = 0

    
    ans = 0
    while que:
        
        p = que.popleft()



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

            
            
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "
                
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
                ans = max(ans, d[p[0]][p[1]] + 1)

    return ans

result = 0
for i, row in enumerate(maze):
    for k, element in enumerate(row):
        if element =='.':
            result = max(result, bfs(i,k))
print(result)

Solution (Python):
from collections import deque

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

max_move = 0
for start_i in range(h):
  for start_j in range(w):
    if maze[start_i][start_j] == '.':
      queue = deque([(0, start_i, start_j)])
      yet = [[True] * w for _ in range(h)]
      yet[start_i][start_j] = False
      while queue:
        move, i, j = queue.popleft()
        if i != 0 and maze[i-1][j] == '.' and yet[i-1][j]:
          queue.append((move + 1, i - 1, j))
          yet[i-1][j] = False
        if i != h - 1 and maze[i+1][j] == '.' and yet[i+1][j]:
          queue.append((move + 1, i + 1, j))
          yet[i+1][j] = False
        if j != 0 and maze[i][j-1] == '.' and yet[i][j-1]:
          queue.append((move + 1, i, j - 1))
          yet[i][j-1] = False
        if j != w - 1 and maze[i][j+1] == '.' and yet[i][j+1]:
          queue.append((move + 1, i, j + 1))
          yet[i][j+1] = False
      if move > max_move:
        max_move = move

print(max_move)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
work = [[[] for j in range(w)] for i in range(h)]
result = 0
for i in range(h):
    for j in range(w):
        append = work[i][j].append
        if i<h-1 and s[i+1][j] == ".":
            append([i+1,j])
        if i>0 and s[i-1][j] == ".":
            append([i-1,j])
        if j<w-1 and s[i][j+1] == ".":
            append([i,j+1])
        if j>0 and s[i][j-1] == ".":
            append([i,j-1])
q = deque()
popleft = q.popleft
append = q.append
for i in range(h):
    for j in range(w):
        if s[i][j] != ".":
            continue
        q.clear()
        q.append([i, j])
        temp = [[i, j]]
        tempappend = temp.append
        d = -1
        count = 1
        counter = 0
        for k in range(w*h):
            x, y = popleft()
            count -= 1
            for el in work[x][y]:
                if el not in temp:
                    counter += 1
                    append(el)
                    tempappend(el)
            if count == 0:
                d += 1
                count = counter
                counter = 0
            if len(q) == 0:
                break
        result = result if result>d else d
    if result == h+w-2:
        break
print(result)

Solution (Python):
from collections import deque

def bfs(maze, visited, sy, sx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    ans=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 maze[new_y][new_x] == "." and visited[new_y][new_x]==-1:
                visited[new_y][new_x]=visited[y][x]+1
                ans=max(ans,visited[new_y][new_x])
                queue.append([new_y,new_x])
    return ans
    
def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="
    maze.appendleft("
    maze.append("
    return list(maze)
    
h,w=map(int,input().split())
maze=[input() for _ in range(h)]
maze=make_wall(maze,h,w)
ans=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if maze[i][j]=="
            continue
        visited=[[-1]*(w+2) for _ in range(h+2)]
        tmp=bfs(maze, visited, i, j)
        ans=max(ans,tmp)
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
g = [list(input()) for i in range(H)]
direction = [[0,1],[1,0],[0,-1],[-1,0]]
ans=0
for sh in range(H):
    for sw in range(W):
        
        if g[sh][sw]=="
            continue
        dist=[[-1]*W for i in range(H)]
        dist[sh][sw] = 0
        que = deque([[sh,sw]])

        while que:
            nh, nw = que.pop()
            for dh, dw in direction:
                if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
                    continue
                if g[nh+dh][nw+dw]=="
                    continue
                if dist[nh+dh][nw+dw]!=-1:
                    continue
                
                
                
                dist[nh + dh][nw + dw] = dist[nh][nw] + 1
                que.appendleft([nh + dh, nw + dw])
        ans = max (ans, max([max(d) for d in dist]))
print(ans)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**8)
INF = float('inf')



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

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

ans = 0
for y in range(h):
  for x in range(w):
    if maze[y][x] == '.':
      ans = max(ans, bfs(y,x))
print(ans)

Solution (Python):
import queue
from itertools import product

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

ans=-1

def bfs(start):
    distance=[[-1]*H for j in range(W)]
    li_x=[1,-1,0,0]
    li_y=[0,0,1,-1]
    q = queue.Queue()
    q.put(start)
    distance[start[0]][start[1]]=0

    while not q.empty():
        hoge=q.get()
        x=hoge[0]
        y=hoge[1]
        dis=distance[x][y]

        for i in range(4):
            x1=x+li_x[i]
            y1=y+li_y[i]
            if (0 <=x1 < W and 0 <= y1 < H):
                if distance[x1][y1] == -1:
                    if S[y1][x1]=='.':
                        q.put([x1,y1])
                        distance[x1][y1]=dis+1
    m=[]
    for i in range(W):
        m.extend(distance[i])
    return max(m)

for sx,sy in product(range(W),range(H)):

                if S[sy][sx]=='.':
                    re=bfs([sx,sy])
                    if re > ans:
                        ans=re

print(ans)

Solution (Python):
from collections import deque
import sys
import math
import io

    
H, W = map(int, input().split())
grid = '
for _ in range(H):
    grid += '
grid += '
move = [1, -1, W+2, -W-2]
    
def bfs(start):
    lst = [10**9] *((H+2)*(W+2))
    lst[start] = 0
    q = deque([start])
    while q:
        x = q.popleft()
        dx = lst[x]
        for d in move:
            y = x + d
            if grid[y] == '
                continue
            dy = dx + 1
            if dy >= lst[y]:
                continue
            lst[y] = dy
            q.append(y)
    return max(x for x in lst if x < 10**9)
    
    
print(max(bfs(i) for i in range((H+2)*(W+2)) if grid[i] != '

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

h, w = na()
maze = nsn(h)

def bfs(sx, sy):
    q = deque()
    q.append((sx, sy))
    dist = [[inf] * w for _ in range(h)]
    dist[sy][sx] = 0
    dx, dy = [1, 0, 0, -1], [0, 1, -1, 0]
    res = 0
    while len(q):
        p = q.popleft()
        cx, cy = p
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if nx < 0 or nx >= w:
                continue
            if ny < 0 or ny >= h:
                continue
            if dist[ny][nx] != inf:
                continue
            if maze[ny][nx] == '
                continue
            update = dist[cy][cx] + 1
            dist[ny][nx] = update
            res = max(res, update)
            q.append((nx, ny))
    
    return res

def main():
    ans = 0

    for y in range(h):
        for x in range(w):
            if maze[y][x] == '
                continue
            ans = max(ans, bfs(x, y))

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

h, w = na()
maze = nsn(h)

def bfs(sx, sy):
    q = deque()
    q.append((sx, sy))
    dist = [[inf] * w for _ in range(h)]
    dist[sy][sx] = 0
    dx, dy = [1, 0, 0, -1], [0, 1, -1, 0]
    res = 0
    while len(q):
        p = q.popleft()
        cx, cy = p
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if nx < 0 or nx >= w:
                continue
            if ny < 0 or ny >= h:
                continue
            if dist[ny][nx] != inf:
                continue
            if maze[ny][nx] == '
                continue
            update = dist[cy][cx] + 1
            dist[ny][nx] = update
            res = max(res, update)
            q.append((nx, ny))
    
    return res

ans = 0

for y in range(h):
    for x in range(w):
        if maze[y][x] == '
            continue
        ans = max(ans, bfs(x, y))

print(ans)

Solution (Python):
from collections import namedtuple
from queue import Queue
from copy import deepcopy

def bfs(start, stage):
    if stage[start.y][start.x] == "
        return -1
    ans = 0
    q = Queue()
    q.put(start)
    stage[start.y][start.x] = 0
    while not q.empty():
        current = q.get()
        for move in moves:
            nxt = point(current.y + move.y, current.x + move.x)
            can_move = 0 <= nxt.y < h and 0 <= nxt.x < w and stage[nxt.y][nxt.x] == "."
            if can_move:
                q.put(nxt)
                stage[nxt.y][nxt.x] = stage[current.y][current.x] + 1
                ans = stage[current.y][current.x] + 1
    return ans


point = namedtuple("point", "y, x")
moves = [point(-1, 0), point(0, 1), point(1, 0), point(0, -1)]
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
ans = -1
for y in range(h):
    for x in range(w):
        steps = bfs(point(y, x), deepcopy(S))
        ans = max(ans, steps)
print(ans)