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

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

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

    

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

        while q:
            i, j = q.popleft()
            if i+1 < H and maze[i+1][j] == '.' and dist[i+1][j] == -1:
                q.append((i+1, j))
                dist[i+1][j] = dist[i][j] + 1
            if i-1 >= 0 and maze[i-1][j] == '.' and dist[i-1][j] == -1:
                q.append((i-1, j))
                dist[i-1][j] = dist[i][j] + 1
            if j+1 < W and maze[i][j+1] == '.' and dist[i][j+1] == -1:
                q.append((i, j+1))
                dist[i][j+1] = dist[i][j] + 1
            if j-1 >= 0 and maze[i][j-1] == '.' and dist[i][j-1] == -1:
                q.append((i, j-1))
                dist[i][j-1] = dist[i][j] + 1

        return max(max(i) for i in dist)
   
    ret = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '.':
                ret = max(ret, bfs(i, j))
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

H, W = map(int, input().split())
field = [input() for _ in range(H)]
MOVE = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def dfs(h, w):
    q = deque([(0, (h, w))])
    visited = [[-1] * W for _ in range(H)]
    count = -1
    
    while q:
        count, (y, x) = q.popleft()
        
        if visited[y][x] != -1:
            continue
        
        visited[y][x] = count

        for a, b in MOVE:
            next_x = x + a
            next_y = y + b
            
            if next_x < 0 or next_x >= W or next_y < 0 or next_y >= H:
                continue
            
            if visited[next_y][next_x] != -1:
                continue
            
            if field[next_y][next_x] == '
                continue
            q.append((count + 1, (next_y, next_x)))
    return count


def solve():
    ans = 0
    for h in range(H):
        for w in range(W):
            if field[h][w] == '
                continue
            count = dfs(h, w)
            ans = max(ans, count)
    return ans

print(solve())

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

inf=100000000
ma=[]
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            x=[[inf for i_sub in range(w)] for j_sub in range(h)]
            q=queue.Queue()
            d=0
            q.put([i,j])
            x[i][j]=0
            while q.qsize()!=0:
                d+=1
                l=q.qsize()
                for t in range(l):
                    I,J=q.get()
                    if I-1>=0 and s[I-1][J]=="." and x[I-1][J]==inf:
                        q.put([I-1,J])
                        x[I-1][J]=d
                    if I+1<=h-1 and s[I+1][J]=="." and x[I+1][J]==inf:
                        q.put([I+1,J])
                        x[I+1][J]=d
                    if J-1>=0 and s[I][J-1]=="." and x[I][J-1]==inf:
                        q.put([I,J-1])
                        x[I][J-1]=d
                    if J+1<=w-1 and s[I][J+1]=="." and x[I][J+1]==inf:
                        q.put([I,J+1])
                        x[I][J+1]=d
            ma_sub=0
            for k in range(h):
                for l in range(w):
                    if x[k][l]!=inf:
                        ma_sub=max(ma_sub,x[k][l])
            ma.append(ma_sub)

print(max(ma))

Solution (Python):
import queue
height,width=map(int,input().split())

graph=[input() for _ in range(height)]

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='
            continue

        route = [[-1]*width for _ in range(height)]
        route[h][w] = 0

        
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            nx,ny,nn = q.get()

            for dx,dy in zip(dxs, dys):
                x = nx+dx
                y = ny+dy
                if   width<=x \
                  or height<=y \
                  or x < 0 \
                  or y < 0 \
                  or graph[y][x]=='
                  or route[y][x]!=-1:
                    continue
                route[y][x] = nn + 1
                q.put([x, y, nn+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))

Solution (Python):
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000
wf=[[inf]*(h*w) for i in range(h*w)]
for i in range(h*w):
    k,l=i//w,i%w
    
    if s[k][l]=="
        continue
    if k!=0:
        if s[k-1][l]==".":
            wf[i][i-w]=1
    if k!=h-1:
        if s[k+1][l]==".":
            wf[i][i+w]=1
    if l!=0:
        if s[k][l-1]==".":
            wf[i][i-1]=1
    if l!=w-1:
        if s[k][l+1]==".":
            wf[i][i+1]=1
    wf[i][i]=0
for i in range(h*w):
    for j in range(h*w):
        for k in range(h*w):
            wf[j][k]=min(wf[j][k],wf[j][i]+wf[i][k])
ans=0
for i in range(h*w):
    for j in range(h*w):
        if wf[i][j]!=inf:
            ans=max(ans,wf[i][j])
