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 = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(input())

ret = 0
for i in range(H):
    for j in range(W):
        s = S[i][j]
        queue = deque([(i,j,0)])
        footprint = [(i,j)]
        if s == '
            continue
        while True:
            x, y, d = queue.popleft()
            for p in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
                if p[0] < 0 or p[0] >= H or p[1] < 0 or p[1] >= W:
                    continue
                if p in footprint:
                    continue
                if S[p[0]][p[1]] == '
                    continue
                queue.append((p[0], p[1], d+1))
                footprint.append(p)

            if len(queue) == 0:
                break
        if d > ret:
            ret = d

print(ret)

Solution (Python):
from collections import deque

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

ret = 0
for i in range(H):
    for j in range(W):
        s = S[i][j]
        queue = deque([(i,j,0)])
        footprint = [(i,j)]
        if s == '
            continue
        while True:
            x, y, d = queue.popleft()
            for p in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
                if p[0] >= 0 and p[0] < H and p[1] >=0 and p[1] < W and p not in footprint and S[p[0]][p[1]] != '
                        queue.append((p[0], p[1], d+1))
                        footprint.append(p)

            if len(queue) == 0:
                break
        if d > ret:
            ret = d

print(ret)

Solution (Python):
from collections import deque

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

ret = 0
for i in range(H):
    for j in range(W):
        s = S[i][j]
        queue = deque([(i,j,0)])
        footprint = [(i,j)]
        if s == '
            continue
        while True:
            x, y, d = queue.popleft()
            for p in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
                if p[0] >= 0 and p[0] < H and p[1] >=0 and p[1] < W and p not in footprint and S[p[0]][p[1]] != '
                        queue.append((p[0], p[1], d+1))
                        footprint.append(p)

            if len(queue) == 0:
                break
        if d > ret:
            ret = d

