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):
H, W = map(int, input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
    
from collections import deque
import numpy as np
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def dfs(sx, sy):
    que = deque()
    
    d = [[-1 for _ in range(W)] for _ in range(H)]
    que.append([sx, sy])
    d[sx][sy] = 0
    
    while(len(que) != 0):
        front = que.popleft()
        for i in range(4):
            nx = front[0] + dx[i]
            ny = front[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W):
                if maze[nx][ny] != "
                    que.append([nx, ny])
                    d[nx][ny] = d[front[0]][front[1]] + 1
                else:
                    continue
            else:
                continue
    return np.max(d)

import itertools

ans = []
l1 = [(s1, s2) for s1 in range(H) for s2 in range(W)]


for v in l1:
    if maze[v[0]][v[1]] == "
        continue
    ans.append(dfs(v[0], v[1]))
print(max(ans))

Solution (Python):
from collections import deque
H, W = map(int, input().split(' '))
maze = [[ch for ch in input()] for _ in range(H)]
max_ans = -1
'''
幅優先探索 実装
'''
def bfs(sx, sy):
    queue = deque()
    queue.append([sx, sy])
    cost_map = [[None if maze[i][j] == '.' else -1 for j in range(W)] for i in range(H)]
    cost_map[sy][sx] = 0
    while queue:
        x, y = queue.popleft()
        for next_x, next_y in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if (-1 < next_x < W) and (-1 < next_y < H) and (cost_map[next_y][next_x] is None):
                queue.append([next_x, next_y])
                cost_map[next_y][next_x] = cost_map[y][x] + 1
    return max([max(x) for x in cost_map])

for i in range(W):
    for j in range(H):
        if maze[j][i] != '
            ans = bfs(i, j)
            if max_ans < ans:
                max_ans = ans
print(max_ans)

Solution (Python):
from collections import deque

def a():
    H,W = map(int,input().split())
    S = ["" for _ in range(H)]
    for _ in range(H):
        S[_] = input()
    b = lambda n:S[n//W][n%W] == '.'
    v = list(filter(b,range(H*W)))
    u = list(map(lambda n:(n%W,n//W),v))

    le = len(v)

    def bfs(root):
        i = 0
        depth = [[-1]*W for _ in range(H)]
        in_que = [[0]*W for _ in range(H)]
        q = deque()
        q.append((root,0))
        xx,yy = root
        in_que[yy][xx] = 1
        while i < le:
            r,d = q.popleft()
            x,y = r
            depth[y][x] = d
            i += 1
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                dx += x
                dy += y
                if 0 <= dx < W and 0 <= dy < H and in_que[dy][dx] == 0 and S[dy][dx] == ".":
                    q.append(((dx,dy),d+1))
                    in_que[dy][dx] = 1
        return depth
    
    print(max([max([max(y) for y in x]) for x in map(bfs,u)]))

a()

Solution (Python):
from collections import deque
h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
def check(s,t):
    if (0 <= s <= w - 1) and (0 <= t <= h - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if (not check(x,y) ) or grid[y][x] == '
            continue
        if (x,y) not in finished:
            finished.add((x,y))
            graph[y][x] = cost
            que.append([x+1,y,cost+1])
            que.append([x, y+1, cost+1])
            que.append([x-1,y,cost+1])
            que.append([x,y-1,cost+1])
ans = 0
inf = 400

for i in range(h):
    for j in range(w):
        que = deque()
        que.append([j,i,0])
        graph = [[inf for _ in range(w)] for _ in range(h)]
        bfs(que)
        for p in range(h):
            for q in range(w):
                if graph[p][q] < inf:
                    ans = max(ans, graph[p][q])
print(ans)

Solution (Python):
from collections import deque
 
H, W = map(int, input().split())
 
init_field = [list(input()) for _ in range(H)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
 
def bfs(x, y):
    distance = [[-1]*W for _ in range(H)]
    que = deque([])
    que.append((y, x))
    distance[y][x] = 0
    res = 0
    while que:
        y, x = que.popleft()
        res = max(res, distance[y][x])
        for i, j in zip(dx, dy):
            nx = x + i
            ny = y + j
            if 0 <= nx < W and 0 <= ny < H and field[ny][nx] == "." and distance[ny][nx] == -1:
                distance[ny][nx] = distance[y][x] + 1
                que.append((ny, nx))
    return res

ans = 0
for sy in range(H):
    for sx in range(W):
        if init_field[sy][sx] == '
            continue
        field = [[i for i in row] for row in init_field]
        d = bfs(sx, sy)
        ans = max(ans, d)
print(ans)

Solution (Python):
import copy
h,w=map(int,input().split())
maze = [['
maze.insert(0,['
maze.append(['

def get_max_length_from_start(maze,x,y):
    ans_maze=[]
    min_now=1000000000
    max_length_list=[]
    tmp_maze=copy.deepcopy(maze)
    searching = [[y,x]]
    length=0
    while len(searching)!=0:
        next_searching_list=[]
        for point in searching:
            tmp_maze[point[0]][point[1]]=length
            mawari = [[point[0]+1,point[1]],[point[0]-1,point[1]],[point[0],point[1]+1],[point[0],point[1]-1]]
            next_searching = list(filter(lambda x:tmp_maze[x[0]][x[1]]==".",mawari))
            if len(next_searching)==0:
                max_length_list.append(length)
                continue
            next_searching_list += next_searching
        searching = list(map(list, set(map(tuple, next_searching_list))))
        length+=1
    return max(max_length_list)

true_max_length_list=[]
for y in range(1,h+1):
    for x in range(1,w+1):
        if maze[y][x]=='
            continue
        max_length=get_max_length_from_start(maze,x,y)
        true_max_length_list.append(max_length)

print(max(true_max_length_list))

Solution (Python):
h, w = map(int, input().split())
n = h * w
INF = 1 << 30

field = []
for i in range(h):
    field.append(input())

dist = [[INF] * n for _ in range(n)]

for i in range(h):
    for j in range(w):
        if field[i][j] == '
            continue
        if j + 1 < w and field[i][j+1] != '
            dist[i * w + j][i * w + j + 1] = 1
            dist[i * w + j + 1][i * w + j] = 1
        if i + 1 < h and field[i+1][j] != '
            dist[i * w + j][(i+1) * w + j] = 1
            dist[(i+1) * w + j][i * w + j] = 1


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

ans = 0

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if dist[i][j] == INF:
            continue
        ans = max(ans, dist[i][j])

print(ans)

Solution (Python):
import queue

q = queue.Queue()

H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
ans = 0
vec_x = [1,0,-1,0]
vec_y = [0,1,0,-1]

def bfs(sx,sy):
    
    d = [[-1 for i in range(W)] for j in range(H)]
    d[sy][sx] = 0
    q.put([sx,sy])
    while not q.empty():
        current_xy = q.get()
        
        for i in range(4):
            nx = current_xy[0] + vec_x[i]
            ny = current_xy[1] + vec_y[i]

            
            if( (nx >= 0 and nx < W ) and (ny >= 0 and ny < H ) ):
                if S[ny][nx] != "
                    
                    if d[ny][nx] == -1:
                        q.put([nx,ny])
                        d[ny][nx] = d[current_xy[1]][current_xy[0]] + 1
    return d[current_xy[1]][current_xy[0]]

for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == "
            continue
        if ans <= bfs(sx,sy):
            ans = bfs(sx,sy)

print(ans)

Solution (Python):
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
inf=float("inf")
d=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
for sx in range(H):
    for sy in range(W):
        if S[sx][sy]==".":
            data=[[inf]*W for i in range(H)]
            que=[[sx,sy]]
            data[sx][sy]=0
            count=1
            while que:
                h=[]
                for x,y in que:
                    for dx,dy in d:
                        nx,ny=x+dx,y+dy
                        if 0<=nx<H and 0<=ny<W and S[nx][ny]=="." and data[nx][ny]==inf:
                            h.append([nx,ny])
                            data[nx][ny]=count
                que=h
                count+=1
            for i in range(H):
                for j in range(W):
                    if data[i][j]!=inf:
                        ans=max(ans,data[i][j])
print(ans)

Solution (Python):
import collections

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

m = []
for _ in range(h):
    m.append(list(input()))


ans = 0
for i in range(h):
    for j in range(w):
        if m[i][j] == '
            continue

        checked = [[False]*w for _ in range(h)]
        q = collections.deque()
        q.append((i, j, 0))
        checked[i][j] = True
        while True:
            x, y, s = q.popleft()
            

            if x > 0 and m[x-1][y] != '
                q.append((x-1, y, s+1))
                checked[x-1][y] = True

            if x+1 < h and m[x+1][y] != '
                q.append((x+1, y, s+1))
                checked[x+1][y] = True

            if y > 0 and m[x][y-1] != '
                q.append((x, y-1, s+1))
                checked[x][y-1] = True

            if y+1 < w and m[x][y+1] != '
                q.append((x, y+1, s+1))
                checked[x][y+1] = True

            ans = max(ans, s)

            if len(q) == 0:
                break

print(ans)

Solution (Python):
from collections import deque

def a():
    H,W = map(int,input().split())
    S = ["" for _ in range(H)]
    for _ in range(H):
        S[_] = input()
    b = lambda n:S[n//W][n%W] == '.'
    v = list(filter(b,range(H*W)))
    u = list(map(lambda n:(n%W,n//W),v))

    le = len(v)

    def bfs(root):
        i = 0
        depth = [[-1]*W for _ in range(H)]
        in_que = [[0]*W for _ in range(H)]
        q = deque()
        q.append((root,0))
        xx,yy = root
        in_que[yy][xx] = 1
        while i < le:
            r,d = q.popleft()
            x,y = r
            depth[y][x] = d
            i += 1
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                dx += x
                dy += y
                if 0 <= dx < W and 0 <= dy < H and in_que[dy][dx] == 0 and S[dy][dx] == ".":
                    q.append(((dx,dy),d+1))
                    in_que[dy][dx] = 1
        return depth
    
    print(max([max([max(y) for y in x]) for x in map(bfs,u)]))

a()

Solution (Python):
from collections import deque

h, w = [int(v) for v in input().split()]

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

def contains(maze, i, j):
    if i < 0 or i >= h:
        return False
    if j < 0 or j >= w:
        return False
    return True

def far(maze, i0, j0):
    q = deque([])

    q.append((i0, j0, 0))

    closed = set()
    closed.add((i0, j0))
    max_dist = 0
    max_p = None
    while len(q) > 0:
        e = q.popleft()
        
        i = e[0]
        j = e[1]
        cost = e[2] + 1
        for n in ((0, 1), (1, 0), (-1, 0), (0, -1)):
            ni = i + n[0]
            nj = j + n[1]
            nkey = (ni, nj)
            if not contains(maze, ni, nj):
                continue
            if maze[ni][nj] != '.':
                continue
            nkey = (ni, nj)
            if nkey in closed:
                continue
            closed.add(nkey)
            q.append((ni, nj, cost))
            if max_dist < cost:
                max_dist = cost
                max_p = nkey
    return max_p, max_dist
    
def solve(maze):
    max_dist = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] != '.':
                continue
            p, dist = far(maze, i, j)
            if max_dist < dist:
                max_dist = dist
    return max_dist

print(solve(maze))

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

Solution (Python):
from collections import deque

h, w = map(int, input().split())
field = []

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

out = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            seen = [[0 for m in range(w)] for n in range(h)]
            seen[i][j] = 1
            q = deque([])
            q.append((i, j, 0))
            while q:
                (y, x, cnt) = q.popleft()
                
                
                for ny, nx in (y, x + 1), (y, x - 1), (y + 1, x), (y - 1, x):
                    if ny < 0 or ny >= h or nx < 0 or nx >= w:
                        pass
                    elif field[ny][nx] == '.' and seen[ny][nx] == 0:
                        q.append((ny, nx, cnt + 1))
                        seen[ny][nx] = 1

            out = max(out, cnt)
print(out)

Solution (Python):
from collections import deque

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

INF = -1

def bfs():
    dist = [[INF for i in range(W)] for j in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        
        
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    ret = -1
    for i in range(H):
        ret = max(ret, max(dist[i]))
    return ret

ans = -1
for i in range(H):
    for j in range(W):
            sx, sy = i, j
            if c[sx][sy] == '
                continue
            ans = max(ans, bfs())
print(ans)

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

def bfs():
    dist = [[-float('inf')]*W for _ in range(H)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    q = deque()
    q.append([sy,sx])
    dist[sy][sx] = 0
    while q:
        p = q.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] == '.' and dist[ny][nx] == -float('inf'):
                q.append([ny,nx])
                dist[ny][nx] = dist[p[0]][p[1]] + 1
    longest_dist = 0
    for y in range(H):
        for x in range(W):
            longest_dist = max(longest_dist,dist[y][x])
    return longest_dist
ans = 0
for sy in range(H):
    for sx in range(W):
        if grid[sy][sx] == '.':
            ans = max(bfs(),ans)

print(ans)

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

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
INF = 10**9 + 7

def bfs(y, x):
    res = 0
    q = [[y,x]]
    D = [[INF for _ in range(W)] for _ in range(H)]
    D[y][x] = 0
    while len(q):
        y, x = q.pop(0);
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0 <= ny <= H-1 and 0 <= nx <= W-1): continue
            if S[ny][nx] == '
            if D[ny][nx] > D[y][x] + 1:
                D[ny][nx] = D[y][x] + 1
                q.append([ny,nx])
                res = max(res, D[ny][nx])
    return res

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):

from scipy.sparse.csgraph import floyd_warshall

int_max = 2 ** 63 - 1

def get_cost(start, end):
    return 1 if start == '.' and end == '.' else 2 ** 63 - 1


def main():

    H, W = map(int, input().split(' '))
    ad_table = [[int_max for _ in range(H*W)] for _ in range(H*W)]
    maze = []
    for _ in range(H):
        maze.append(input())

    for si in range(H):
        for sj in range(W):
            for ti in range(H):
                for tj in range(W):
                    if si == ti and sj == tj:
                        ad_table[(si*W)+sj][(ti*W)+tj] = 0
                    elif (abs(si - ti) == 1 and sj - tj == 0) or (si - ti == 0 and abs(sj - tj) == 1):
                        ad_table[(si*W)+sj][(ti*W)+tj] = get_cost(maze[si][sj], maze[ti][tj])

    res = floyd_warshall(ad_table)
    ans = -1
    for i in range(H*W):
        for j in range(i+1,H*W):
            if res[i][j] != int_max:
                ans = max(res[i][j], ans)
    print(int(ans))

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
s = ['


di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]


def bfs(si, sj):
    queue = deque([(si, sj, 0)])
    cost = [[-1] * (w + 2) for _ in range(h + 2)]
    cost[si][sj] = 0
    while queue:
        ci, cj, cc = queue.popleft()
        for k in range(4):
            ni = ci + di[k]
            nj = cj + dj[k]
            if s[ni][nj] == '
                continue
            if cost[ni][nj] != -1:
                continue
            queue.append((ni, nj, cc + 1))
            cost[ni][nj] = cc + 1

    return max(map(lambda x: max(x), cost))


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

Solution (Python):
from collections import deque

def bfs():
    reg = [[0] * w for _ in range(h)]    
    for i in range(h):
        for j in range(w):
            d = [[float("inf")] * w for _ in range(h)]
            que = deque([])
            res = 0
            if field[i][j] == ".":
                sx = i
                sy = j
                que.append([sx, sy])
                d[sx][sy] = 0
                
                dx = [0, 1, 0, -1]
                dy = [1, 0, -1, 0]
    
                while len(que) != 0:
                    p = que.popleft()

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

                        if 0 <= nx < h and 0 <= ny < w and field[nx][ny] != "
                            que.append([nx, ny])
                            d[nx][ny] = d[p[0]][p[1]] + 1
                            res = max(res, d[nx][ny])
                reg[sx][sy] = res
    global ans
    for i in range(h):
        for j in range(w):
            ans = max(ans, reg[i][j])


h, w = map(int, input().split())
field =[list(input()) for _ in range(h)]
ans = 0
bfs()

print(ans)

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

    for hs in range(H):
        for ws in range(W):
            if S[hs][ws] == '
                continue
            answer = bfs(S, H, W, hs, ws)
            if max_move < answer:
                max_move = answer
    print(max_move)

def bfs(S, H, W, hs, ws):
    visited = [[-1] * W for _ in range(H)]
    s = (hs, ws, 0)
    queue = [s]
    c = s
    max_c = 0
    while len(queue) > 0:
        c = queue.pop(0)
        count = c[2]
        if count > max_c:
            max_c = count
        
        visited[c[0]][c[1]] = 1
        
        enqueue(c[0] - 1, c[1], S, H, W, queue, count, visited)
        
        enqueue(c[0], c[1] - 1, S, H, W, queue, count, visited)
        
        enqueue(c[0] + 1, c[1], S, H, W, queue, count, visited)
        
        enqueue(c[0], c[1] + 1, S, H, W, queue, count, visited)
    
    return max_c

def enqueue(i, j, S, H, W, queue, count, visited):
    if i >= 0 and i < H and j >= 0 and j < W and visited[i][j] == -1 and S[i][j] == '.':
        queue.append((i, j, count + 1))
        visited[i][j] = 1

main()

Solution (Python):
dxys = [(-1,0), (1,0), (0,-1), (0,1)]

H, W = map(int, input().split())
Sss = ['

N = H*W
adjL = [[] for _ in range(N)]
for x in range(1, H+1):
    for y in range(1, W+1):
        if Sss[x][y] != '.': continue
        for dx, dy in dxys:
            x2, y2 = x+dx, y+dy
            if Sss[x2][y2] != '.': continue
            z = (x-1)*W + y-1
            z2 = (x2-1)*W + y2-1
            adjL[z].append(z2)


def getDiameterOfUnweightedGraph(adjList):
    numV = len(adjList)
    def bfs(vSt):
        costs = [-1] * numV
        costs[vSt] = cost = 0
        vs = [vSt]
        while vs:
            cost += 1
            v2s = []
            for v in vs:
                for v2 in adjList[v]:
                    if costs[v2] == -1:
                        costs[v2] = cost
                        v2s.append(v2)
            vs = v2s
        return cost - 1
    return max([bfs(vSt) for vSt in range(numV)])

maxDist = getDiameterOfUnweightedGraph(adjL)
print(maxDist)

Solution (Python):

import queue
import copy

import time
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**9 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
l = 0

for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
            l += 1
if l == H*W:
    print(H+W-2)
    exit()
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start, bb):
    dist = [[10**9 for _ in range(W)] for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        bb[x][y] == '
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            if x+dx>=0 and x+dx<= H-1 and y+dy>=0 and y+dy<=W-1 and abs(dx-dy)==1:
                if bb[x+dx][y+dy] != '
                    if dist[x+dx][y+dy] > dist[x][y]:
                        dist[x+dx][y+dy] = dist[x][y] + 1
                        if dist[x+dx][y+dy] > far:
                            far = dist[x+dx][y+dy]
                        q.put((x+dx,y+dy))
        if q.empty():
            break
    return far
res = 0
while 1:
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)

Solution (Python):
import queue
import copy

def bfs(s1,s2):
    global ans
    cs = copy.deepcopy(s)
    queueX = queue.Queue()
    queueY = queue.Queue()
    queueX.put(s1)
    queueY.put(s2)
    cs[s1][s2] = 0
    while queueX.empty() == False:
        x = queueX.get()
        y = queueY.get()

        for i in range(4):
            nextX = x + moveR[i]
            nextY = y + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and cs[nextX][nextY] != '
                and cs[nextX][nextY] == '.':
                cs[nextX][nextY] = cs[x][y] + 1
                ans = max(ans, cs[nextX][nextY])
                queueX.put(nextX)
                queueY.put(nextY)

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

moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]
ans = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            bfs(i, j)

print(ans)

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

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

for i in range(H-1):
    for j in range(W):
        if S[i][j] == "." and S[i+1][j] == ".":
            graph[j+(i*W)][j+(W*(i+1))] = 1
            graph[j+(W*(i+1))][j+(i*W)] = 1
for i in range(H):
    for j in range(W-1):
        if S[i][j] == "." and S[i][j+1] == ".":
            graph[j+(i*W)][j+(W*i)+1] = 1
            graph[j+(W*i)+1][j+(i*W)] = 1
            
d = floyd_warshall(graph)

ans = 0
for i in range(H*W):
    for j in range(i+1,H*W):
        if d[i][j] != float("inf"):
            ans = max(ans, d[i][j])

print(int(ans))

Solution (Python):
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    longest = 0
    while stack:
        h, w = stack.popleft()
        
        
        
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                    continue
            elif maze[new_h][new_w] != "
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    longest = max(longest, visited[new_h][new_w])
                    stack.append([new_h, new_w])
    
    
    return longest

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if maze[sh][sw] != "
                visited = [[-1] * W for _ in range(H)]
                step_cnt = bfs(maze, visited, sh, sw)
                ans = max(ans, step_cnt)
    print(ans - 1)

Solution (Python):
import copy

def judge1(masu,h,w):
    if (masu[0]>=0)&(masu[0]<h)&(masu[1]>=0)&(masu[1]<w):
        return True
    else:
        return False
    
def judge2(masu,s):
    if s[masu[0]][masu[1]] == '.':
        return True
    else:
        return False
    
def tsugi(i,j,h,w,s2):
    ans=[]
    for masu in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
        if judge1(masu,h,w):
            if judge2(masu,s2):
                ans.append(masu)
    return ans
    


def solve(i,j,s,h,w):
    ma = 0
    s2 = copy.deepcopy(s)
    if s2[i][j]=='.':
        s2[i][j]='
        nex = tsugi(i,j,h,w,s2)
        while len(nex)!=0 :
            ma+=1
            nex2=[]
            for n in nex:
                nex2[len(nex2):] = tsugi(n[0],n[1],h,w,s2)
                s2[n[0]][n[1]]='
            nex = set(nex2)
    return ma


h,w=map(int,input().split())
s = []
ma = 0
for i in range(h):
    s.append(list(input()))
for i in range(h):
    for j in range(w):
        ans = solve(i,j,s,h,w)
        ma = max(ma,ans)
print(ma)

Solution (Python):
import numpy as np
from collections import deque
infinity = -10**5
H,W = map(int,input().split())

A = np.zeros((H+1,W+1))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            A[i][j] = 1
        else:
            A[i][j] = -1

N = H*W
G=[[] for i in range(N)]

for i in range(H):
    for j in range(W):
        if A[i][j] ==1:
            if A[i+1][j] == 1:
                G[W*(i+1)+j].append(W*i+j)
                G[W*i+j].append(W*(i+1)+j)

            if A[i][j+1] == 1:
                G[W*i+(j+1)].append(W*i+j)
                G[W*i+j].append(W*i+(j+1))

def BFS (s):
    queue = deque()
    d = [infinity]*N
    
    queue.append(s)
    d[s]= 0
    
    while len(queue)!=0:
      u = queue.popleft()
      for v in G[u]:
      	if d[v] == infinity:
        	d[v] = d[u]+1
        	queue.append(v) 	  
  
    return d

ans = 0

"""
for i in range(N):
    I = i//W
    J = i%W
    if A[I][J] == 1:
        d = BFS(i)
        for k in range(N):
            if d[k] == infinity:
                d[k] = -1
        ans = max(ans,max(d))
"""

for i in range(H):
    for j in range(W):
        if A[i][j] == 1:
            d = BFS(W*i+j)
            ans = max(ans,max(d))

print(ans)

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

def bfs(i,j,d):
    d_max=0
    used=[[False for j in range(W)] for i in range(H)]
    Q=deque()
    Q.append((i,j,d))
    used[i][j]=True
    while Q:
        i,j,d=Q.popleft()
        for ni,nj in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
            if ni<0 or nj<0 or ni>=H or nj>=W:
                continue
            if M[ni][nj]=='.' and not used[ni][nj]:
                d_max=max(d_max,d+1)
                used[ni][nj]=True
                Q.append((ni,nj,d+1))
    return d_max

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

print(ans)

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

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

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

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

        if count > ans:
            ans = count


print(ans)