print(ans)

Solution (Python):




def f(i, j):
    global H, W, S
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


def main():
    global H, W, S
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    result = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != '
                result = max(result, f(i, j))
    print(result)


if __name__ == "__main__":

    main()

Solution (Python):
from collections import deque
from copy import copy

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

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
field_org = [-1] * (W * H)
for j in range(H):
    for i in range(W):
        if S[j][i] == '
            continue
        q = deque()
        q.append((i, j, 0))
        field = copy(field_org)
        field[j * W + i] = 0
        while q:
            p = q.popleft()
            for dx, dy in zip(dxs, dys):
                x, y = p[0] + dx, p[1] + dy
                f_idx = y * W + x
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '
                    continue
                field[f_idx] = p[2] + 1
                q.append((x, y, p[2] + 1))
        cand.append(max(field))
print(max(cand))

Solution (Python):
from collections import deque
from copy import deepcopy

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

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
field_org = [[-1] * W for _ in range(H)]
for j in range(H):
    for i in range(W):
        if S[j][i] == '
            continue
        q = deque()
        q.append((i, j, 0))
        field = deepcopy(field_org)
        field[j][i] = 0
        while q:
            p = q.popleft()
            for dx, dy in zip(dxs, dys):
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '
                    continue
                field[y][x] = p[2] + 1
                q.append((x, y, p[2] + 1))
        cand.append(max(max(row) for row in field))
print(max(cand))

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

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        if S[j][i] == '
            continue
        q = deque()
        q.append((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        field[j][i] = 0
        while q:
            p = q.popleft()
            for dx, dy in zip(dxs, dys):
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '
                    continue
                field[y][x] = p[2] + 1
                q.append((x, y, p[2] + 1))
        cand.append(max(max(row) for row in field))
print(max(cand))

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

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        if S[j][i] == '
            continue
        q = queue.Queue()
        q.put((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        field[j][i] = 0
        while not q.empty():
            p = q.get()
            for dx, dy in zip(dxs, dys):
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '
                    continue
                field[y][x] = p[2] + 1
                q.put((x, y, p[2] + 1))
        cand.append(max(max(row) for row in field))
print(max(cand))

Solution (Python):
import collections as cl
def check(y,x):
    if 0 <= x and x < w and 0 <= y and y < h :
        return True
    else:
        return False

def func():
    while q:
        y,x,count= q.popleft()
        if check(y,x) == False or s[y][x] == '
            continue
        else:
            q.append([y-1,x,count+1])
            q.append([y+1,x,count+1])
            q.append([y,x-1,count+1])
            q.append([y,x+1,count+1])
            ans.append(count)
            conf.add((y,x))
    return max(ans)
q = cl.deque()
conf = set()
h,w = map(int,input().split())
s = []
step_max = []
for i in range(h):
    s.append(list(map(str,input())))
ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            q.append([i,j,0])
            step_max.append(func())
            conf = set()
            ans = []
print(max(step_max))

Solution (Python):
import queue

dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)

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

ans = 0


for y in range(h):
    for x in range(w):
    
        i = 0
        move = [[-1] * w for _ in range(h)]
        
        if(maze[y][x] == '
            continue

        
        q = queue.Queue()
        q.put([x, y])
        move[y][x] = 0

        while not q.empty():
            pos = q.get()
            for i in range(4):
                next = [pos[0] + dx[i], pos[1] + dy[i]]

                
                if(next[0] == w or next[1] == h or next[0] < 0 or next[1] < 0):
                    continue

                if(maze[next[1]][next[0]] == '.' and move[next[1]][next[0]] == -1):
                    move[next[1]][next[0]] = move[pos[1]][pos[0]] + 1
                    q.put(next)
        ans = max([ans] + [max(v) for v in move])

print(ans)

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

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

inf = float('inf')

import queue

ans = 0

for h in range(H):
    for w in range(W):
        if S[h][w] != '
            q = queue.Queue()
            d = [[inf for _ in range(W)] for _ in range(H)]
            
            q.put([h, w])
            d[h][w] = 0
            
            while not q.empty():
                p = q.get()
                
                
                for i in range(4):
                    nx = p[1] + dx[i]
                    ny = p[0] + dy[i]
                    if nx >= 0 and nx < W and ny >= 0 and ny < H and S[ny][nx] != '
                        q.put([ny, nx])
                        d[ny][nx] = d[p[0]][p[1]] + 1
            for hh in range(H):
                for ww in range(W):
                    if d[hh][ww] != inf:
                        ans = max(ans, d[hh][ww])

print(ans)

Solution (Python):
from collections import deque

h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0

for i in range(h):
    for j in range(w):
        if S[i][j]=="
            continue
        else:
            dist=[[inf for _ in range(w)] for _ in range(h)]
            dist[i][j]=0
            queue=deque([(i,j)])
            while queue:
                si,sj=queue.popleft()
                for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                    if 0<=ni<=h-1 and 0<=nj<=w-1 and S[ni][nj] != "
                        if dist[ni][nj] > dist[si][sj] + 1:
                            dist[ni][nj] = dist[si][sj] + 1
                            queue.append((ni, nj))
                max_dist = 0
                for ii in range(h):
                    for jj in range(w):
                        if dist[ii][jj] != inf:
                            max_dist = max(max_dist, dist[ii][jj])
                            ans = max(max_dist,ans)
print(ans)

Solution (Python):
H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10**3

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 m[py][px] == "
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "
                continue
            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 check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False

count=0
def bfs():
    while (q):
        x,y,count=q.popleft()
        
        if check(x,y)==False or (x,y) in finished or c[x][y]=='
            continue

        else:
            q.append([x,y-1,count+1])
            q.append([x,y+1,count+1])
            q.append([x+1,y,count+1])
            q.append([x-1,y,count+1])
            finished.add((x,y))
            bfscount.append(count)

    return max(bfscount)

q = deque()
h,w=map(int,input().split())
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))
ans=[]
bfscount=[]
for i in range(h):
    for j in range(w):
        if c[i][j]==".":
            q.append([i,j,0])
            ans.append(bfs())
            finished = set()
            bfscount=[]
print(max(ans))

Solution (Python):
from collections import deque
def check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False

count=0
def bfs():
    while (q):
        x,y,count=q.popleft()
        
        if check(x,y)==False or (x,y) in finished or c[x][y]=='
            continue

        else:
            q.append([x,y-1,count+1])
            q.append([x,y+1,count+1])
            q.append([x+1,y,count+1])
            q.append([x-1,y,count+1])
            finished.add((x,y))
            bfscount.append(count)

    return max(bfscount)

q = deque()
h,w=map(int,input().split())
global finished 
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))
ans=[]
bfscount=[]
for i in range(h):
    for j in range(w):
        if c[i][j]==".":
            q.append([i,j,0])
            ans.append(bfs())
            finished = set()
            bfscount=[]