print(ret)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]
directions = [[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 _ in range(H)]
    dist[sh][sw]=0
    
    que=deque([[sh,sw]])
    
    while que:
      nh,nw=que.popleft()
      
      for dh,dw in directions:
        
        
        if not 0<=nh+dh<=H-1 or not 0<=nw+dw<= W-1:
          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.append([nh+dh,nw+dw])
      
    ans=max(ans, max([max(d) for d in dist]))
    
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 = [readline().rstrip().decode() for _ in range(h)]
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
sg = []
memo = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            sg.append((i, j))
        else:
            memo[i][j] = True
ans = 0
for ss in sg:
    q = [ss]
    cnt = 0
    dist = deepcopy(memo)
    dist[ss[0]][ss[1]] = True
    while q:
        cnt += 1
        qq = []
        for y, x in q:
            for dy, dx in move:
                xx, yy = x + dx, y + dy
                if xx < 0 or yy > h - 1 or yy < 0 or xx > w - 1:
                    continue
                if dist[yy][xx]:
                    continue
                dist[yy][xx] = True
                qq.append((yy, xx))
        q = qq
    ans = max(ans, cnt - 1)
print(ans)

Solution (Python):
from collections import deque

from sys import stdin, setrecursionlimit


def main():
    h, w = map(int, stdin.readline().split())
    g = [list(map(str, list(input()))) for _ in range(h)]

    ans = 0

    for i in range(h):
        for j in range(w):
            if g[i][j] == '.':
                d = [[-1 for _ in range(w)] for _ in range(h)]
                q = deque()

                d[i][j] = 0
                q.append([i, j])

                while q:
                    vi, vj = q.popleft()

                    if vi > 0:
                        if g[vi - 1][vj] == '.' and d[vi - 1][vj] == -1:
                            d[vi - 1][vj] = d[vi][vj] + 1
                            q.append([vi - 1, vj])
                    if vi < h - 1:
                        if g[vi + 1][vj] == '.' and d[vi + 1][vj] == -1:
                            d[vi + 1][vj] = d[vi][vj] + 1
                            q.append([vi + 1, vj])
                    if vj > 0:
                        if g[vi][vj - 1] == '.' and d[vi][vj - 1] == -1:
                            d[vi][vj - 1] = d[vi][vj] + 1
                            q.append([vi, vj - 1])
                    if vj < w - 1:
                        if g[vi][vj + 1] == '.' and d[vi][vj + 1] == -1:
                            d[vi][vj + 1] = d[vi][vj] + 1
                            q.append([vi, vj + 1])
                tmp_max = 0
                for hi in range(h):
                    for wj in range(w):
                        tmp_max = max(tmp_max, d[hi][wj])
                ans = max(ans, tmp_max)

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = [input() for i in range(h)]
def bfs(i0, j0):
    INF = 100
    search = deque([(i0, j0)])
    d = [[INF] * w for i in range(h)]
    d[i0][j0] = 0
    while search:
        i, j = search.popleft()
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.' and d[ni][nj] == INF:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

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

Solution (Python):
h , w = input().split()
h , w = int(h) , int(w)

mp = [ '' for j in range(w * h)]
j = 0

for i in range (h) :
    tmp1 = list(input())
    for j in range (w) :
        mp[w * i + j] = tmp1[j]

def bfs (k) :
    used = [False for i in range(h * w)]
    q = [k]
    used[k] = True
    depth = [0 for i in range (h * w)]

    while len(q) > 0 :
        tmp = q.pop(0)
        if tmp > w - 1 and mp[tmp - w] == '.' and used[tmp - w] == False:
            q.append (tmp - w)
            used[tmp - w] = True
            depth [tmp - w] = depth[tmp] + 1

        if tmp < (h - 1) * w and mp[tmp + w] == '.' and used[tmp + w] == False :
            q.append (tmp + w)
            used[tmp + w] = True
            depth [tmp + w] = depth[tmp] + 1

        if tmp % w != 0 and mp[tmp - 1] == '.' and used[tmp - 1] == False :
            q.append (tmp - 1)
            used[tmp - 1] = True
            depth [tmp - 1] = depth[tmp] + 1

        if (tmp + 1) % w != 0 and mp[tmp + 1] == '.'and used[tmp + 1] == False :
            q.append (tmp + 1)
            used[tmp + 1] = True
            depth [tmp + 1] = depth[tmp] + 1
    
    mx = max(depth)

    return mx

ans = 0 

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

print (ans)

Solution (Python):
from collections import deque

def bfs(h_i, w_i):
    visit = [[0] * w for _ in range(h)]
    visit[h_i][w_i] = 1
    d = deque()
    d.append([h_i, w_i])
    distance = [[0] * w for _ in range(h)]
    while d:
        x, y = d.popleft()
        for i, j in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            if (0 <= x + i <= h - 1) & (0 <= y + j <= w - 1):
                if visit[x + i][y + j] == 0:
                    visit[x + i][y + j] = 1
                    if s[x + i][y + j] == '.':
                        distance[x + i][y + j] = distance[x][y] + 1
                        d.append([x+i, y+j])
    ans = []
    for i in distance:
        ans += i
    return max(ans)

h, w = map(int, input().split())
s = []
for _ in range(h):
    t = list(input())
    s.append(t)
dist = []
for i in range(h * w):
    h_i = i % h
    w_i = i // h
    if s[h_i][w_i] == '.':
        dist.append(bfs(h_i, w_i))
print(max(dist))

Solution (Python):
from collections import deque 
INF = 10000

H,W = map(int,input().split())
S = [list(input()) for i in range(0,H,1)]
S_count=[[INF for j in range(0,W,1)]for i in range(0,H,1)]
task_list = deque([])

def bfs(x,y,count):
    if x<0 or H-1 < x or y < 0 or W-1<y:
        return False
    if S[x][y]=="
        return False
    if S_count[x][y] > count:
        S_count[x][y]=count
        task_list.append([x+1,y,count+1])
        task_list.append([x-1,y,count+1])
        task_list.append([x,y-1,count+1])
        task_list.append([x,y+1,count+1])
        return True

maxi = 0

for i in range(0,H,1):
    for j in range(0,W,1):
        S_count=[[INF for j in range(0,W,1)]for i in range(0,H,1)]
        task_list.append([i,j,0])
        while(len(task_list)):
            X,Y,T = task_list.popleft()
            if bfs(X,Y,T):
                maxi = max(T,maxi)

print(maxi)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
maze = [input() for _ in range(h)]
dires = [(1,0),(0,1),(-1,0),(0,-1)]
ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == "
            continue        
        q = deque()
        q.append((i, j, 0))
        explored = set()
        explored.add((i, j))
        longest = 0
        while q:
            y, x, count = q.popleft()
            for d, r in dires:
                y_ = y+d
                x_ = x+r
                if (y_, x_) in explored or y_ >= h or x_ >= w or y_ < 0 or x_ < 0 or maze[y_][x_] == "
                    continue

                explored.add((y_, x_))
                q.append((y_, x_, count+1))
                longest = max(longest, count+1)

        ans = max(ans, longest)

print(ans)

Solution (Python):
import numpy as np
from scipy.sparse import csgraph
H, W = map(int, input().split())
maze = "".join(input() for _ in range(H))
array = np.zeros((H * W, H * W), dtype=np.bool)
for n in range(H * W):
    if maze[n] == "
        continue
    r, c = divmod(n, W)
    if c and maze[n - 1] == ".":
        array[n][n - 1] = 1
        array[n - 1][n] = 1
    if r and maze[n - W] == ".":
        array[n][n - W] = 1
        array[n - W][n] = 1
dist = csgraph.shortest_path(array)
print(int(dist[dist < 401].max()))

Solution (Python):
import numpy as np
from scipy.sparse import csgraph
H, W = map(int, input().split())
maze = "".join(input() for _ in range(H))
array = np.zeros((H * W, H * W), dtype=np.bool)
for n in range(H * W):
    if maze[n] == "
        continue
    r, c = divmod(n, W)
    if c and maze[n - 1] == ".":
        array[n][n - 1] = 1
    if c != W - 1 and maze[n + 1] == ".":
        array[n][n + 1] = 1
    if r and maze[n - W] == ".":
        array[n][n - W] = 1
    if r != H - 1 and maze[n + W] == ".":
        array[n][n + W] = 1
dist = csgraph.shortest_path(array, directed=False)
print(int(dist[dist < 401].max()))

Solution (Python):
from collections import deque
H,W = map(int,input().split())
S= [[0]* W for _ in range(H)]
for i in range(H):
  S[i] = list("".join(input()))

def BFS(i,j):
  v= deque([[i,j]])
  d= [[-1 for _ in range (W)] for _ in range(H)]
  d[i][j]=0
  
  while len(v)>0:
    a=v.popleft()
    s=a[0]
    t=a[1]
    if s>0:
      if d[s-1][t]==-1 and S[s-1][t]==".":
        d[s-1][t]= d[s][t]+1
        v.append([s-1,t])
    if s<H-1:
      if d[s+1][t]==-1 and S[s+1][t]==".":
        d[s+1][t]= d[s][t]+1
        v.append([s+1,t])
    if t>0:
      if d[s][t-1]==-1 and S[s][t-1]==".":
        d[s][t-1]= d[s][t]+1
        v.append([s,t-1])
    if t<W-1:
      if d[s][t+1]==-1 and S[s][t+1]==".":
        d[s][t+1]= d[s][t]+1
        v.append([s,t+1])
  maxi=0
  for i in range(H):
    for j in range(W):
      maxi=max(maxi,d[i][j])
  
  return maxi

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

Solution (Python):
from collections import deque
H,W = map(int,input().split())
S= [[0]* W for _ in range(H)]
for i in range(H):
  S[i] = list("".join(input()))

def BFS(i,j):
  v= deque([[i,j]])
  d= [[-1 for _ in range (W)] for _ in range(H)]
  d[i][j]=0
  
  while len(v)>0:
    a=v.popleft()
    s=a[0]
    t=a[1]
    if s>0:
      if d[s-1][t]==-1 and S[s-1][t]==".":
        d[s-1][t]= d[s][t]+1
        v.append([s-1,t])
    if s<H-1:
      if d[s+1][t]==-1 and S[s+1][t]==".":
        d[s+1][t]= d[s][t]+1
        v.append([s+1,t])
    if t>0:
      if d[s][t-1]==-1 and S[s][t-1]==".":
        d[s][t-1]= d[s][t]+1
        v.append([s,t-1])
    if t<W-1:
      if d[s][t+1]==-1 and S[s][t+1]==".":
        d[s][t+1]= d[s][t]+1
        v.append([s,t+1])
  maxi=0
  for i in range(H):
    for j in range(W):
      maxi=max(maxi,d[i][j])
  
  return maxi

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

Solution (Python):
h,w = map(int,input().split())
ma = []
for i in range(h):
    ma.append(list(input()))
directions = [[-1,0],[1,0],[0,-1],[0,1]]
ans = []

for j in range(h):
    for k in range(w):
        if ma[j][k] == '
            continue

        bfs = [[-1]*w for _ in range(h)]
        bfs[j][k] = 0
        que = [[j,k]]

        while len(que)>0:
            s,t = que.pop(0)
            for x,y in directions:
                if s+x < 0 or s+x>=h or t+y<0 or t+y>=w:
                    continue
                if ma[s+x][t+y] == '
                    continue
                if bfs[s+x][t+y] != -1:
                    continue
                bfs[s+x][t+y] = bfs[s][t] + 1
                que.append([s+x,t+y])
        
        tmp = 0
        for bf in bfs:
            for b in bf:
                if b>tmp:
                    tmp = b
        ans.append(tmp)
print(max(ans))

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = []

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

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


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = [[False for _ in range(w)] for _ in range(h)]
    check[start[0]][start[1]] = True
    queue = deque([start])
    res = -1
    while len(queue) > 0:
        [x, y, bx, by] = queue.popleft()

        length[x][y] = length[bx][by] + 1
        res = max(res, length[x][y])

        for p in move:
            next_x = x + p[0]
            next_y = y + p[1]
            if (next_x < 0)or(next_x == h)or(next_y < 0)or(next_y == w):
                continue
            if not check[next_x][next_y]:
                check[next_x][next_y] = True
                if maze[next_x][next_y] == ".":
                    queue.append([next_x, next_y, x, y])

    return res


ans = -1

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

print(ans)

Solution (Python):
from collections import deque

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

moves = [[-1,0], [1,0], [0,-1], [0,1]]



min_val = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            continue
        todo = deque([[i,j]])
        
        shortest = [[-10e+10 for _ in range(W)] for _ in range(H)]
        shortest[i][j] = 0
        
        while len(todo) > 0:
            checking = todo.popleft()
            for move in moves:
                if checking[0] + move[0] >= 0 and checking[0] + move[0] < H and checking[1] + move[1] >= 0 and checking[1] + move[1] < W:
                    if shortest[checking[0]+move[0]][checking[1]+move[1]] == -10e+10 and S[checking[0]+move[0]][checking[1]+move[1]] == ".":
                        shortest[checking[0]+move[0]][checking[1]+move[1]] = shortest[checking[0]][checking[1]]+1
                        todo.append([checking[0]+move[0],checking[1]+move[1]])
        if min_val < max([max(row) for row in shortest]):
            min_val = max([max(row) for row in shortest])
print(min_val)

Solution (Python):
DIR = ((0, 1), (0, -1), (1, 0), (-1, 0))

H, W = list (map (int, input().split()))
G = []
for i in range (H) :
    G.append(list (input()))

ans = 0

for i in range (H) :
    for j in range (W) :
        if G[i][j] == '.' :
            use = [[False for ii in range (W)] for jj in range (H)]
            q = [(i, j, 0)]
            use[i][j] = True
            path = 0

            while len (q) :
                node = q.pop(0)
                path = max (path, node[2])
                for k in range (4) :
                    x, y = node[0] + DIR[k][0], node[1] + DIR[k][1]
                    if x < 0 or y < 0 or x >= H or y >= W :
                        continue
                    if use[x][y] or G[x][y] == '
                        continue
                    use[x][y] = True
                    q.append((x, y, node[2] + 1))
            ans = max (ans, path)

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
import sys
def I(): return int(input())  
def Is(): return map(int, input().split())  
def LI(): return list(map(int, input().split()))  
def TI(): return tuple(map(int, input().split()))  
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()  
def LS(): return list(input())  
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(1000000)
MOD = 1000000007
INF = float('inf')

h, w = Is()
maze = LSR(h)

def bfs(sy, sx):
    vmaze = [[INF] * w for _ in range(h)]
    move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    que = deque()
    que.append((sy, sx))
    vmaze[sy][sx] = 0

    while que:
        py, px = que.popleft()
        for ymove, xmove in move:
            ny = py + ymove
            nx = px + xmove
            if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] != '
                vmaze[ny][nx] = vmaze[py][px] + 1
                que.append((ny, nx))

    ret = 0
    for y in range(h):
        for x in range(w):
            if vmaze[y][x] != INF:
                ret = max(ret, vmaze[y][x])
    return ret

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

