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 = [list(input()) for _ in range(h)]

from collections import deque
import numpy as np
def bfs(sy, sx):
    d = [[-1] * w for _ in range(h)]
    que = deque([[sy, sx]])
    d[sy][sx] = 0
    while que:
        y, x = que.popleft()
        
            
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w and 0 <= ny < h and d[ny][nx] == -1 and maze[ny][nx] != "
                d[ny][nx] = d[y][x] + 1
                que.append([ny, nx])
    d = np.array(d)
    return np.max(d)

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

Solution (Python):

from collections import deque
h,w=map(int,input().split())
s=[]

for i in range(h):
    s.append(list(input()))
dx=[1,0,-1,0]
dy=[0,-1,0,1]
ans=0
def search(i,j):
    if s[i][j]=="
        return 0
    max_step=0
    que=deque()
    que.append([i,j])
    dist=[[-1 for _ in range(w)] for _ in range (h)]
    
    dist[i][j]=0
    while que:
        y,x=que.popleft()
        for dir in range(4):
            nx=x+dx[dir]
            ny=y+dy[dir]
            if ny<0 or ny>=h or nx<0 or nx>=w or s[ny][nx]=="
                pass
            elif dist[ny][nx]!=-1:
                pass
            elif s[ny][nx]==".":
            
                dist[ny][nx]=dist[y][x]+1
                que.append([ny,nx])
    out=0
    for i in range(h):
        for j in range(w):
            if dist[i][j]==-1:
                pass
            out=max(out,dist[i][j])
    return out

for i in range(h):
    for j in range(w):
        step=search(i,j)
        if ans<step:
            ans=step
print(ans)

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

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

ans = 0
for x in range(H):
    for y in range(W):
        if maze[x][y] == "
            continue
        distance = [[0]*W for _ in range(H)]
        
        stack = deque([[x,y]])
        
        while stack:
            h,w = stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h, new_w = h+i, w+j
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue
                elif maze[new_h][new_w] != "
                    distance[new_h][new_w] = distance[h][w]+1
                    stack.append([new_h, new_w])
        
        
        distance[x][y] = 0
        
        
        
        
        ans = max(ans, np.max(distance))
        
print(ans)

Solution (Python):
from collections import deque

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

board = []
for row in range(h):
    board.append(list(input()))

def bfs(row, col):
    if board[row][col] == "
        return 0
    max_path = 0
    queue = deque([(row, col)])
    visited[row][col] = 0
    while queue:
        next = queue.popleft()
        if next[0] < h-1 and visited[next[0]+1][next[1]] == -1 and board[next[0]+1][next[1]] == ".":
            visited[next[0]+1][next[1]] = visited[next[0]][next[1]] + 1
            if visited[next[0]][next[1]] + 1 > max_path:
                max_path = visited[next[0]][next[1]] + 1
            queue.append((next[0]+1, next[1]))
        if next[0] > 0 and visited[next[0]-1][next[1]] == -1 and board[next[0]-1][next[1]] == ".":
            visited[next[0]-1][next[1]] = visited[next[0]][next[1]] + 1
            if visited[next[0]][next[1]] + 1 > max_path:
                max_path = visited[next[0]][next[1]] + 1
            queue.append((next[0]-1, next[1]))
        if next[1] < w-1 and visited[next[0]][next[1]+1] == -1 and board[next[0]][next[1]+1] == ".":
            visited[next[0]][next[1]+1] = visited[next[0]][next[1]] + 1
            if visited[next[0]][next[1]] + 1 > max_path:
                max_path = visited[next[0]][next[1]] + 1
            queue.append((next[0], next[1]+1))
        if next[1] > 0 and visited[next[0]][next[1]-1] == -1 and board[next[0]][next[1]-1] == ".":
            visited[next[0]][next[1]-1] = visited[next[0]][next[1]] + 1
            if visited[next[0]][next[1]] + 1 > max_path:
                max_path = visited[next[0]][next[1]] + 1
            queue.append((next[0], next[1]-1))
    return max_path

result = 0
for i in range(h):
    for j in range(w):
        visited = [[-1]*w for _ in range(h)]
        max_path = bfs(i, j)
        if result < max_path:
            result = max_path

print(result)

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