print(max(ans))

Solution (Python):

from collections import deque
def check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False

count=0
def bfs():
    while (q):
        x,y,count=q.popleft()
        
        if check(x,y)==False or (x,y) in finished or c[x][y]=='
            continue

        else:
            q.append([x,y-1,count+1])
            q.append([x,y+1,count+1])
            q.append([x+1,y,count+1])
            q.append([x-1,y,count+1])
            finished.add((x,y))
            bfscount.append(count)

    return max(bfscount)

q = deque()
h,w=map(int,input().split())
global finished 
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))
ans=[]
bfscount=[]
for i in range(h):
    for j in range(w):
        if c[i][j]==".":
            q.append([i,j,0])
            ans.append(bfs())
            finished = set()
            bfscount=[]
print(max(ans))

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

def bfs():
    global goal
    
    d=[[float('inf')]*w for _ in range(h)]
    d[st[0]][st[1]]=0
    
    x=[0,1,0,-1]
    y=[1,0,-1,0]

    p=deque([])
    p.append(st)

    while p:
        zahyo=p.popleft()
        for i in range(4):
            nx=zahyo[0]+x[i]
            ny=zahyo[1]+y[i]

            if 0<=nx<=h-1 and 0<=ny<=w-1 and d[nx][ny]==float('inf') and maze[nx][ny]=='.':
                d[nx][ny]=d[zahyo[0]][zahyo[1]]+1
                p.append([nx,ny])
                if goal<d[nx][ny]:
                    goal=d[nx][ny]

goal=0
ans=0

for i in range(h):
    for j in range(w):
        if maze[i][j]=='.':
            st=[i,j]
            bfs()
            if ans<goal:
                ans=goal
print(ans)