print(ans)

Solution (Python):
import queue

h, w = map(int, input().split())
s = '
for _ in range(h):
    s += '
s += '

ans = 0
for i in range((w+2)*(h+2)):
    if s[i] == '
        continue
    dist = [10**5]*(w+2)*(h+2)
    dist[i] = 0
    q = queue.Queue()
    q.put(i)
    while not q.empty():
        x = q.get()
        for j in (1, -1, w+2, -w-2):
            if s[j+x] =='
                continue
            if dist[j+x] > dist[x] + 1:
                dist[j+x] = dist[x] + 1
                q.put(j+x)
    for k in range((w+2)*(h+2)):
      if dist[k] != 10**5:
        ans = max(ans, dist[k])

print(ans)

Solution (Python):
import queue

h, w = map(int, input().split())
s = '
for _ in range(h):
    s += '
s += '

ans = 0
for i in range((w+2)*(h+2)):
    if s[i] == '
        continue
    dist = [10**10]*(w+2)*(h+2)
    dist[i] = 0
    q = queue.Queue()
    q.put(i)
    while not q.empty():
        x = q.get()
        for j in (1, -1, w+2, -w-2):
            if s[j+x] =='
                continue
            if dist[j+x] > dist[x] + 1:
                dist[j+x] = dist[x] + 1
                ans = max(ans, dist[j+x])
                q.put(j+x)