def bfs(maze, visited, sx, sy):
    if s[sx][sy] == "
        return 0
    queue = deque([[sx, sy]])
    visited[sx][sy] = 0
    while queue:
        x, y = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_x, new_y = x + j, y + k
            if (new_x < 0 or new_x >= H or new_y < 0 or new_y >= W or 
            visited[new_x][new_y] != -1 or s[new_x][new_y] == "
                continue
            else:
                visited[new_x][new_y] = visited[x][y] + 1
                queue.append([new_x, new_y])
    return max(np.array(visited).flatten())

H, W = map(int, input().split())
s = []
for _ in range(H):
    s.append([i for i in input()])
ans = 0
for i in range(H):
    for k in range(W):
        visited = [[-1 for _ in range(W)] for _ in range(H)]
        ans = max(ans, bfs(s, visited, i, k))
print(ans)

Solution (Python):
from collections import deque

h, w = list(map(int,input().split()))
s = [list(input()) for _ in range(h)]
dyx = [(1, 0), (-1, 0), (0, 1), (0, -1)]

q = deque()
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=="
            continue
        q.append((i, j))
        d = [ [0] * w for _ in range(h) ]
        while q:
            y, x = q.popleft()
            for dy, dx in dyx:
                ny = y + dy
                nx = x + dx
                if ny == i and nx == j:
                    continue
                if 0 <= ny < h and 0 <= nx < w and d[ny][nx]==0 and s[ny][nx]==".":
                    d[ny][nx] = d[y][x] + 1
                    q.append((ny, nx))

        
        for k in range(h):
            ans = max(ans, max(d[k]))
print(ans)

Solution (Python):
from collections import deque
def farthest(yi,xi):
    q = deque([])
    q.append((yi,xi))
    dis = [[-1]*(w+2) for i in range(h+2)]
    dis[yi][xi] = 0
    while q:
        y,x = q.popleft()
        for i in range(4):
            nexty = y + dy[i]
            nextx = x + dx[i]
            if maze[nexty][nextx] == '.' and dis[nexty][nextx] == -1:
                q.append((nexty,nextx))
                dis[nexty][nextx] = dis[y][x] + 1
    return dis[y][x]
h,w = map(int,input().split())
maze = [['
maze += [['
maze += [['
dx = [-1,0,0,1]
dy = [0,1,-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,farthest(i,j))
print(maxdis)

Solution (Python):
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
dyx=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
q=deque()
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=="
            continue
        q.append((i,j))
        d=[[0]*w for _ in range(h)]
        while q:
            y,x=q.popleft()
            for dy,dx in dyx:
                ny,nx=y+dy,x+dx
                if ny==i and nx==j:
                    continue
                if 0<=ny<h and 0<=nx<w and d[ny][nx]==0 and s[ny][nx]==".":
                    d[ny][nx]=d[y][x]+1
                    q.append((ny,nx))
        for k in range(h):
            ans=max(ans,max(d[k]))
print(ans)

Solution (Python):
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
n=h*w
INF=1<<20
d = [[float("inf") for i in range(n)] for i in range(n)]

dyx=[(1,0),(-1,0),(0,1),(0,-1)]
for i in range(h):
    for j in range(w):
        if s[i][j]=="
            continue
        for dy,dx in dyx:
            if 0<=i+dy<h and 0<=j+dx<w and s[i+dy][j+dx]==".":
                d[i*w+j][(i+dy)*w+j+dx]=1
                d[(i+dy)*w+j+dx][i*w+j]=1



for i in range(n):
    d[i][i] = 0 

x=warshall_floyd(d)
for i in range(n):
    for j in range(n):
        if x[i][j]==float("inf"):
            x[i][j]=-1

ans=0
for i in range(n):
    ans=max(ans,max(x[i]))
print(ans)

Solution (Python):
from collections import deque

def shortestpath(y0, x0):
    step_cnt = [[-1] * (w+2) for _ in range(h+2)]
    step_cnt[y0][x0] = 0
    q.append((y0, x0))
    while q:
        y, x = q.popleft()
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if maze[y_next][x_next] == '.'\
            and step_cnt[y_next][x_next] == -1:
                q.append((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1

    
    return step_cnt[y][x]

h, w = map(int, input().split())
maze = [['
maze += [['
maze += [['
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
q = deque()

max_steps = -1
for y0 in range(1, h+1):
    for x0 in range(1, w+1):
        if maze[y0][x0] != '
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)

Solution (Python):
from collections import deque

def shortestpath(y0, x0):
    step_cnt = [[-1] * w for _ in range(h)]
    step_cnt[y0-1][x0-1] = 0
    q.append((y0, x0))
    while q:
        y, x = q.popleft()
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 1 <= y_next < h+1 and 1 <= x_next < w+1\
            and maze[y_next][x_next] == '.'\
            and step_cnt[y_next-1][x_next-1] == -1:
                q.append((y_next, x_next))
                step_cnt[y_next-1][x_next-1] = step_cnt[y-1][x-1] + 1

    return step_cnt[y-1][x-1]

h, w = map(int, input().split())
maze = [['
maze += [['
maze += [['
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
q = deque()

max_steps = -1
for y0 in range(1, h+1):
    for x0 in range(1, w+1):
        if maze[y0][x0] != '
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)

Solution (Python):
from collections import deque

def shortestpath(y0, x0):
    step_cnt = [[-1] * (w+2) for _ in range(h+2)]
    step_cnt[y0][x0] = 0
    q.append((y0, x0))
    while q:
        y, x = q.popleft()
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 1 <= y_next < h+1 and 1 <= x_next < w+1\
            and maze[y_next][x_next] == '.'\
            and step_cnt[y_next][x_next] == -1:
                q.append((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1

    return step_cnt[y][x]

h, w = map(int, input().split())
maze = [['
maze += [['
maze += [['
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
q = deque()

max_steps = -1
for y0 in range(1, h+1):
    for x0 in range(1, w+1):
        if maze[y0][x0] != '
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)

Solution (Python):
from collections import deque

def shortestpath(y0, x0):
    step_cnt = [[-1] * w for _ in range(h)]
    step_cnt[y0][x0] = 0
    q.append((y0, x0))
    while q:
        y, x = q.popleft()
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 0 <= y_next < h and 0 <= x_next < w\
            and maze[y_next][x_next] == '.'\
            and step_cnt[y_next][x_next] == -1:
                q.append((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1
                    
    return step_cnt[y][x]

h, w = map(int, input().split())      
maze = [[x for x in input()] for _ in range(h)]
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
q = deque()

max_steps = -1
for y0 in range(h):
    for x0 in range(w):
        if maze[y0][x0] != '
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)

Solution (Python):
import queue

def shortestpath(y0, x0):
    step_cnt = [[-1] * w for _ in range(h)]
    step_cnt[y0][x0] = 0
    q.put((y0, x0))
    while not q.empty():
        y, x = q.get()
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 0 <= y_next < h and 0 <= x_next < w\
            and maze[y_next][x_next] == '.'\
            and step_cnt[y_next][x_next] == -1:
                q.put((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1
                    
    return step_cnt[y][x]

h, w = map(int, input().split())      
maze = [[x for x in input()] for _ in range(h)]
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
q = queue.Queue()

max_steps = -1
for y0 in range(h):
    for x0 in range(w):
        if maze[y0][x0] != '
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)

Solution (Python):
from collections import deque


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

starts = []
for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            starts.append((i,j))

step = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ans = 0
for si in starts:
    maxlen = 0
    seen = [[0] * w for _ in range(h)]
    que = deque()
    que.append(si)
    
    while len(que) > 0:
        x, y = que.popleft()
        for xs, ys in step:
            xi, yi = x + xs, y + ys
            if xi < 0 or yi < 0 or xi >= h or yi >= w:
                continue
            if xi == si[0] and yi == si[1]:
                continue
            if S[xi][yi] == '
                continue
            if seen[xi][yi] != 0:
                continue
            else:
                seen[xi][yi] = seen[x][y] + 1
                que.append((xi, yi))
                maxlen = max(maxlen, seen[xi][yi])
    
    ans = max(ans, maxlen)
print(ans)

Solution (Python):
from copy import deepcopy


def solve(maze, i, j, h, w, count):
    distance = 0
    if maze[i][j] == ".":
        distance = 0
        next_search = [(i, j)]
        while not next_search == []:
            now = next_search.pop(0)
            if maze[now[0]][now[1]] == ".":
                maze[now[0]][now[1]] = "
                for direction in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    search = [direction[0] + now[0], direction[1] + now[1]]
                    if search[0] < 0 or h <= search[0] or search[1] < 0 or w <= search[1] or \
                            maze[search[0]][search[1]] == "
                        continue
                    else:
                        count[search[0]][search[1]] = count[now[0]][now[1]] + 1
                        next_search.append(tuple(search))
                        distance = max(distance, count[search[0]][search[1]])
    return distance


def main():
    height, width = map(int, input().split(" "))
    maze = []
    answer = 0
    for _ in range(height):
        maze.append(list(input()))
    count = [[0 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            answer = max(answer, solve(deepcopy(maze), i, j, height, width, deepcopy(count)))
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
from copy import deepcopy


def solve(maze, i, j, h, w, count):
    
    if maze[i][j] == "
        return 0
    else:
        distance = 0
        next_search = [(i, j)]
        while not next_search == []:
            now = next_search.pop(0)
            if maze[now[0]][now[1]] == ".":
                maze[now[0]][now[1]] = "
                for direction in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    search = [direction[0] + now[0], direction[1] + now[1]]
                    if search[0] < 0 or h <= search[0] or search[1] < 0 or w <= search[1] or \
                            maze[search[0]][search[1]] == "
                        continue
                    else:
                        count[search[0]][search[1]] = count[now[0]][now[1]] + 1
                        next_search.append(tuple(search))
                        distance = max(distance, count[search[0]][search[1]])
        return distance


def main():
    height, width = map(int, input().split(" "))
    maze = []
    answer = 0
    for _ in range(height):
        maze.append(list(input()))
    count = [[0 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            answer = max(answer, solve(deepcopy(maze), i, j, height, width, deepcopy(count)))
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
import queue

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] == ".":
            t = [["."]*w for _ in range(h)]
            t[i][j] = 0
            q = queue.Queue()
            q.put((j, i))
            while True:
                x, y = q.get()
                for k, l in (1, 0), (-1, 0), (0, 1), (0, -1):
                    if (0 <= x+k and x+k < w and
                        0 <= y+l and y+l < h and
                        s[y+l][x+k] == "." and t[y+l][x+k] == "."):
                            t[y+l][x+k] = t[y][x] + 1
                            q.put((x+k, y+l))
                            
                if q.empty():
                    ans = max(ans, t[y][x])
                    break
print(ans)

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


from collections import deque
def bfs(maze, dist, sy, sx):
    d = deque()
    d.append([sy, sx])
    while d:
        y, x = d.popleft()
        for dy, dx in [1, 0], [-1, 0], [0, 1], [0, -1]:
            ny = y + dy
            nx = x + dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            if maze[ny][nx] == '
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                d.append([ny, nx])

ans = -1
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '
            continue
        dist = [[-1] * W for _ in range(H)]
        for gy in range(H):
            for gx in range(W):
                if maze[gy][gx] == '
                    continue
                dist[sy][sx] = 0
                bfs(maze, dist, sy, sx)
                ans = max(ans, dist[gy][gx])
print(ans)

Solution (Python):
h,w=map(int,input().split())
data=[]
data.append(list("
for i in range(h):
    s=input()
    s="
    lists=list(s)
    data.append(lists)
data.append("
s=0
uselist=[]
graph={i:[] for i in range(1,h*w+1)}
for i in range(1,h+1):
    for j in range(1,w+1):
        if data[i][j]==".":
            a=w*(i-1)+j
            uselist.append(a)
            if data[i+1][j]==".":
                b=w*(i)+j
                graph[b].append(a)
                graph[a].append(b)

            if data[i][j+1]==".":
                b=w*(i-1)+j+1
                graph[b].append(a)
                graph[a].append(b)

from collections import deque

def how_far_from(s,n):
    d=deque()

    parent=[0 for i in range(n+1)]
    visited=[False for i in range(n+1)]
    visited[s]=True
    d.append((s,0))

    how_far={i:[] for i in range(n+1)}
    while d:
        node=d.popleft()
        for point in graph[node[0]]:
            if visited[point]==False:
      
                visited[point]=True

                d.append((point,node[1]+1))
                how_far[node[1]+1].append(point)

    return how_far
maxi=0
for s in uselist:
    Q=how_far_from(s,h*w)

    for i in range(h*w,-1,-1):
        if Q[i]:
            maxi=max(maxi,i)
            break
print(maxi)

Solution (Python):
import queue
h,w = map(int,input().split())
maze_ = []
ans = 0
for _ in range(h):
    maze = list(input())
    maze_.append(maze)
for i in range(h):
    for j in range(w):
        if maze_[i][j] == ".":
            dist = [[-1]*w for i in range(h)]
            dist[i][j] = 0
            q = queue.Queue()
            q.put([i,j])
            while not q.empty():
                now = q.get()
                y = now[0]
                x = now[1]
                if x>0 and maze_[y][x-1] == "." and dist[y][x-1] == -1:
                    dist[y][x-1] = dist[y][x] + 1
                    q.put([y,x-1])
                if y>0 and maze_[y-1][x] == "." and dist[y-1][x] == -1:
                    dist[y-1][x] = dist[y][x] + 1
                    q.put([y-1,x])
                if x<w-1 and maze_[y][x+1] == "." and dist[y][x+1] == -1:
                    dist[y][x+1] = dist[y][x] + 1
                    q.put([y,x+1])
                if y<h-1 and maze_[y+1][x] == "." and dist[y+1][x] == -1:
                    dist[y+1][x] = dist[y][x] + 1
                    q.put([y+1,x])
            saidai = 0
            for s in range(h):
                for t in range(w):
                    saidai = max(saidai,dist[s][t])
            ans = max(ans,saidai)
print(ans)

Solution (Python):
H,W = map(int,input().split())
graph = [[i for i in input()] for j in range(H)]

def bfs(sx,sy):
  queue = [[sx,sy,0]]
  visited = [[False for i in range(W)] for j in range(H)]
  while queue:
    now = queue.pop(0)
    visited[now[0]][now[1]] = True
    for next in [[1,0],[-1,0],[0,1],[0,-1]]:
      if now[0]+next[0] < 0 or now[1]+next[1] < 0: continue
      if now[0]+next[0] > H-1 or now[1]+next[1] > W-1: continue
      if visited[now[0]+next[0]][now[1]+next[1]]: continue
      if graph[now[0]+next[0]][now[1]+next[1]]=='
      queue.append([now[0]+next[0],now[1]+next[1],now[2]+1])
      visited[now[0]+next[0]][now[1]+next[1]] = True
  return now[2]

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

Solution (Python):
from collections import deque
inf = -1

h,w = map(int,input().split())
s = []
for i in range(h):
    s.append(list(input()))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

def bfs(sx,sy):
    d = [[inf] * w for _ in range(h)]
    que = deque()
    que.append([sx,sy])
    d[sx][sy] = 0
    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != '
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    cnt = 0
    for i in range(h):
        for j in range(w):
            cnt = max(cnt, d[i][j])
    return cnt

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 collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


def bfs(x, y):
    d = [[-1] * w for _ in range(h)]
    q = deque()
    q.append([x, y])
    d[x][y] = 0
    while q:
        p = q.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 s[nx][ny] != '
                    ny] == -1:
                q.append([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    cnt = 0
    for i in range(h):
        for j in range(w):
            cnt = max(cnt, d[i][j])
    return cnt


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):
import collections
from collections import deque

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


for i in range(h):
    maze[i]=['
maze=[['

def clear_maze(sx, sy):

    INF=-10**9
    distance = [[INF for i in range(w+2)] for j in range(h+2)]
    
    def bfs():
        d = deque()
        d.append((sx, sy))
        distance[sx][sy] = 0
        ans=0

        while len(d):
            x, y = d.popleft()

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and  0 <= ny  and maze[nx][ny] != '
                    d.append((nx, ny))
                    distance[nx][ny] = distance[x][y] + 1
                    ans=max(distance[nx][ny],ans)


        return ans

    return bfs()

m=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if maze[i][j] == '.':
            x=clear_maze(i,j)
            m=max(x,m)
print(m)

Solution (Python):
h,w=map(int,input().split())
s=[input() for _ in range(h)]
from collections import deque
ans=0
dd=[(1,0),(-1,0),(0,1),(0,-1)]
for i in range(h):
  for j in range(w):
    if  s[i][j]=="
          continue
    
    g=[[0]*w for _ in range(h)]
    v=[[0]*w for _ in range(h)]
    g[i][j]=1
    q=deque([(j,i)])
    while q:
      x,y=q.popleft()
      for dx,dy in dd:
        nx=x+dx
        ny=y+dy
        if not 0<=nx<w:
          continue
        if not 0<=ny<h:
          continue
        if g[ny][nx]:
          continue
        if s[ny][nx]=="
          continue
        g[ny][nx]=1
        v[ny][nx]=v[y][x]+1
        q.append((nx,ny))
    for ii in v:
      ans=max(ans,max(ii))

print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
G=[["
for i in range(1,h+1):
  G[i]=["
ans=0
for sx in range(1,h+1):
  for sy in range(1,w+1):
    if G[sx][sy]==".":
      B=[[0]*(w+2) for i in range(h+2)]
      for i in range(h+2):
        for j in range(w+2):
          if G[i][j]=="
            B[i][j]=1
      INF=10**4
      A=[[INF]*(w+2) for i in range(h+2)]
      C=[-1,1,0,0]
      D=[0,0,-1,1]
      A[sx][sy]=0
      E=deque([sx,sy])
      while len(E)>0:
        x=E[0]
        E.popleft()
        y=E[0]
        E.popleft()
        B[x][y]=1
        for i in range(4):
          if B[x+C[i]][y+D[i]]==0:
            A[x+C[i]][y+D[i]]=A[x][y]+1
            a=A[x+C[i]][y+D[i]]
            B[x+C[i]][y+D[i]]=1
            E.append(x+C[i])
            E.append(y+D[i])
      if ans<a:
        ans=a
    else:
      continue
print(ans)

Solution (Python):
from collections import deque

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

def bfs(s, start_x, start_y, h, w):
    que = deque()
    que.append((start_x, start_y))
    
    d = [[-1]*w for i in range(h)]
    d[start_y][start_x] = 0
    
    while que:
        (x, y) = que.popleft()
        for (nx, ny) in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if 0 <= nx and nx<w and 0<=ny and ny<h and s[ny][nx]!='
                que.append((nx, ny))
                d[ny][nx] = d[y][x] + 1
                
    answer = 0    
    for i in range(h):
        for j in range(w):
            answer = max(answer, d[i][j])
                        
    return answer

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

Solution (Python):
from collections import deque

def bfs(h,w,s,sx,sy):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    d = [[-1] * w for _ in range(h)]
    d[sx][sy] = 0
    que = deque()
    que.append((sx,sy))
    
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != '
                que.append((nx,ny))
                d[nx][ny] = d[x][y] + 1
    
    md = 0
    for i in range(h):
        for j in range(w):
            md = max(md,d[i][j])
    return md

h,w = [int(_) for _ in input().split()]
s = [0] * h
for i in range(h):
    s[i] = list(input())
    
ans = 0

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

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


def BFS(x, y, M):
    dist = [[-1] * W for i in range(H)]
    quex = deque([x])
    quey = deque([y])
    dist[x][y] = 0

    while quex:
        vx = quex.popleft()
        vy = quey.popleft()
        d = dist[vx][vy]
        for w in D:
            nx = w[0] + vx
            ny = w[1] + vy
            if nx < 0 or H <= nx or ny < 0 or W <= ny:
                continue
            elif dist[nx][ny] > -1 or S[nx][ny] == "
                continue
            dist[nx][ny] = d + 1
            M = max(M, d+1)
            quex.append(nx)
            quey.append(ny)

    return M


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

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

V = H*W
maze = [[INF]*V for _ in range(V)]


for i in range(V):
    maze[i][i] = 0


for py in range(H):
    for px in range(W):
        if s[py][px] == '
        target = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in target:
            if not (0<=x<W and 0<=y<H): continue
            if s[y][x] == '
            maze[W*py+px][W*y+x] = 1


for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=INF]))

Solution (Python):
from collections import deque
 
def bfs(h, w, s, sx, sy):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    d = [[-1] * w for _ in range(h)]
    d[sx][sy] = 0
    que = deque()
    que.append((sx, sy))
 
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != '
                que.append((nx, ny))
                d[nx][ny] = d[x][y] + 1
 
    md = 0
    for i in range(h):
        for j in range(w):
          md = max(md, d[i][j])
 
    return md
 
h, w = [int(_) for _ in input().split()]
s = [0] * h
for i in range(h):
    s[i] = list(input())
 
ans = 0
 
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            ans = max(ans, bfs(h, w, s, i, j))
 
print(ans)