Solution (Python):
from collections import deque
import numpy as np
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(sy, sx):
    if s[sy][sx] == '
        return -1
    
    dist = [[-1] * w for _ in range(h)]
    dist[sy][sx] = 0
    dq = deque()
    dq.append((sy, sx))
    while dq:
        y, x = dq.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if s[ny][nx] == '
                    continue
                dist[ny][nx] = dist[y][x] + 1
                dq.append((ny, nx))
    return np.array(dist).max()


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(ans)

Solution (Python):
from collections import deque


def BFS(x,y):
    color=[["white" for i in range(w+2)] for j in range(h+2)]
    D=[[-1 for i in range(w+2)] for j in range(h+2)]

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

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


h,w=map(int,input().split())
S=[["
S.insert(0,["
S.append(["

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):
import copy
import sys
from collections import deque
H,W = (int(_) for _ in input().split())  
f_tmp = []
for _ in range(H):
    f_tmp.append(list(input()))
dp = [[0] * (W+1) for i in range(H+1)]

d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
max_root = 0
for s_i in range(H):
    for s_j in range(W):
        f = copy.deepcopy(f_tmp)
        if f[s_i][s_j] != '
            q = deque()
            q.append([s_i,s_j,0])
            flg = False
            while len(q)>0:
                
                
                node = q.popleft()
                if node is not None:
                    y = node[0]
                    x = node[1]
                    z = node[2]
                    f[y][x] = '
                    for dx, dy in d:
                        nx, ny = x + dx, y + dy
                        if not (0 <= nx < W and 0 <= ny < H) or f[ny][nx] == '
                            
                            continue
                        else:
                            tmp = [ny,nx,z+1]
                            if f[ny][nx] != 'y':
                                q.append(tmp)
                            if f[ny][nx] == 'g' and flg == False:
                                flg = True
                                if max_root < z+1:
                                    max_root = z+1
                            f[ny][nx] = 'y'
                            
                            if max_root < z+1:
                                max_root =z+1
print(max_root)

Solution (Python):
from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype='int')

S=np.zeros_like(T,dtype='int') 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="

d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        
        
        
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype='int')
        
print(d-1)

Solution (Python):
from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)

S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="

d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        
        
        
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype=int)
        
print(d-1)

Solution (Python):
import collections

h, w = map(int, input().split())
s = [[""]*(w+2)]
for _ in range(h):
    _s = list(input())
    _s.insert(0, "")
    _s.append("")
    s.append(_s)
s.append([""]*(w+2))

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

ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j] == "
            continue

        q = collections.deque([[i, j]])

        f = [[-1]*(w+2) for _ in range(h+2)]
        f[i][j] += 1

        while 0 < len(q):
            _x, _y = q.pop()
            for _dx, _dy in zip(dx, dy):
                x = _x + _dx
                y = _y + _dy
                if s[x][y] == "." and f[x][y] == -1:
                    f[x][y] = f[_x][_y] + 1
                    q.appendleft([x, y])

        for _f in f:
            ans = max(ans, max(_f))

print(ans)

Solution (Python):
import sys
from collections import deque

hw = list(map(int, input().split()))
field = [list(input()) for l in range(hw[0])]
ans = 0


direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]

for i in range(hw[0]):
    for j in range(hw[1]):
        
        if field[i][j] == "
            continue
        
        
        costmap = [[-1] * hw[1] for k in range(hw[0])]
        costmap[i][j] = 0
        
        
        que = deque([[i, j]])
        
        while len(que) > 0:
            
            nh, nw = que.popleft()

            
            for dh, dw in direction:

                
                
                if dh + nh > hw[0] - 1:
                    continue
                if dh + nh < 0:
                    continue
                if dw + nw > hw[1] - 1:
                    continue
                if dw + nw < 0:
                    continue 

                
                if field[nh + dh][nw + dw] == "
                    continue

                
                if costmap[nh + dh][nw + dw] != -1:
                    continue

                
                costmap[nh + dh][nw + dw] = costmap[nh][nw] + 1

                
                que.append([nh + dh, nw + dw])
        ans = max(ans, max([max(d) for d in costmap]))
print(ans)

Solution (Python):
import queue

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

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

ans = 0

for i in range(h) :
    for j in range(w) :
        if s[i][j] == '
            continue
        dist = [[-1 for i in range(w)] for j in range(h)]
        q = queue.Queue()
        q.put([j,i])
        dist[i][j] = 0
        cnt = 0
        while not q.empty() :
            xy = q.get()
            for k in range(4) :
                x = xy[0] + dx[k]
                y = xy[1] + dy[k]
                if y < 0 or y >= h or x < 0 or x >= w :
                    continue
                if s[y][x] == '
                    continue
                if dist[y][x] != -1 :
                    continue
                q.put([x, y])
                dist[y][x] = dist[xy[1]][xy[0]] + 1
        for k in range(h) :
            for l in range(w) :
                ans = max(ans, dist[k][l])