print(ans)

Solution (Python):



import copy


h, w = map(int,input().split())
s = list()
init_s = list('
s.append(init_s)

for i in range(h):
    ws = list(input())
    ws.insert(0, '
    ws.append('
    s.append(ws)

s.append(init_s)

q = list()
rflg = True

max_movecnt = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        wk_s = copy.deepcopy(s)
        
        if s[i][j] == '.':
            wk_s[i][j] = '
            init_idx = [i, j]
            q.append(init_idx)
            movecnt = 0
            cntupidx = len(q)
            popcnt = 0
            
            while(len(q) > 0):
                stidx = q.pop(0)
                popcnt = popcnt + 1
                
                if wk_s[stidx[0]-1][stidx[1]] == '.':
                    q.append([stidx[0]-1, stidx[1]])
                    wk_s[stidx[0]-1][stidx[1]] = '
                
                if wk_s[stidx[0]][stidx[1]+1] == '.':
                    q.append([stidx[0], stidx[1]+1])
                    wk_s[stidx[0]][stidx[1]+1] = '
                
                if wk_s[stidx[0]+1][stidx[1]] == '.':
                    q.append([stidx[0]+1, stidx[1]])
                    wk_s[stidx[0]+1][stidx[1]] = '
                
                if wk_s[stidx[0]][stidx[1]-1] == '.':
                    q.append([stidx[0], stidx[1]-1])
                    wk_s[stidx[0]][stidx[1]-1] = '

                if popcnt >= cntupidx:
                    movecnt = movecnt + 1
                    cntupidx = len(q)
                    popcnt = 0

            max_movecnt = max(movecnt-1, max_movecnt)


print(max_movecnt)

Solution (Python):
from collections import deque

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

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

def bfs(sx, sy):
    d = [[-1] * W for _ in range(H)]

    que = deque([])
    que.append((sx, sy))
    d[sy][sx] = 0

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

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if 0 <= nx < W and 0 <= ny < H and d[ny][nx] == -1 and c[ny][nx] == '.':
                que.append((nx, ny))
                tmp = d[y][x] + 1
                d[ny][nx] = tmp
                res = max(res, tmp)

    return res

ans = 0
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = bfs(j, i)
            ans = max(ans, tmp)

print(ans)

Solution (Python):
def main():
  from collections import deque
  H, W = map(int, input().split())
  graph = [['
  for i in range(H):
    S = input()
    for j in range(W):
      graph[i+1][j+1] = S[j]

  def dfs(sx, sy):
    q = deque([(sx, sy)])
    dist = [[-1] * (W+2) for _ in range(H+2)]
    dist[sx][sy] = 0
    s = 0
    while q:
      x, y = q.popleft()
      dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
      for dx, dy in dxy:
        nextx = x+dx
        nexty = y+dy
        if(dist[nextx][nexty] >= 0):
          continue
        if(graph[nextx][nexty] == '
          continue
        dist[nextx][nexty] = dist[x][y] + 1
        q.append((nextx, nexty))
    for i in range(H+2):
      for j in range(W+2):
        if(dist[i][j] >= 0):
          s = max(s, dist[i][j])
    return s

  ans = 0  
  for sx in range(1, H+1):
    for sy in range(1, W+1):
      if(graph[sx][sy] == '.'):
          tmp = dfs(sx, sy)
          ans = max(ans, tmp)
          
  print(ans)
  
main()

Solution (Python):
from collections import deque
from copy import deepcopy
H, W = map(int, input().split())
maze = [[]for i in range(H)]
for i in range(H):
    S = input()
    for j in range(W):
        maze[i].append(S[j])

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
ans = 0
Q = deque()

for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '
            continue
        mazenow = deepcopy(maze)
        Q.clear()
        Q.append((sy, sx))
        mazenow[sy][sx] = 0
        flag = True
        max_maze_now = 0
        while len(Q) > 0:
            y, x = Q.popleft()
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if (ny < 0) or (nx < 0) or (ny >= H) or (nx >= W):
                    continue
                elif mazenow[ny][nx] == '.':
                    mazenow[ny][nx] = mazenow[y][x] + 1
                    max_maze_now = max(max_maze_now, mazenow[ny][nx])
                    Q.append((ny, nx))
        ans = max(max_maze_now, ans)

print(ans)

Solution (Python):
from collections import deque


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

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

    
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 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))
                temp = d[p[0]][p[1]] + 1
                d[nx][ny] = temp
                if temp >= ma:
                  ma = temp
             
    return ma


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

ans = 0
for i in range(n):
  for j in range(m):
    if maze[i][j] != "
      a = bfs(i,j)
      if a >= ans:
        ans = a
    
print(ans)

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

def update(y, x, direction, d, q):
    next_y, next_x = (y + direction[0], x + direction[1])
    if (next_y < 0 or next_y >= H or next_x < 0 or next_x >= W): 
        return
    if (S[next_y][next_x] == '
        return 
    d[next_y][next_x] = d[y][x] + 1
    q.append((next_y, next_x))

def bfs(i, j):
    DIJ = ((-1, 0), (0, -1), (1, 0), (0, 1)) 
    dist = [[-1] * W for _ in range(H)]
    dist[i][j] = 0 

    queue = [(i, j)]
    while queue:
        cur_y, cur_x = queue.pop(0)
        for i in range(4):
            update(cur_y, cur_x, DIJ[i], dist, queue)
    return max(max(dd) for dd in dist)
    
max_results = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '
            max_results = max(bfs(i, j), max_results) 
print(max_results)

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

def update(y, x, direction, d, q):
    next_y, next_x = (y + direction[0], x + direction[1])
    if (next_y < 0 or next_y >= H or next_x < 0 or next_x >= W): 
        return
    if (S[next_y][next_x] == '
        return 
    d[next_y][next_x] = d[y][x] + 1
    q.append((next_y, next_x))

def bfs(i, j):
    DIJ = ((-1, 0), (0, -1), (1, 0), (0, 1)) 
    dist = [[-1] * W for _ in range(H)]
    dist[i][j] = 0 

    queue = [(i, j)]
    while queue:
        cur_y, cur_x = queue.pop(0)
        for i in range(4):
            update(cur_y, cur_x, DIJ[i], dist, queue)
    return max(max(dd) for dd in dist)
    
max_results = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '
            max_results = max(bfs(i, j), max_results) 
print(max_results)

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):
H, W = list(map(int, input().split()))
S = [input() for _ in range(H)]

def update(y, x, direction, d, q, end_pos):
    next_y, next_x = (y + direction[0], x + direction[1])
    if (next_y < 0 or next_y >= H or next_x < 0 or next_x >= W): 
        return end_pos 
    if (S[next_y][next_x] == '
        return end_pos
    d[next_y][next_x] = d[y][x] + 1
    q[end_pos] = (next_y, next_x)
    return end_pos + 1
    
def bfs(i, j):
    DIJ = ((-1, 0), (0, -1), (1, 0), (0, 1)) 
    dist = [[-1] * W for _ in range(H)]
    dist[i][j] = 0 

    wall_num = sum(ss.count('
    queue = [(-1, -1) for _ in range(H * W - wall_num)]
    queue[0] = (i, j)
    queue_end_pos = 1 
    while queue:
        cur_y, cur_x = queue.pop(0)
        queue_end_pos -= 1
        for i in range(4):
            queue_end_pos = \
            update(cur_y, cur_x, DIJ[i], dist, queue, queue_end_pos)
    return max(max(dd) for dd in dist)
    
max_results = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '
            max_results = max(bfs(i, j), max_results) 
print(max_results)