Problem:
 Score : 400 points    Problem Statement Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i -th row from the top and the j -th column is a "wall" square if S_{ij} is # , and a "road" square if S_{ij} is . .  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.      Constraints  1 \leq H,W \leq 20  S_{ij} is . or # .  S contains at least two occurrences of . .  Any road square can be reached from any road square in zero or more moves.         Input Input is given from Standard Input in the following format:  H  W  S_{11} ... S_{1W}  :  S_{H1} ... S_{HW}       Output Print the maximum possible number of moves Aoki has to make.        Sample Input 1 3 3
...
...
...      Sample Output 1 4  If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.       Sample Input 2 3 5
...#.
.#.#.
.#...      Sample Output 2 10  If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = []
ans = 0
si, sj = 0, 0

for i in range(h):
    s.append(input())

for x in range(h):
    for y in range(w):
        
        if s[x][y] == '
            continue
        q = deque()
        q.append((0, (x, y)))
        done = set()
        done.add(str(x) + ':' + str(y))
        temp = 0

        while q:
            dis, tup = q.popleft()
            i, j = tup[0], tup[1]
            temp = max(temp, dis)

            
            if j < w - 1 and s[i][j + 1] == '.':
                if str(i) + ':' + str(j + 1) not in done:
                    done.add(str(i) + ':' + str(j + 1))
                    q.append((dis + 1, (i, j + 1)))

            
            if j > 0 and s[i][j - 1] == '.':
                if str(i) + ':' + str(j - 1) not in done:
                    done.add(str(i) + ':' + str(j - 1))
                    q.append((dis + 1, (i, j - 1)))

            
            if i > 0 and s[i - 1][j] == '.':
                if str(i - 1) + ':' + str(j) not in done:
                    done.add(str(i - 1) + ':' + str(j))
                    q.append((dis + 1, (i - 1, j)))

            
            if i < h - 1 and s[i + 1][j] == '.':
                if str(i + 1) + ':' + str(j) not in done:
                    done.add(str(i + 1) + ':' + str(j))
                    q.append((dis + 1, (i + 1, j)))

        if temp > ans:
            
            
            ans = temp
            si, sj = x, y

        

print(ans)

Solution (Python):
from collections import deque

def bfs(maze,dist,sy,sx):
    
    queue = deque([[sy,sx]])
    
    dist[sy][sx] = 0
    
    md = 0
    while queue:
        
        y,x = queue.popleft()
        for j, k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y, new_x = y+j, x+k
            
            if 0 <= new_y < H and 0 <= new_x < W:
                
                
                if maze[new_y][new_x] == "." and dist[new_y][new_x] == -1:
                    dist[new_y][new_x] = dist[y][x] + 1
                    queue.append([new_y, new_x])
                    md = max(dist[new_y][new_x],md)
    return md
H, W = map(int,input().split())
maze = [input() for i in range(H)]

ans = 0
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for k in range(H)]
        
        if maze[i][j] != "
            a = bfs(maze,dist,i,j)
            ans = max(a,ans)
print(ans)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
S=[]

for i in range(H):
    S.append(list(input()))

step=[[1,0],[-1,0],[0,1],[0,-1]]


mx=0
for sh in range(H):
    for sw in range(W):
        if S[sh][sw]=="
        visited = [[False] * W for i in range(H)]
        q=deque([[sh,sw,0]])
        visited[sh][sw]=True

        while q:
            h,w,c=q.popleft()
            for dh,dw in step:
                if not (0<=h+dh<H and 0<=w+dw<W):continue
                if S[h+dh][w+dw]=="
                if visited[h+dh][w+dw]==False:
                    q.append([h+dh,w+dw,c+1])
                    visited[h+dh][w+dw]=True
                else:
                    mx=max(mx,c)
print(mx)

Solution (Python):
from collections import deque

def bfs(maze,dist,sy,sx):
    
    queue = deque([[sy,sx]])
    dist[sy][sx] = 0
    md = 0
    l = []
    while queue:
        
        y,x = queue.popleft()
        for j, k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y, new_x = y+j, x+k
            
            if 0 <= new_y < H and 0 <= new_x < W:
                
                if maze[new_y][new_x] == "." and dist[new_y][new_x] == -1:
                    dist[new_y][new_x] = dist[y][x] + 1
                    queue.append([new_y, new_x])
                    md = max(dist[new_y][new_x],md)
    return md
H, W = map(int,input().split())
maze = [input() for i in range(H)]