print(ans)

Solution (Python):


import sys
from collections import deque
mv = ((1,0),(-1,0),(0,1),(0,-1))
h,w = map(int,input().split())
board = [["
for i in range(h):
    s = input()
    for j in range(w):
        board[i+1][j+1] = str(s[j])
cur_max = 0 


    
for i in range(h+2):
    for j in range(w+2):
        
        tmp =  board[i][j]
        if tmp == ".":
            
            visit = deque()
            start_pos = (i,j)
            visit.append(start_pos)
            cnt = [[-1]*(w+2) for _ in range(h+2)] 
            cnt[i][j] = 0 
            while visit:
                point = visit.popleft()
                
                for k in mv:
                    pos = (point[0]+k[0],point[1]+k[1])
                    
                    if str(board[pos[0]][pos[1]]) == ".":
                        if cnt[pos[0]][pos[1]] == -1: 
                            
                            cnt[pos[0]][pos[1]] = cnt[point[0]][point[1]] + 1
                            visit.append((pos[0],pos[1]))
                            if cnt[pos[0]][pos[1]] > cur_max:
                                cur_max = cnt[pos[0]][pos[1]]
print(cur_max)

Solution (Python):

from collections import deque
INF = int(1e9)
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def main():
    h, w = map(int, input().split())
    maze = [input() for _ in range(h)]

    ans = -1
    for si in range(h):
        for sj in range(w):
            if maze[si][sj] == '
                continue
            
            dist = [[INF for _ in range(w)] for _ in range(h)]
            Q = deque()
            Q.append((si, sj))
            dist[si][sj] = 0
            while len(Q) > 0:
                pi, pj = Q.popleft()

                for di, dj in d:
                    x = pi + di
                    y = pj + dj
                    if (x < 0) | (y < 0) | (x >= h) | (y >= w):
                        continue
                    if maze[x][y] == '
                        continue 
                    if dist[x][y] != INF:
                        continue

                    Q.append((x, y))
                    dist[x][y] = dist[pi][pj] + 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)
main()

Solution (Python):
from collections import deque

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

def bfs(x,y):
  d = deque()
  d.append([x,y,0])
  visited = [[False for i in range(W)] for j in range(H)]
  will_search = [[False for i in range(W)] for j in range(H)]
  maxd = -1
  while len(d) > 0:
    x,y,w = d.popleft()
    visited[x][y] = True
    next_point = []
    for dx,dy in [[1,0], [-1,0], [0,-1], [0,1]]:
      if 0 <= x + dx and x + dx < H and 0 <= y + dy and y + dy < W and S[x+dx][y+dy] == ".":
        next_point.append([x + dx, y + dy])
    for p, q in next_point:
      if visited[p][q]:
        continue
      if will_search[p][q]:
        continue
      d.append([p,q,w+1])
      will_search[p][q] = True
      maxd = max(maxd, w+1)

  return maxd

ans = -1
for X in range(H):
  for Y in range(W):
    if S[X][Y] == "
      continue
    ans = max(bfs(X,Y), ans)
    
print(ans)

Solution (Python):
from collections import deque

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

def bfs(x,y):
  d = deque()
  d.append([x,y,0])
  visited = [[False for i in range(W)] for j in range(H)]
  will_search = [[False for i in range(W)] for j in range(H)]
  maxd = -1
  while len(d) > 0:
    x,y,w = d.popleft()
    visited[x][y] = True
    next_point = []
    for dx,dy in [[1,0], [-1,0], [0,-1], [0,1]]:
      if 0 <= x + dx and x + dx < H and 0 <= y + dy and y + dy < W and S[x+dx][y+dy] == ".":
        next_point.append([x + dx, y + dy])
    for p, q in next_point:
      if visited[p][q]:
        continue
      if will_search[p][q]:
        continue
      d.append([p,q,w+1])
      will_search[p][q] = True
      maxd = max(maxd, w+1)

  return maxd

ans = -1
for X in range(H):
  for Y in range(W):
    if S[X][Y] == "
      continue
    ans = max(bfs(X,Y), ans)
    
print(ans)