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 queue

def bfs(start):
  d_mat = [[-1]*(w+2) for i in range(h+2)]
  q.put(start)
  d_mat[start[0]][start[1]] = 0
  while not q.empty():
    x, y = q.get()
    d = d_mat[x][y]
    if mat[x-1][y] == "." and d_mat[x-1][y] == -1:
      d_mat[x-1][y] = d+1
      q.put((x-1, y))
    
    if mat[x+1][y] == "." and d_mat[x+1][y] == -1:
      d_mat[x+1][y] = d+1
      q.put((x+1, y))
    
    if mat[x][y-1] == "." and d_mat[x][y-1] == -1:
      d_mat[x][y-1] = d+1
      q.put((x, y-1))
    
    if mat[x][y+1] == "." and d_mat[x][y+1] == -1:
      d_mat[x][y+1] = d+1
      q.put((x, y+1))
  return d_mat[x][y]
h, w = map(int, input().split())
mat = ["
for y in range(h):
  mat.append("
mat.append("

d_mat1 = [[-1]*(w+2) for i in range(h+2)]
d_mat2 = [[-1]*(w+2) for i in range(h+2)]
q = queue.Queue()
start_list = []
flag = True
for x in range(1, w+1):
  if flag:
    for y in range(1, h+1):
      if mat[y][x] == ".":
        start = (y, x)
        start_list.append(start)
        
q.put(start)

while not q.empty():
  x, y = q.get()
  d = d_mat1[x][y]
  if mat[x-1][y] == "." and d_mat1[x-1][y] == -1:
    d_mat1[x-1][y] = d+1
    q.put((x-1, y))
    
  if mat[x+1][y] == "." and d_mat1[x+1][y] == -1:
    d_mat1[x+1][y] = d+1
    q.put((x+1, y))
    
  if mat[x][y-1] == "." and d_mat1[x][y-1] == -1:
    d_mat1[x][y-1] = d+1
    q.put((x, y-1))
    
  if mat[x][y+1] == "." and d_mat1[x][y+1] == -1:
    d_mat1[x][y+1] = d+1
    q.put((x, y+1))



print(max(list(map(bfs, start_list))))

Solution (Python):
from collections import deque

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

start=[[j,i] for i in range(W) for j in range(H)]
res=0

for pt in start:
    v=[[0]*W for _ in range(H)]
    if S[pt[0]][pt[1]]=='
        continue
    q=deque([pt+[0]])
    dist=0

    while len(q)>0:
        h,w,cnt=q.popleft()
        
        if v[h][w]==1:
            continue
        else:
            v[h][w]=1

        dist=max(dist,cnt)

        for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
            nh=h+dh
            nw=w+dw
            if 0>nh or nh>=H or 0>nw or nw>=W or S[nh][nw]=='
                continue
            q.append([nh,nw,cnt+1])
    
    res=max(res,dist)

print(res)

Solution (Python):
h,w = map(int,input().split())
s = [0] * h
for i in range(h):
    s[i] = str(input())

def warshall_floyd(d):
    
    for k in range(w*h):
        for i in range(w*h):
            for j in range(w*h):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


d = [[float("inf")] * (h * w) for i in range((h * w))]

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            a = i * w + j
            d[a][a] = 0
            for m, n in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                ss = i + m
                t = j + n
                if 0 <= ss <= h-1 and 0 <= t <= w-1 and s[ss][t] == '.':
                    b = ss * w + t
                    d[a][b] = 1
                    d[b][a] = 1
     
ans = 0
box = warshall_floyd(d)
for i in range(h * w):
    for j in range(h*w):
        if box[j][i] > 1000000:
            box[j][i] = 0
        ans = max(ans,box[j][i])

print(ans)

Solution (Python):
import heapq
H, W = map(int, input().split())
area = ['
for i in range(H):
    area += ['
area += ['
H+=2
W+=2
move = [-1, 1, W, -W]
ans = 0
for i in range(H):
    for j in range(W):
        st = W*i+j
        if area[st]=='
        hq = []
        dist = [-1]*(H*W)
        dist[st] = 0
        heapq.heappush(hq, (0, st))
        while hq:
            cost, now = heapq.heappop(hq)
            for dx in move:
                nxt = now+dx
                if dist[nxt]>=0 or area[nxt]=='
                dist[nxt] = dist[now] + 1
                ans = max(ans, dist[nxt])
                heapq.heappush(hq, (dist[nxt], nxt))
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
area = ['
for i in range(H):
    area += ['
area += ['
H+=2
W+=2
move = [-1, 1, W, -W]
ans = 0
for i in range(H):
    for j in range(W):
        st = W*i+j
        if area[st]=='
        dq = deque([])
        dist = [-1]*(H*W)
        dq.append(st)
        dist[st] = 0
        while dq:
            now = dq.popleft()
            for dx in move:
                nxt = now+dx
                if dist[nxt]>=0 or area[nxt]=='
                dist[nxt] = dist[now]+1
                ans = max(ans, dist[nxt])
                dq.append(nxt)
print(ans)

Solution (Python):

import sys
import queue

INF = 10 ** 10

def solve(H: int, W: int, S: list):

    
    h_move = [0, 1, 0, -1]
    w_move = [1, 0, -1, 0]

    max_distance = 0
    for h_start in range(H):
        for w_start in range(W):
            if  S[h_start][w_start] != ".":
                continue
            distance = []
            for _ in range(H):
                l = [INF] * W
                distance.append(l)
            q = queue.Queue()
            q.put((h_start, w_start)) 
            distance[h_start][w_start] = 0

            while not q.empty():
                h, w = q.get()
                for i in range(4):
                    h_next = h + h_move[i]
                    w_next = w + w_move[i]
                    
                    if (h_next < 0 or h_next >= H or w_next < 0 or w_next >= W or S[h_next][w_next] != "." or distance[h_next][w_next] != INF):
                        continue
                    q.put((h_next, w_next))
                    distance[h_next][w_next] = min(distance[h][w] + 1, distance[h_next][w_next])
                    max_distance = max(max_distance, distance[h_next][w_next])

    print(max_distance)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))
    W = int(next(tokens))
    S = [next(tokens) for _ in range(H)]
    solve(H, W, S)
if __name__ == '__main__':
    main()

Solution (Python):
import queue
import copy

INF = 10 ** 10

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

maze = [[-1] * (W+2)]
for _ in range(H):
    maze.append( [-1] + list( map(lambda c: INF if c == '.' else -1, input()) ) + [-1] )
maze.append([-1] * (W+2))

maze_backup = copy.deepcopy(maze)
maxpath = 0
for start_y in range(1, H+1):
    for start_x in range(1, W+1):
        if maze[start_y][start_x] == -1:
            continue
        

        bfs_q = queue.Queue()
        bfs_q.put( (start_y, start_x) )
        maze[start_y][start_x] = 0

        while not bfs_q.empty():
            y, x = bfs_q.get()
            for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
                if maze[y+dy][x+dx] > maze[y][x] + 1:
                    maze[y+dy][x+dx] = maze[y][x] + 1
                    bfs_q.put( (y+dy, x+dx) )

        maxpath = max(maxpath, max(max(row) for row in maze))
        maze = copy.deepcopy(maze_backup)

print(maxpath)

Solution (Python):
from collections import deque
def max_dis_from(xi,yi):
    d = deque([(xi,yi)])
    dis = [[-1]*(w+2) for i in range(h+2)]
    dis[yi][xi] = 0
    while d:
        x,y = d.popleft()
        for i in range(4):
            newy = y+dy[i]
            newx = x+dx[i]
            if maze[newy][newx] == "." and dis[newy][newx] == -1:
                d.append((newx,newy))
                dis[newy][newx] = dis[y][x] + 1
    return dis[y][x]   
h,w = map(int,input().split())
maze = []
maze.append(["
for i in range(h):
    maze.append(["
maze.append(["
dx = [0,1,0,-1]
dy = [1,0,-1,0]
maxdis = 1
for i in range(1,h+1):
    for j in range(1,w+1):
        if maze[i][j] == ".":
            maxdis = max(maxdis,max_dis_from(j,i))
print(maxdis)

Solution (Python):
h,w = map(int,input().split())
x = [''.join(["
s = x+["
ans = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="
            continue
        checked = [[False]*(w+2) for _ in range(h+2)]
        checked[i][j]=True
        stack=[[i,j]]
        stack_=[]
        count = 1
        while stack:
            pair=stack.pop()
            for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:
                if s[pair[0]+x][pair[1]+y]=="." and checked[pair[0]+x][pair[1]+y] == False:
                    stack_.append([pair[0]+x,pair[1]+y])
                    checked[pair[0]+x][pair[1]+y] = True
            if stack==[]:
                stack = stack_.copy()
                stack_ = []
                count += 1

        ans = max(ans,count)
        
print(ans-2)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque 
INF = 100000
dir = ((1, 0), (-1, 0), (0, 1), (0, -1)) 
def main():
    H, W = map(int, readline().split())
    maze = []
    for _ in range(H):
        s = readline().rstrip().decode()
        maze.append(s) 
    
    
    def bfs(si, sj):
        dq = deque()
        dq.append((si, sj))        
        dist = [[INF for _ in range(W)] for _ in range(H)]
        dist[si][sj] = 0
        while len(dq)>0:
            i, j = dq.popleft()
            for di, dj in dir:
                nxi = i+di
                nxj = j+dj
                if (nxi<0) or (nxj<0) or (nxi>=H) or (nxj>=W):
                    continue
                if maze[nxi][nxj] == '
                    continue
                if dist[nxi][nxj] != INF:
                    continue
                dist[nxi][nxj] = dist[i][j]+1
                dq.append((nxi, nxj))
        res = 0
        for i in range(H):
            for j in range(W):
                if dist[i][j] == INF:
                    continue
                res = max(dist[i][j], res)        
        return res

    ans = 0
    for si in range(H):
        for sj in range(W):
            if maze[si][sj] == '
                continue
            ans = max(bfs(si, sj), ans)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall


def next_locations(maze, H, W, i, j):
    if maze[i][j] == '
        return list()
    locations = list()
    if i - 1 >= 0 and maze[i - 1][j] == '.':
        locations.append((i - 1, j))
    if i + 1 < H and maze[i + 1][j] == '.':
        locations.append((i + 1, j))
    if j - 1 >= 0 and maze[i][j - 1] == '.':
        locations.append((i, j - 1))
    if j + 1 < W and maze[i][j + 1] == '.':
        locations.append((i, j + 1))
    return locations


def location_to_index(W, i, j):
    return W * i + j


def main():
    H, W = list(map(int, input().split(' ')))
    INF = H * W
    maze = list()
    for _ in range(H):
        maze.append(input())
    d = [[INF for _ in range(H * W)] for _ in range(H * W)]
    for i in range(H):
        for j in range(W):
            from_index = location_to_index(W, i, j)
            locs = next_locations(maze, H, W, i, j)
            for loc in locs:
                to_index = location_to_index(W, loc[0], loc[1])
                d[from_index][to_index] = 1 if from_index != to_index else 0
    d = csgraph_from_dense(d, null_value=INF)
    d = floyd_warshall(d)
    answer = 0
    for from_index in range(H * W):
        for to_index in range(H * W):
            dist = d[from_index][to_index]
            if dist == float('inf'):
                continue
            if dist > answer:
                answer = dist
    print(int(answer))


if __name__ == '__main__':
    main()

Solution (Python):
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
ans = 0
def bfs(dist, s, queue):
    ret = 0
    while len(queue) > 0:
        y, x = queue.pop(0)
        for i, j in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
            h, w = y + i, x + j
            if 0 <= h < H and 0 <= w < W:
                if s[h][w] == "." and dist[h][w] == -1:
                    dist[h][w] = dist[y][x] + 1
                    queue.append([h, w])
    for i in range(H):
        ret = max(ret, max(dist[i]))
    return ret

for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            dist = [[-1] * W for _ in range(H)]
            dist[i][j] = 0
            queue = [(i, j)]
            ans = max(ans, bfs(dist, s, queue))

print(ans)

Solution (Python):
from collections import deque

inf = 10 ** 9

def bfs(si, sj, str_list, dist, h, w):
    q = deque([[si, sj]])
    dist[si][sj] = 0
    max_tmp = 0
    while len(q) != 0:
        i, j = q.popleft()
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ni = i + dx
            nj = j + dy
            if ni < 0 or ni >= h or nj < 0 or nj >= w:
                continue
            if str_list[ni][0][nj] != '.':
                continue
            if dist[ni][nj] != inf:
                continue
            dist[ni][nj] = dist[i][j] + 1
            q.append([ni, nj])
            max_tmp = max(max_tmp, dist[ni][nj])
    return max_tmp

def main():
    h, w = map(int, input().split())
    str_list = []
    for i in range(h):
        str_list.append(list(input().split()))

    max_num = 0

    for si in range(h):
        for sj in range(w):
            if str_list[si][0][sj] != '.':
                continue
            dist = [[inf] * w for i in range(h)]
            bfs_result = bfs(si, sj, str_list, dist, h, w)
            max_num = max(max_num, bfs_result)

    print(max_num)  

if __name__ == '__main__':
    main()

Solution (Python):
'''ika tako
スタートが決められたとき、そこから最も遠いマスは、
幅優先探索で最後に訪れたマスとなる。
よって、道である各マスをスタート地点として全て試し、
最長移動距離の最大値が答え。
H,W  の上限が小さいので、スタート地点候補が最大400、
1回の探索で探索するマスが最大400、あわせて160000回に
比例する計算量で間に合う。
'''
from collections import deque
 
def bfs(field, s):
    MOVE = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    q = deque([(0, s)])
    dist = [[-1] * w for _ in range(h)]
 
    d, i, j = -1, -1, -1
    while q:
        d, (i, j) = q.popleft()
        if dist[i][j] != -1:
            continue
        dist[i][j] = d
        for di, dj in MOVE:
            ni, nj = i + di, j + dj
            if not 0 <= ni < h or not 0 <= nj < w:
                continue
            if field[ni][nj] == '
                continue
            if dist[ni][nj] != -1:
                continue
            q.append((d + 1, (ni, nj)))
    return d, i, j

h, w = map(int, input().split())
field = [input() for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            d, i, j = bfs(field, (i, j))
            ans = max(ans, d)
print(ans)

Solution (Python):
import sys
h,w = map(int,input().split())
S = [list(input()) for i in range(h)]
ans = 0

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

for i in range(h):
    for j in range(w):
        visit = [[0 for i in range(w)] for i in range(h)]
        pos = []
        if S[i][j] == '.':
            visit[i][j] = 1
            pos.append([i, j])
            while len(pos) > 0:
                now = pos.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 S[y][x] != '
                            visit[y][x] = visit[now[0]][now[1]] + 1
                            pos.append([y, x])
        for p in range(h):
            for q in range(w):
                ans = max(ans, visit[p][q])
                
print(ans - 1)

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

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

for i in range(h):
    for j in range(w):
        visit = [[0 for i in range(w)] for i in range(h)]
        pos = []
        if S[i][j] == '.':
            visit[i][j] = 1
            d = 0
            pos.append([i, j, 0])
            while len(pos) > 0:
                now = pos.pop(0)
                d = now[2]
                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 S[y][x] != '
                            visit[y][x] = 1
                            pos.append([y, x, d + 1])
            ans.append(d)
                
print(max(ans))

Solution (Python):
from collections import deque


def BFS(x,y):
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

    color[x][y]="gray"
    D[x][y]=0
    queue=deque([[x,y]])

    num=0
    while len(queue)>0:
        a,b=queue.popleft()
        for c,d in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=a+c,b+d
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]=="white" and S[X][Y]==".":
                    D[X][Y]=D[a][b]+1
                    num=max(num,D[X][Y])
                    color[X][Y]="gray"
                    queue.append([X,Y])
        color[a][b]="black"
    
    return num


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

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

print(ans)

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

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

def longest_BFS(h, w):
    ret = -1
    if S[h][w] == '
        return -1
    table = [[-1 for i in range(W)] for j in range(H)]
    table[h][w] = 0
    next_step = [[h, w]]
    while next_step:
        ret += 1
        step = next_step[:]
        next_step = []
        while step:
            u = step.pop()
            for i in range(4):
                if u[0]+dx[i] >= 0 and u[0]+dx[i] < H \
                    and u[1]+dy[i] >= 0 and u[1]+dy[i] < W \
                    and S[u[0]+dx[i]][u[1]+dy[i]] == '.' \
                    and table[u[0]+dx[i]][u[1]+dy[i]] == -1:
                    next_step += [[u[0]+dx[i], u[1]+dy[i]]]
                    table[u[0]+dx[i]][u[1]+dy[i]] = ret

    return ret

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, longest_BFS(h, w))
print(ans)

Solution (Python):
h,w=map(int,input().split())
import sys
import queue
mok=queue.Queue()
s = [[str(c) for c in l.strip()] for l in sys.stdin]
dx=[1,0,-1,0]
dy=[0,1,0,-1]

maxx=0
for i in range(h):
  for j in range(w):
    d=[[-1]*w for k in range(h)]
    d[i][j]=0
    if s[i][j]=='.':
      mok.put([i,j])
      while not mok.empty():
        [nx,ny]=mok.get()
        for k in range(4):
          if 0<=nx+dx[k]<h and 0<=ny+dy[k]<w and s[nx+dx[k]][ny+dy[k]]=='.' and d[nx+dx[k]][ny+dy[k]]==-1:
            d[nx+dx[k]][ny+dy[k]]=d[nx][ny]+1
            if d[nx+dx[k]][ny+dy[k]]>maxx:
              maxx=d[nx+dx[k]][ny+dy[k]]
            mok.put([nx+dx[k],ny+dy[k]])

print(maxx)

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


l = [[] for i in range(H*W)]
for i in range(H-1):
    for j in range(W-1):
        if maze[i][j] == "." and maze[i+1][j] == ".":
            l[j+W*i].append(j+W*(i+1))
            l[j+W*(i+1)].append(j+W*i)
        if maze[i][j] == "." and maze[i][j+1] == ".":
            l[j+W*i].append(j+W*i+1)
            l[j+W*i+1].append(j+W*i)

for i in range(H-1):
    if maze[i][W-1] == "." and maze[i+1][W-1] == ".":
            l[W*i+W-1].append(W*i+2*W-1)
            l[W*i+2*W-1].append(W*i+W-1)

for j in range(W-1):
    if maze[H-1][j] == "." and maze[H-1][j+1] == ".":
            l[j+W*(H-1)].append(W*(H-1)+j+1)
            l[j+W*(H-1)+1].append(j+W*(H-1))

kosuu = H*W
ans = 0
for i in range(kosuu):
    dist = [-1]*kosuu
    d = deque()
    dist[i] = 0
    d.appendleft(i)
    while d:
        v = d.popleft()
        for j in l[v]:
            if dist[j] == -1:
                dist[j] = dist[v] + 1
                d.append(j)
    ans = max(ans,max(dist))
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
s=[input()for _ in range(h)]
a=[[400]*w for _ in range(h)]
ans=0
def bfs(b,i,j):
    b[i][j]=0
    seen=[[0]*w for _ in range(h)]
    todo=deque([(i,j)])
    while len(todo)>0:
        x,y=todo.popleft()
        if seen[x][y]==1:
            continue
        seen[x][y]=1
        if x>0 and seen[x-1][y]==0 and s[x-1][y]=='.':
            b[x-1][y]=b[x][y]+1
            todo.append((x-1,y))
        if x>0 and s[x-1][y]=='
            seen[x-1][y]=1
        if x<h-1 and seen[x+1][y]==0 and s[x+1][y]=='.':
            b[x+1][y]=b[x][y]+1
            todo.append((x+1,y))
        if x<h-1 and s[x+1][y]=='
            seen[x+1][y]=1
        if y>0 and seen[x][y-1]==0 and s[x][y-1]=='.':
            b[x][y-1]=b[x][y]+1
            todo.append((x,y-1))
        if y>0 and s[x][y-1]=='
            seen[x][y-1]=1
        if y<w-1 and seen[x][y+1]==0 and s[x][y+1]=='.':
            b[x][y+1]=b[x][y]+1
            todo.append((x,y+1))
        if y<w-1 and s[x][y+1]=='
            seen[x][y+1]=1
    ret=0 
    for bi in b:
        for bij in bi:
            if bij<400:
                ret=max(ret,bij)
    
    return ret

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

Solution (Python):
from collections import deque

def maze(h, w, sh, sw, list1):
    if list1[sh][sw]=="
        return 0
    flag = True
    for i in range(h):
        for j in range(w):
            if list1[i][j]=="
                flag=False
    if flag:
        return h+w-2
    
    que = deque()
    que.append([sh, sw, 0])
    list2 = list1.copy()
    direct = [(0,1), (0,-1), (1,0), (-1, 0)]
    count = 0
    while que:
        nh, nw, co = que.pop()
        count = co
        co +=1
        li=list(list2[nh])
        li[nw]="
        list2[nh]="".join(li)
        for i, j in direct:
            if nh+i<0 or nh+i>=h or nw+j<0 or nw+j>=w:
                pass
            elif list2[nh+i][nw+j]==".":
                que.appendleft([nh+i, nw+j, co])
    return count
        
h, w = (int(x) for x in input().split())
list1 = []
ans = 0
for i in range(h):
    list1.append(input())
for i in range(h):
    for j in range(w):
        ans_ij = maze(h, w, i, j , list1)
        if ans_ij>ans:
            ans=ans_ij
print(ans)

Solution (Python):
from collections import deque

def maze(h, w, sh, sw, list1):
    if list1[sh][sw]=="
        return 0
    flag = True
    for i in range(h):
        for j in range(w):
            if list1[i][j]=="
                flag=False
    if flag:
        return h+w-2
    
    que = deque()
    que.append([sh, sw, 0])
    list2 = list1.copy()
    direct = [(0,1), (0,-1), (1,0), (-1, 0)]
    count = 0
    while que:
        nh, nw, co = que.pop()
        count = co
        co +=1
        li=list(list2[nh])
        li[nw]="
        list2[nh]="".join(li)
        for i, j in direct:
            if nh+i<0 or nh+i>=h or nw+j<0 or nw+j>=w:
                pass
            elif list2[nh+i][nw+j]==".":
                que.appendleft([nh+i, nw+j, co])
    return count
        
h, w = (int(x) for x in input().split())
list1 = []
ans = 0
for i in range(h):
    list1.append(input())
for i in range(h):
    for j in range(w):
        ans_ij = maze(h, w, i, j , list1)
        if ans_ij>ans:
            ans=ans_ij
print(ans)

Solution (Python):
import queue

H,W = map(int, input().split())
S = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    tmp = input()
    S[i] = list(tmp)
dismax = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
        gone = [[-1 for i in range(W)] for j in range(H)]
        gone[i][j] = 0
        dis = 0
        q = queue.Queue()
        q.put(i)
        q.put(j)
        while not q.empty():
            tmpi = q.get()
            tmpj = q.get()
            if tmpi - 1 >= 0 and gone[tmpi - 1][tmpj] == -1 and S[tmpi - 1][tmpj] == ".": 
                gone[tmpi - 1][tmpj] = gone[tmpi][tmpj] + 1
                if dis < gone[tmpi - 1][tmpj]: dis = gone[tmpi - 1][tmpj]
                q.put(tmpi - 1)
                q.put(tmpj)
            if tmpj - 1 >= 0 and gone[tmpi][tmpj - 1] == -1 and S[tmpi][tmpj - 1] == ".":
                gone[tmpi][tmpj - 1] = gone[tmpi][tmpj] + 1
                if dis < gone[tmpi][tmpj - 1]: dis = gone[tmpi][tmpj - 1]
                q.put(tmpi)
                q.put(tmpj - 1)
            if tmpi + 1 < H and gone[tmpi + 1][tmpj] == -1 and S[tmpi + 1][tmpj] == ".":
                gone[tmpi + 1][tmpj] = gone[tmpi][tmpj] + 1
                if dis < gone[tmpi + 1][tmpj]: dis = gone[tmpi + 1][tmpj]
                q.put(tmpi + 1)
                q.put(tmpj)
            if tmpj + 1 < W  and gone[tmpi][tmpj + 1] == -1 and S[tmpi][tmpj + 1] == ".":
                gone[tmpi][tmpj + 1] = gone[tmpi][tmpj] + 1
                if dis < gone[tmpi][tmpj + 1]: dis = gone[tmpi][tmpj + 1]
                q.put(tmpi)
                q.put(tmpj + 1)
        if dismax < dis: dismax = dis
print(dismax)

Solution (Python):

import queue

h, w = map(int, input().split())
c = [list(input()) for i in range(h)]
visited = [[0 for i in range(w)] for j in range(h)]
q = queue.Queue()
ans = 0
            
dyx = [[0, 1], [1, 0], [-1, 0], [0, -1]]

for i in range(h):
    for j in range(w):
        if c[i][j] == '.':
            q.put([i, j])
            visited[i][j] = 1
            while not q.empty():
                now = q.get()
                for k in range(4):
                    y = now[0] + dyx[k][0]
                    x = now[1] + dyx[k][1]
                    if 0 <= y < h and 0 <= x < w:
                        if c[y][x] != '
                            visited[y][x] = visited[now[0]][now[1]] + 1
                            q.put([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 j in range(h)]
print(ans-1)

Solution (Python):


from heapq import heappop, heappush

h, w = list(map(int, input().split()))

map_list = [list(str(input())) for _ in range(h)]

ans = 0
for h1 in range(h):
    for w1 in range(w):
        D = [[False]*w for i in range(h)]
        Q = [(0, (h1, w1))]
        while Q:
            q = heappop(Q)
            qh, qw = q[1][0], q[1][1]
            if qh < 0 or qh >= h or qw < 0 or qw >= w:
                continue
            if map_list[qh][qw] == "
                continue
            if D[qh][qw]:
                continue
            D[qh][qw] = True
            ans = max(q[0], ans)
            heappush(Q, (q[0]+1, (qh+1, qw)))
            heappush(Q, (q[0]+1, (qh-1, qw)))
            heappush(Q, (q[0]+1, (qh, qw+1)))
            heappush(Q, (q[0]+1, (qh, qw-1)))
print(ans)

Solution (Python):
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

def check(ny, nx, sS):
    if 0<=ny<H and 0<=nx<W:
        if sS[ny][nx]=='.':
            return True
    else:
        return False

def bfs(sy, sx, sS):
    deq = deque()
    deq.append([(sy-1, sx-1)]) 
    sS[sy-1][sx-1] = '
    ddy = [-1, 0, 1, 0]
    ddx = [0, -1, 0, 1]
    step = 0
    while deq[0]:
        
        nqueue = []
        cqueue = deq.popleft()
        for val in cqueue:
            y, x = val
            for dy, dx in zip(ddy, ddx):
                ny, nx = y+dy, x+dx
                if check(ny, nx, sS):
                    sS[ny][nx] = '
                    nqueue.append((ny, nx))
        deq.append(nqueue)
        if not(deq[0]):
            break
        step += 1
    return step

res = 0
for i in range(H):
    for j in range(W):
        
        if S[i][j] == '.':
            sS = deepcopy(S)
            val = bfs(i+1, j+1, sS)
            res = max(res, val)

print(res)

Solution (Python):
from collections import deque

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




def bfs(C, visited_list, que):
    _max_move_num = 0
    while len(que) > 0:
        h, w, d = que.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h = h + j
            new_w = w + k
            if (new_h >= H or new_w >= W or new_w < 0 or new_h < 0):
                continue
            if (C[new_h][new_w] != '
                new_d = d + 1
                
                if (_max_move_num < new_d):
                    _max_move_num = new_d
                visited_list[new_h][new_w] = 1
                que.append((new_h, new_w, new_d))

    
    return(_max_move_num)


max_move_num = 0
for h in range(H):
    for w in range(W):
        if (C[h][w] == '.'):
            start_h, start_w = h, w
            
            que = deque([(start_h, start_w, 0)])
            visited_list = [[0]*W for _ in range(H)]
            visited_list[start_h][start_w] = 1
            max_move_num_ = bfs(C, visited_list, que)
            
            if(max_move_num_ > max_move_num):
                max_move_num = max_move_num_

print(max_move_num)

Solution (Python):
h,w = map(int,input().split())
from copy import deepcopy
from collections import deque
a = [list(input()) for l in range(h)]
c = [[None for i in range(w)]for j in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            c[i][j] = -1
ans = 0
g = deque()
for l in range(h):
    for k in range(w):
        b = deepcopy(c)
        if a[l][k] == '.':
            b[l][k] = 0
            g.append((l,k))
            while len(g)>0:
                i,j = g.popleft()
                dis = b[i][j] 
                for dx,dy in ((1,0),(0,1),(-1,0), (0,-1)):
                    newi = i + dx
                    newj = j +dy
                    if newi < 0 or newi > h-1 or newj < 0 or newj > w-1:
                        continue
                    if b[newi][newj] == -1:
                        b[newi][newj] = dis + 1
                        ans = max(ans,dis+1)
                        g.append((newi,newj))
print(ans)