ans = 0
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for k in range(H)]
        if maze[i][j] != "
            a = bfs(maze,dist,i,j)
            ans = max(a,ans)
print(ans)

Solution (Python):
from collections import deque

def bfs(maze,dist,sy,sx):
    
    queue = deque([[sy,sx]])
    dist[sy][sx] = 0
    md = 0
    l = []
    while queue:
        
        y,x = queue.popleft()
        for j, k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y, new_x = y+j, x+k
            
            if 0 <= new_y < H and 0 <= new_x < W:
                
                if maze[new_y][new_x] == "." and dist[new_y][new_x] == -1:
                    dist[new_y][new_x] = dist[y][x] + 1
                    queue.append([new_y, new_x])
                    md = max(dist[new_y][new_x],md)
    return md
H, W = map(int,input().split())
maze = [input() for i in range(H)]

ans = 0
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for j in range(H)]
        if maze[i][j] != "
            a = bfs(maze,dist,i,j)
            ans = max(a,ans)
print(ans)

Solution (Python):


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

S = ["
S[0] = ["
S[H+1] = ["
for i in range(1,H+1):
    S[i] = ["

inf = 10 ** 3
m = 0
mi = -1
mj = -1
mk = -1
ml = -1
  
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j] == "
            continue
        data = [[inf]*(W+2) for k in range(H+2)]
        data[i][j] = 0
        stack = [[i,j,0]]
        while stack:
            x = stack.pop()
            if S[x[0]+1][x[1]] == "." and data[x[0]+1][x[1]]>x[2]+1:
                data[x[0]+1][x[1]] = x[2]+1
                stack.append([x[0]+1,x[1],x[2]+1])
            if S[x[0]][x[1]+1] == "." and data[x[0]][x[1]+1]>x[2]+1:
                data[x[0]][x[1]+1] = x[2]+1
                stack.append([x[0],x[1]+1,x[2]+1])
            if S[x[0]-1][x[1]] == "." and data[x[0]-1][x[1]]>x[2]+1:
                data[x[0]-1][x[1]] = x[2]+1
                stack.append([x[0]-1,x[1],x[2]+1])
            if S[x[0]][x[1]-1] == "." and data[x[0]][x[1]-1]>x[2]+1:
                data[x[0]][x[1]-1] = x[2]+1
                stack.append([x[0],x[1]-1,x[2]+1])
            

        for k in range(1,H+1):
            for l in range(1,W+1):
                if data[k][l] > m and data[k][l] != inf:
                    m = data[k][l]
                    mi = i
                    mj = j
                    mk = k
                    ml = l


print(m)

Solution (Python):
def main():
    h, w = map(int, input().split())
    grid = ["
    grid = [[i == "." for i in j] for j in grid]
    ans_list = []
    for i in range(1, h+1):
        for j in range(1, w+1):
            if grid[i][j]:
                ans_list.append((i, j))
    m = 0
    for i, j in ans_list:
        q = [(i, j)]
        dist = [[-1]*(w+2) for _ in [0]*(h+2)]
        cnt = 0
        dist[i][j] = 0
        while q:
            qq = []
            cnt += 1
            while q:
                x, y = q.pop()
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    if dist[x+dx][y+dy] == -1:
                        if grid[x+dx][y+dy]:
                            dist[x+dx][y+dy] = cnt
                            qq.append((x+dx, y+dy))
            q = qq
        m = max(m, max([max([l for l in k]) for k in dist]))
    print(m)


main()

Solution (Python):
from collections import deque
H, W = map(int, input().split())
X = [[1 if a == "

def BFS(i0=0):
    Q = deque([i0])
    D = [-1] * (H * W)
    D[i0] = 0
    while Q:
        x = Q.popleft()
        i, j = x // W, x % W
        for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W:
                if X[ni][nj] == 0:
                    y = ni * W + nj
                    if D[y] == -1:
                        D[y] = D[x] + 1
                        Q.append(y)
    return D

ma = 0
for i in range(H):
    for j in range(W):
        if X[i][j] == 0:
            ma = max(ma, max(BFS(i*W+j)))
print(ma)

Solution (Python):
from collections import deque

def bfs(maze, visited, H, W, sx, sy):
    que = deque()
    que.append([sx, sy])
    visited[sx][sy] = 0
    ml = 0
    
    while que:
        x, y = que.popleft()
        
        for px, py in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx, ny = x+px, y+py
            if (0<=nx<H)and(0<=ny<W):
                if (maze[nx][ny] == '.')and(visited[nx][ny]==-1):
                    que.append([nx, ny])
                    dist = visited[x][y] + 1
                    visited[nx][ny] = dist
                    ml = max(ml, dist)
    return ml
                    

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '
            continue
        else:
            visited = [[-1]*W for _ in range(H)]
            ans = max(ans, bfs(maze, visited, H, W, i, j))
print(ans)

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

import copy
dp=[[1000 for i in range(w)]for i in range(h)]
for y,i in enumerate(field):
    for x,j in enumerate(i):
        if j=="
            dp[y][x]=9999

dydx=[[-1,0],[1,0],[0,-1],[0,1]]

maxi=0
for y,i in enumerate(field):
    for x,j in enumerate(i):
        if j==".":
            ndp=copy.deepcopy(dp)
            ndp[y][x]=0
            cnt=0
            queue=[]
            queue.append([y,x])
            while queue:
                ny,nx=queue.pop(0)
                for dy,dx in dydx:
                    nny,nnx=ny+dy,nx+dx
                    if 0<=nny<=h-1 and 0<=nnx<=w-1 and field[nny][nnx]!="
                        ndp[nny][nnx]=ndp[ny][nx]+1
                        queue.append([nny,nnx])
                        if ndp[nny][nnx]>maxi:
                            maxi=ndp[nny][nnx]
            
print(maxi)

Solution (Python):
def main():
    h, w = map(int, input().split())
    grid = ["
    grid = [[i == "." for i in j] for j in grid]
    ans_list = []
    for i in range(1, h+1):
        for j in range(1, w+1):
            if grid[i][j]:
                ans_list.append((i, j))
    m = 0
    for i, j in ans_list:
        q = [(i, j)]
        dist = [[-1]*(w+2) for _ in [0]*(h+2)]
        cnt = 0
        dist[i][j] = 0
        while q:
            qq = []
            cnt += 1
            while q:
                x, y = q.pop()
                if dist[x-1][y] == -1:
                    if grid[x-1][y]:
                        dist[x-1][y] = cnt
                        qq.append((x-1, y))
                if dist[x+1][y] == -1:
                    if grid[x+1][y]:
                        dist[x+1][y] = cnt
                        qq.append((x+1, y))
                if dist[x][y-1] == -1:
                    if grid[x][y-1]:
                        dist[x][y-1] = cnt
                        qq.append((x, y-1))
                if dist[x][y+1] == -1:
                    if grid[x][y+1]:
                        dist[x][y+1] = cnt
                        qq.append((x, y+1))
            q = qq
        m = max(m, max([max([l for l in k]) for k in dist]))
    print(m)


main()

Solution (Python):

from collections import deque

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



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

def update(i, j, x):
    if dist[i][j] != inf:
        return
    dist[i][j] = x
    q.append([i, j])

ans = 0

for si in range(h):
    for sj in range(w):
        if s[si][sj] == "
            continue
        dist = [[inf] * w for _ in range(h)]
        q = deque()



        update(si, sj, 0)
        while q:
            i, j = q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                if s[ni][nj] == "
                    continue
                update(ni, nj, dist[i][j] + 1)
        for i in range(h):
            for j in range(w):
                if dist[i][j] == inf:
                    continue
                ans = max(ans, dist[i][j])
print(ans)

Solution (Python):
def main():
    h, w = map(int, input().split())
    grid = ["
    
    ans_list = []
    for i in range(1, h+1):
        for j in range(1, w+1):
            if grid[i][j] == ".":
                ans_list.append((i, j))
    m = 0
    for i, j in ans_list:
        q = [(i, j)]
        dist = [[-1]*(w+2) for _ in [0]*(h+2)]
        cnt = 0
        dist[i][j] = 0
        while q:
            qq = []
            cnt += 1
            while q:
                x, y = q.pop()
                if dist[x-1][y] == -1:
                    if grid[x-1][y] == ".":
                        dist[x-1][y] = cnt
                        qq.append((x-1, y))
                if dist[x+1][y] == -1:
                    if grid[x+1][y] == ".":
                        dist[x+1][y] = cnt
                        qq.append((x+1, y))
                if dist[x][y-1] == -1:
                    if grid[x][y-1] == ".":
                        dist[x][y-1] = cnt
                        qq.append((x, y-1))
                if dist[x][y+1] == -1:
                    if grid[x][y+1] == ".":
                        dist[x][y+1] = cnt
                        qq.append((x, y+1))
            q = qq
        m = max(m, max([max([l for l in k]) for k in dist]))
    print(m)


main()

Solution (Python):

from collections import deque

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



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


ans = 0

for si in range(h):
    for sj in range(w):
        if s[si][sj] == "
            continue
        dist = [[inf] * w for _ in range(h)]
        q = deque()

        def update(i, j, x):
            if dist[i][j] != inf:
                return
            dist[i][j] = x
            q.append([i, j])

        update(si, sj, 0)
        while q:
            i, j = q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                if s[ni][nj] == "
                    continue
                update(ni, nj, dist[i][j] + 1)
        for i in range(h):
            for j in range(w):
                if dist[i][j] == inf:
                    continue
                ans = max(ans, dist[i][j])
print(ans)

Solution (Python):
from collections import deque

def bfs(table, visited, sy, sx):
    queue=deque([[sy, sx]])
    visited[sy][sx]=0
    md=0
    while queue:
        y, x=queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < R and 0 <= new_x < C:
              if table[new_y][new_x]=="." and visited[new_y][new_x]==-1:
                visited[new_y][new_x]=visited[y][x] + 1
                queue.append([new_y, new_x])
                md=max(visited[new_y][new_x],md)
    return md

R, C=map(int, input().split())
table = [input() for i in range(R)]
ans=0
for yi in range(R):
  for xi in range(C):
    visited=[[-1]*C for j in range(R)]
    if table[yi][xi]!='
      a=bfs(table,visited,yi,xi)
      ans=max(a,ans)
print(ans)

Solution (Python):
from collections import deque

def bfs(maze, dist, sy, sx):
    queue = deque([[sy, sx]])
    dist[sy][sx] = 0
    md = 0
    l = []
    while queue:
        y,x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x]=="." and dist[new_y][new_x]==-1:
                    dist[new_y][new_x] = dist[y][x] + 1
                    queue.append([new_y, new_x])
                    md=max(dist[new_y][new_x],md)
    return md

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

ans=0
for i in range(H):
  for j in range(W):
    dist=[[-1]*W for j in range(H)]
    if maze[i][j]!='
      a=bfs(maze,dist,i,j)
      ans=max(a,ans)
print(ans)

Solution (Python):
from collections import deque


def solve(S, s):
    if S[s[0]][s[1]] != ".":
        return -1
    queue = deque([s])
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    visited[s[0]][s[1]] = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1,0], [-1,0], [0,1], [0,-1]):
            new_y, new_x = y+j, x+k
            if new_x in range(W) and new_y in range(H) and S[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])


    return max(map(max,visited))


H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = -1
for i in range(H):
    for l in range(W):
        ans = max(ans, solve(S, [i, l]))
print(ans)

Solution (Python):
from copy import deepcopy
EMP = -1            
BLOCK = -2          

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


maze_map = [[EMP for i in range(w)] for j in range(h)]


pos_list = [[-1,0], [0,-1], [0,1], [1,0]]


for i in range(h):
    input_data = input()
    char_data = list(input_data)

    for j in range(len(char_data)):
        
        if(char_data[j] == "
            maze_map[i][j] = BLOCK


max_mass = 0


for i in range(h):
    for j in range(w):

        
        tmp_maze_map = deepcopy(maze_map)
        queue_list = []

        
        if(tmp_maze_map[i][j] == BLOCK):
            continue
        tmp_maze_map[i][j] = 0

        
        queue_list.append([i,j])

        while(len(queue_list) > 0):
            get_x = queue_list[0][0]
            get_y = queue_list[0][1]

            
            for k in pos_list:
                rin_x = get_x + k[0]
                rin_y = get_y + k[1]
            
                
                if(tmp_maze_map[get_x][get_y] == BLOCK):
                    continue
                
                if((rin_x < 0) or (rin_x >= h) or (rin_y < 0) or (rin_y >= w)):
                    continue
                
                if(tmp_maze_map[rin_x][rin_y] != EMP):
                    continue
                
                tmp_maze_map[rin_x][rin_y] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([rin_x,rin_y])            

            
            queue_list.pop(0)

        
        for k in tmp_maze_map:
            t_sum_list = deepcopy(k)
            t_sum_list += [max_mass]
            max_mass = max(t_sum_list)
            t_sum_list.clear()
        
        
        tmp_maze_map.clear()

print(max_mass)

Solution (Python):
def main():
    h, w = map(int, input().split())
    grid = [input() for _ in [0]*h]
    ans_list = []
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                ans_list.append((i, j))
    m = 0
    for i, j in ans_list:
        q = [(i, j)]
        dist = [[-1]*w for _ in [0]*h]
        cnt = 0
        dist[i][j] = 0
        while q:
            qq = []
            cnt += 1
            while q:
                x, y = q.pop()
                if x > 0:
                    if dist[x-1][y] == -1:
                        if grid[x-1][y] == ".":
                            dist[x-1][y] = cnt
                            qq.append((x-1, y))
                if x < h-1:
                    if dist[x+1][y] == -1:
                        if grid[x+1][y] == ".":
                            dist[x+1][y] = cnt
                            qq.append((x+1, y))
                if y > 0:
                    if dist[x][y-1] == -1:
                        if grid[x][y-1] == ".":
                            dist[x][y-1] = cnt
                            qq.append((x, y-1))
                if y < w-1:
                    if dist[x][y+1] == -1:
                        if grid[x][y+1] == ".":
                            dist[x][y+1] = cnt
                            qq.append((x, y+1))
            q = qq
        m = max(m, max([max([l for l in k]) for k in dist]))
    print(m)


main()

Solution (Python):

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

def dfs(i, j):
    dists = [[-1 for _ in range(W)] for _ in range(H)]
    nexts = ((-1,0), (1,0), (0,-1), (0,1))

    buf = [(i, j)]
    dists[i][j] = 0
    while buf:
        i, j = buf.pop(0)

        for x, y in nexts:
            next_i = i + x
            next_j = j + y
            if 0 <= next_i < H and 0 <= next_j < W:
                if table[next_i][next_j] == '.' and dists[next_i][next_j] == -1:
                    dists[next_i][next_j] = dists[i][j] + 1
                    buf.append((next_i, next_j))


    ret = 0
    for i in range(H):
        for j in range(W):
            ret = max(ret, dists[i][j])

    return ret



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


print(ans)

Solution (Python):
from copy import deepcopy
EMP = -1 
BLOCK = -2

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


maze_map = [[EMP for i in range(w)] for j in range(h)]


for i in range(h):
    input_data = input()
    char_data = list(input_data)

    for j in range(len(char_data)):
        
        if(char_data[j] == "
            maze_map[i][j] = BLOCK


max_mass = 0


for i in range(h):
    for j in range(w):

        
        tmp_maze_map = deepcopy(maze_map)
        queue_list = []

        
        if(tmp_maze_map[i][j] == BLOCK):
            continue
        tmp_maze_map[i][j] = 0

        
        queue_list.append([i,j])

        while(len(queue_list) > 0):
            get_x = queue_list[0][0]
            get_y = queue_list[0][1]

            
            if(not ((get_x == 0) or (tmp_maze_map[get_x][get_y] == BLOCK) or (tmp_maze_map[get_x-1][get_y] != EMP))):
                tmp_maze_map[get_x-1][get_y] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([get_x-1,get_y])

            
            if(not ((get_y == 0) or (tmp_maze_map[get_x][get_y] == BLOCK) or (tmp_maze_map[get_x][get_y-1] != EMP))):
                tmp_maze_map[get_x][get_y-1] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([get_x, get_y-1])

            
            if(not ((get_y == w-1) or (tmp_maze_map[get_x][get_y] == BLOCK) or (tmp_maze_map[get_x][get_y+1] != EMP))):
                tmp_maze_map[get_x][get_y+1] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([get_x, get_y+1])
            
            if(not ((get_x == h-1) or (tmp_maze_map[get_x][get_y] == BLOCK) or (tmp_maze_map[get_x+1][get_y] != EMP))):
                tmp_maze_map[get_x+1][get_y] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([get_x+1,get_y])

            
            queue_list.pop(0)

        
        for k in tmp_maze_map:
            t_sum_list = deepcopy(k)
            t_sum_list += [max_mass]
            max_mass = max(t_sum_list)
            t_sum_list.clear()
        
        
        tmp_maze_map.clear()

print(max_mass)

Solution (Python):
from collections import deque

def bfs(maze, visited, sy, sx):
    queue=deque([[sy, sx]])
    visited[sy][sx]=0
    md=0
    l=[]
    while queue:
        y, x=queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x=y+j, x+k
            if 0<=new_y<R and 0<=new_x<C:
              if maze[new_y][new_x]=="." and visited[new_y][new_x]==-1:
                visited[new_y][new_x]=visited[y][x] + 1
                queue.append([new_y, new_x])
                md=max(visited[new_y][new_x],md)
    return md


R, C=map(int, input().split())

maze=[input() for i in range(R)]
ans=0
for i in range(R):
  for j in range(C):
    visited=[[-1]*C for j in range(R)]
    if maze[i][j]!='
      a=bfs(maze,visited,i,j)
      ans=max(a,ans)
print(ans)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,input().split())
meiro=[input() for _ in range(h)]
n=w*h
e=[[0]*n for _ in range(n)]
d=[(1,0),(0,1),(-1,0),(0,-1)]
for i in range(h):
  for j in range(w):
    if meiro[i][j]==".":
      for x,y in d:
        ni,nj=i+x,j+y
        if 0<=ni<h and 0<=nj<w and meiro[ni][nj]==".":
          e[w*i+j][w*ni+nj]=1

ans=floyd_warshall(e)
INF=float("inf")
print(int(max(max(a if a != INF else 0 for a in a) for a in ans)))

Solution (Python):
H,W=map(int,input().split())
grid=[None]*H
for i in range(H):
  grid[i]=input()
  
from collections import deque
ans=0

INF=10**9
ans=0
for i in range(H):
  for j in range(W):
    dist=[[INF for j in range(W)] for i in range(H)]
    q=deque()
    q.append([i,j,0])
    while q:
      node=q.popleft()
      y=node[0]
      x=node[1]
      d=node[2]
      if grid[y][x]=="
        continue
      if dist[y][x]<=d:
        continue
      if ans<d:
        ans=d
      dist[y][x]=d
      cases=((0,1),(0,-1),(1,0),(-1,0))
      for c in cases:
        if 0<=y+c[0]<H and 0<=x+c[1]<W:
          q.append([y+c[0],x+c[1],d+1])
      
print(ans)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[-1] * (W + 2) for _ in range(H + 2)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                distance[new_x][new_y] = distance[x][y] + 1
                queue.append((new_x, new_y))
        if not queue:
            return distance[x][y]


answer = 0
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if S[i][j] == '
            continue

        cnt = 0
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = dy + j, dx + i
            if S[new_x][new_y] == '.':
                cnt += 1

        if cnt > 2:
            continue

        tmp = bfs(S, (i, j))
        if tmp > answer:
            answer = tmp

print(answer)

Solution (Python):
H, W = map(int, input().split())
l = [input() for i in range(H)]
 
from collections import deque
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

ans = 0
for i in range(H):
    for j in range(W):
        if l[i][j] == '
            continue
        cells = [[None] * W for _ in range(H)]
        cells[i][j] = 0
        q = deque([(i, j)])
        while q:
            y, x = q.popleft()
            for dy, dx in d:
                if 0 <= y+dy < H and 0 <= x+dx < W and l[y+dy][x+dx] == '.' and (cells[y+dy][x+dx] is None or cells[y+dy][x+dx] > cells[y][x]+1):
                    n = cells[y][x] + 1
                    cells[y+dy][x+dx] = n
                    q.append((y+dy, x+dx))
                    if ans < n:
                        ans = n

print(ans)

Solution (Python):
from collections import deque

def bfs(maze, visited, sy, sx, dot_num):
    q = deque([[sy, sx]])
    visited[sy][sx] = 0
    cnt = 1
    while q:
        y, x = q.popleft()
        
        if dot_num == cnt:
            visited_1dim = [0] * H*W
            for i in range(H):
                for j in range(W):
                    visited_1dim[i*W + j] = visited[i][j]
            return max(visited_1dim)
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y <= H-1 and 0 <= new_x <= W-1:
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    q.append([new_y, new_x])
                    cnt += 1
                    
H, W = map(int, input().split())
maze = [input() for i in range(H)]


maze_1dim = [0] * H*W
for y in range(H):
    for x in range(W):
        maze_1dim[y*W + x] = maze[y][x]
dot_num = maze_1dim.count(".")


ans = 0
for y in range(H):
    for x in range(W):
        visited = [[-1]*W for j in range(H)]
        if maze[y][x] == ".":
            ans = max(ans, bfs(maze, visited, y, x, dot_num))
print(ans)

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

queue = []
visited = [] 
ans = 0

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

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

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

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

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

queue = []
visited = [] 
ans = 0
for i in range(h):
    T = [0]*w
    visited.append(T) 


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

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

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