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
from itertools import chain

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
max_d = 400


def bfs(start):
    queue = deque()
    queue.append(start)

    distance = [[max_d] * W for _ in range(H)]
    sx, sy = start
    distance[sx][sy] = 0

    while len(queue) > 0:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if nx >= 0 and nx < H and ny >= 0 and ny < W and maze[nx][ny] == '.' and distance[nx][ny] == max_d:
                queue.append((nx, ny))
                distance[nx][ny] = distance[x][y] + 1

    return max(filter(lambda d: d != max_d, chain.from_iterable(distance)))


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

print(ans)

Solution (Python):
from collections import deque

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


def bfs(sty, stx):
    visited = [[-1]*W for _ in range(H)]
    q = deque()
    visited[sty][stx] = 0
    q.append((sty, stx, 0))


    def is_ok(y, x):
        if not 0 <= y <= H - 1:
            return False
        if not 0 <= x <= W - 1:
            return False
        if visited[y][x] != -1:
            return False
        if maze[y][x] == '
            return False
        return True


    while q:
        y, x, lv = q.popleft()
        for i in (-1, 1):
            if is_ok(y+i, x):
                visited[y+i][x] = lv+1
                q.append((y+i, x, lv+1))
            if is_ok(y, x+i):
                visited[y][x+i] = lv + 1
                q.append((y, x+i, lv+1))

    return max(max(r) for r in visited)

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

print(res)

Solution (Python):
from collections import deque
from itertools import chain
h, w = (int(x) for x in input().split())
s = []
for _ in range(h):
    s.append(list(input()))
dx = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            continue
        d = [[0] * w for i in range(h)]
        for k, sh in enumerate(s):
            for l, sw in enumerate(sh):
                if sw == '
                    d[k][l] = -1
                else:
                    d[k][l] = float('inf')
        que = deque()
        que.append([i, j])
        d[i][j] = 0
        while len(que) > 0:
            qx, qy = que.popleft()
            for x, y in dx:
                nx, ny = qx + x, qy + y
                if 0 <= nx and nx < h and 0 <= ny and ny < w and d[nx][ny] == float('inf'):
                    que.append([nx, ny]) 
                    d[nx][ny] = d[qx][qy] + 1
        ans.append(max(chain.from_iterable(d)))
print(max(ans))

Solution (Python):
from collections import deque

h, w = map(int, input().split())
c = [input() for _ in range(h)]
ans = -1

def bfs(sx, sy):
    que = deque([[sy, sx]])
    d = [[-1] * w for _ in range(h)]
    d[sy][sx] = 0
    res = 0
    while que:
        y, x = que.popleft()
        res = max(res, d[y][x])
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            nx, ny = x+i, y+j
            if 0 <= nx and nx < w and 0 <= ny and ny < h and d[ny][nx] == -1 and c[ny][nx] != "
                nx_, ny_ = nx-i, ny-j
                d[ny][nx] = d[ny_][nx_] + 1
                que.append([ny, nx])
    return res

for i_ in range(h):
    for j_ in range(w):
        if c[i_][j_] != "
            ans = max(ans, bfs( j_, i_))

print(ans)

Solution (Python):
def get_neighbors(S, i):
    n = []
    if S[i]:
        if i >= W: 
            if S[i-W]:
                n += [i-W]
        if i < (H-1)*W:
            if S[i+W]:
                n += [i+W]
        if i % W > 0:
            if S[i-1]:
                n += [i-1]
        if i % W < W-1:
            if S[i+1]:
                n += [i+1]
    return n

import numpy as np
H, W = map(int, raw_input().split())
S = np.empty(H*W, bool)

for i in xrange(H):
    S[i*W:(i+1)*W] = map(lambda x: x==".", raw_input())
    
NR = sum(S) 
NE = [] 
for i in xrange(H*W):
    NE += [get_neighbors(S, i)]

M = np.zeros([H*W, H*W], int)

for i,n in enumerate(NE):
    for j in n:
        M[i,j] = 1
        

I = np.sum(M != 0)
Count = 2

while I < NR *NR:
    a = []
    for i,n in enumerate(NE):
        for j in n:
            a = np.logical_and(M[i] == 0, M[j] == Count-1)
            M[i][a] = Count
    I = np.sum(M != 0)
    Count += 1

np.fill_diagonal(M, 0)
print(M.max())

Solution (Python):
H,W = [int(i) for i in input().split()]
maze = [list(input()) for _ in range(H)]
dica = [[-1] * W for _ in range(H)]
import collections
from collections import deque
import numpy as np
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ans = -1
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            dic = [k[:] for k in dica]
            que = deque()
            que.append([i,j])
            dic[i][j] = 0
            while len(que) != 0:
                k = que.popleft()
                x = k[0]
                y = k[1]
                for l in range(4):
                    nx = x + dx[l]
                    ny = y + dy[l]
                    if nx < 0 or ny < 0 or nx >= H or ny >= W:
                        continue
                    if maze[nx][ny] == "
                        continue
                    if dic[nx][ny] != -1:
                        continue
                    dic[nx][ny] = dic[x][y] + 1
                    que.append([nx,ny])
            arr = np.array(dic)
            M = np.amax(arr)
            if M > ans:
                ans = M
print(ans)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
l = []
for i in range(h):
    s = list(input())
    l.append(s)
q = deque()
s = [[1,0],[0,1],[-1,0],[0,-1]]
def aaa(i,j,h,w):
    if i >= 0 and i <= h-1 and j >= 0 and j <= w-1:
        return True
    else:
        return False
ans = []
for i in range(h):
    for j in range(w):
        if l[i][j] == ".":
            rl = [[-1 for i in range(w)] for j in range(h)]
            rl[i][j] = 0
            q.append([i,j])
            while len(q) > 0:
                a,b = deque.popleft(q)
                for x in s:
                    if aaa(a+x[0],b+x[1],h,w):
                        if l[a+x[0]][b+x[1]] == ".":
                            if rl[a+x[0]][b+x[1]] >= 0:
                                rl[a+x[0]][b+x[1]] = min(rl[a+x[0]][b+x[1]],rl[a][b]+1)
                            else:
                                rl[a+x[0]][b+x[1]] = rl[a][b]+1
                                q.append([a+x[0],b+x[1]])
            for y in range(h):
                ans.append(max(rl[y]))
print(max(ans))

Solution (Python):
from collections import deque
from itertools import product



def bfs(s,x, y):
    
    INF=400
    
    DX = [1, 0, -1, 0]
    DY = [0, 1, 0, -1]
    
    que = deque() 
    res = 0
    dist = [[INF for _ in range(W)] for _ in range(H)]
 
    que.append((x, y))
    dist[x][y] = 0
    while que:
        x, y = que.pop()
        res = max(res, dist[x][y])
 
        for i in range(4):
            dx, dy = x + DX[i], y + DY[i]
 
            if dx < 0 or dx >= H or dy < 0 or dy >= W:
                continue
            if s[dx][dy] == "
                continue
 
            if dist[dx][dy] == 400:
                dist[dx][dy] = dist[x][y] + 1
                que.appendleft((dx, dy))
    return res
 
if __name__=="__main__":
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]


    
    
    ans = 0
    for x, y in product(range(H), range(W)):
        if S[x][y] == "
            continue
        ans = max(ans, bfs(S,x, y))
    print(ans)

Solution (Python):
from collections import deque

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

move=((1,0),(-1,0),(0,1),(0,-1))

def bfs(i,j): 
    if S[i][j] == '
        return 0
    
    visited=[[0]*w for _ in range(h)] 
    visited[i][j]=1 
    
    que=deque([(i,j,0)]) 
    
    while len(que)>0:
        ci,cj,d = que.popleft() 

        for mi,mj in move: 
            ni,nj = ci+mi,cj+mj 
            if 0 <= ni < h and 0 <= nj < w and visited[ni][nj]==0:
                if S[ni][nj] == '.':
                    visited[ni][nj] = 1
                    que.append((ni, nj, d+1))
    return d
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

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    maze.append(input())
flag = True
check = '.'*w
for i in range(h):
    if maze[i] != check:
        flag = False
        break
if flag:
    print(h+w-2)
else:
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                ne = deque([[i,j]])
                dist = [[0]*w for k in range(h)]
                checked = [[0]*w for k in range(h)]
                while len(ne) != 0:
                    cur = ne.popleft()
                    checked[cur[0]][cur[1]] = 1
                    for l in range(4):
                        t = cur[0]+dy_dx[l][0]
                        u = cur[1]+dy_dx[l][1]
                        if (0 <= t <= h-1) and (0 <= u <= w-1):
                            if checked[t][u] == 0:
                                if maze[t][u] == '.':
                                    dist[t][u] = dist[cur[0]][cur[1]]+1
                                    ne.append([t,u])
                                    ans = max(ans,dist[t][u])
    print(ans)

Solution (Python):

from itertools import product

def main():
    field_y_length,field_x_length =  map(int, input().split())
    maze = [input() for i in range(field_y_length)]

    INF = 10**8
    
    max_distance = 0

    def bfs(sy,sx):
        distance = [[INF for i in range(field_x_length)] for j in range(field_y_length)]
        queue = []

        queue.insert(0,(sy,sx))

        distance[sy][sx] = 0

        res = 0

        while len(queue):
            y,x = queue.pop()

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

                if (0 <= nx and nx < field_x_length and 0 <= ny):
                    if (ny < field_y_length and maze[ny][nx] != '
                        if (distance[ny][nx] == INF):
                            queue.insert(0, (ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                            res = max(res,distance[y][x] + 1)
        
        return res

    
    for y,x in product(range(field_y_length),range(field_x_length)):
        if maze[y][x] == '
            continue
        max_distance = max(max_distance,bfs(y,x))
    print(max_distance)
    

if __name__ == "__main__":
    main()

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = 998244353
INF = int(1e15)


def bfs(S, H, W, s):
    if S[s[1]][s[0]] == '
        return 0
    q = []
    q.append(s)
    M = [[-1 for _ in range(W)]for _ in range(H)]
    M[s[1]][s[0]] = 0
    while q != []:
        p = q.pop(0)
        DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for i in range(4):
            n = (p[0] + DIR[i][0], p[1] + DIR[i][1])
            if not (0 <= n[0] < W and 0 <= n[1] < H):
                continue
            if S[n[1]][n[0]] == "
                continue
            if M[n[1]][n[0]] != -1:
                continue
            M[n[1]][n[0]] = M[p[1]][p[0]] + 1
            q.append(n)
    res = 0
    for h in range(H):
        res = max(res, max(M[h]))
    return res


def main():
    
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, bfs(S, H, W, (w, h)))
    print(ans)
    return


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
from itertools import product

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

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


def bfs(x, y):
    que = deque()
    res = 0
    dist = [[-1 for _ in range(W)] for _ in range(H)]

    que.append((x, y))
    dist[x][y] = 0
    while que:
        x, y = que.pop()
        res = max(res, dist[x][y])

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if nx < 0 or nx >= H or ny < 0 or ny >= W:
                continue
            if Shw[nx][ny] == "
                continue

            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                que.appendleft((nx, ny))
    return res


ans = 0
for x, y in product(range(H), range(W)):
    if Shw[x][y] == "
        continue
    ans = max(ans, bfs(x, y))
print(ans)

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


def dist(s, t):
    if r[s][t] == "
        return 0
    else:
        visited = np.zeros((h, w))
        visited[s][t] += 1
        distance = np.zeros((h, w))
        q = deque([[s, t]])
        while len(q) > 0:
            i, j = q.popleft()
            d = distance[i][j] + 1
            if j != w-1:
                if r[i][j+1] == "." and not visited[i][j+1]:
                    q.append([i, j + 1])
                    visited[i][j+1] += 1
                    distance[i][j+1] += d
            if j != 0:
                if r[i][j-1] == "." and not visited[i][j-1]:
                    q.append([i, j - 1])
                    visited[i][j - 1] += 1
                    distance[i][j - 1] += d
            if i != 0:
                if r[i-1][j] == "." and not visited[i-1][j]:
                    q.append([i - 1, j])
                    visited[i-1][j] += 1
                    distance[i-1][j] += d
            if i != h-1:
                if r[i+1][j] == "." and not visited[i+1][j]:
                    q.append([i + 1, j])
                    visited[i+1][j] += 1
                    distance[i+1][j] += d
        return np.max(distance)


ans = 0
for s in range(h):
    for t in range(w):
        ans = max(ans, dist(s, t))

print(int(ans))

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

from heapq import heappop, heappush

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

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

def dfs(x, y):
    dist = [[float("inf")]*w for i in range(h)]
    heap = [(0, x, y)]
    while heap:
        c,x,y = heappop(heap)
        if dist[x][y] <= c:
            continue
        dist[x][y] = c
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if 0<=nx<h and 0<=ny<w and board[nx][ny] == "." and dist[nx][ny] > c+1:
                heappush(heap, (c+1, nx, ny))
    ret = 0
    for i in range(h):
        for j in range(w):
            if dist[i][j] != float("inf"):
                ret = max(ret, dist[i][j])
    return ret

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

print(ans)

Solution (Python):
import sys,copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	H,W = MI()
	maze = [[-1 for _ in range(W)] for _ in range(H)]
	for i in range(H):
		S = IS()
		for j,s in enumerate(S):
			if s == '
				maze[i][j] = '

	def bfs(sx,sy):
		from collections import deque
		que = deque()
		dist_map = copy.deepcopy(maze)
		dist_map[sy][sx]=0
		que.append((sx,sy))
		res = 0
		while len(que) > 0:
			x,y=que.popleft()
			for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
				nx = x+dx
				ny = y+dy
				if(0<=nx<W and 0<=ny<H):
					if(dist_map[ny][nx]==-1):
						dist_map[ny][nx] = dist_map[y][x]+1
						res = max(res, dist_map[ny][nx])
						que.append((nx,ny))
		return res

	ans = -1
	for i in range(H):
		for j in range(W):
			if(maze[i][j]==-1):
				dist = bfs(j,i)
				if(dist > ans):
					ans = dist
	print(ans)

main()

Solution (Python):
import sys,copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	H,W = MI()
	maze = [[-1 for _ in range(W)] for _ in range(H)]
	for i in range(H):
		S = IS()
		for j,s in enumerate(S):
			if s == '
				maze[i][j] = '

	def bfs(sx,sy):
		from collections import deque
		que = deque()
		dist_map = copy.deepcopy(maze)
		dist_map[sy][sx]=0
		que.append((sx,sy))
		res = 0
		while len(que) > 0:
			x,y=que.popleft()
			for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
				nx = x+dx
				ny = y+dy
				if(0<=nx<W and 0<=ny<H):
					if(dist_map[ny][nx]==-1):
						dist_map[ny][nx] = dist_map[y][x]+1
						res = max(res, dist_map[ny][nx])
						que.append((nx,ny))
		return res

	ans = -1
	for i in range(H):
		for j in range(W):
			if(maze[i][j]==-1):
				dist = bfs(j,i)
				if(dist > ans):
					ans = dist
	print(ans)

main()

Solution (Python):
h,w = map(int,input().split())
n = h * w
raw = []
for i in range(h):
  tmp = input()
  add = []
  for j in range(w):
    if tmp[j] == '.':
      add.append(0)
    else:
      add.append(1)
  raw += add
wf = [[1000 for _ in range(n)] for _ in range(n)]
for i in range(n):
  if raw[i] == 0:
    wf[i][i] = 0
    d = []
    if i-w >= 0:
      d.append(i-w)
    if i+w < n:
      d.append(i+w)
    if i%w != 0:
      d.append(i-1)
    if (i+1)%w != 0:
      d.append(i+1)
    for e in d:
      if raw[e] == 0:
        wf[i][e] = 1

  
for k in range(n):
  for i in range(n):
    for j in range(n):
      if wf[i][k] + wf[k][j] < wf[i][j]:
        wf[i][j] = wf[i][k] + wf[k][j]
ans = 0
for i in range(n):
  for j in range(n):
    if ans < wf[i][j] % 1000:
      ans = wf[i][j]
print(ans)

Solution (Python):



import numpy
from itertools import product
from collections import deque

def bfs(maze, s):
  dq = deque()
  count = 0
  dq.append((s[0], s[1], count))
  visited = numpy.zeros(maze.shape, dtype=numpy.int)
  visited[s] = 1
  dxdys = [tuple(map(lambda x:int(x.real), [(0+1j)**(id), (0+1j)**(id+1)])) for id in range(4)]
  while dq:
    x, y, count = dq.popleft()
    for dx, dy in dxdys:
      if x+dx < 0 or y+dy < 0 or maze.shape[0] <= x+dx or maze.shape[1] <= y+dy:
        continue
      if maze[x+dx, y+dy]==1 and visited[x+dx, y+dy]!=1:
        dq.append((x+dx, y+dy, count+1))
        visited[(x+dx, y+dy)] = 1
  return count


def main():
  h, w = map(int, input().strip().split())
  maze = numpy.zeros((h, w), dtype=numpy.int)
  scores = numpy.full((h, w), -1, dtype=numpy.int)
  for ih in range(h):
    maze[ih] = [(0 if c=='
  for sx, sy in product(range(h), range(w)):
    if maze[sx, sy] == 0:
      continue
    scores[sx, sy] = bfs(maze, (sx, sy))
  print(numpy.max([numpy.max(scores), 0]))


if __name__=='__main__':
  main()

Solution (Python):
import math
from collections import deque
import itertools

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


for h in range(H):
    Ss = input().rstrip()
    S.append(Ss)

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

max_cost = 0

for h in range(H):
    for w in range(W):
        if S[h][w] == "
            continue
        que = deque()
        history = [ [-1 for w in range(W)] for h in range(H)]
        que.append([h, w])
        history[h][w] = 0
        current_max_cost = 0
        while len(que) != 0:
            [x, y] = que.pop()
            for i in range(4):
                newx = x + dx[i]
                newy = y + dy[i]
                if 0 <= newx and newx < H and 0 <= newy and newy < W and S[newx][newy] != "
                    history[newx][newy] = history[x][y] + 1
                    que.append([newx, newy])
        current_max_cost = max(list(itertools.chain.from_iterable(history)))
        if max_cost < current_max_cost:
            max_cost = current_max_cost

print(max_cost)

Solution (Python):
import math
from collections import deque
import itertools

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


for h in range(H):
    Ss = input().rstrip()
    S.append(Ss)

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

max_cost = 0

for h in range(H):
    for w in range(W):
        if S[h][w] == "
            continue
        que = deque()
        history = [ [float('inf') for w in range(W)] for h in range(H)]
        que.append([h, w])
        history[h][w] = 0
        current_max_cost = 0
        while len(que) != 0:
            [x, y] = que.popleft()
            for i in range(4):
                newx = x + dx[i]
                newy = y + dy[i]
                if 0 <= newx and newx < H and 0 <= newy and newy < W and S[newx][newy] != "
                    history[newx][newy] = history[x][y] + 1
                    if current_max_cost < history[newx][newy]:
                        current_max_cost = history[newx][newy]
                    que.append([newx, newy])
        if max_cost < current_max_cost:
            max_cost = current_max_cost

print(max_cost)

Solution (Python):
from collections import deque
def bfs(h,w,m,sy,sx):
    INF = 10**12
    max_length = 0
    
    d = [[INF for j in range(w)] for i in range(h)]
    
    
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    
    q = deque([])
    q.append((sx,sy))
    d[sy][sx] = 0
    
    
    while q:
        
        p = q.popleft()
        
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < w and 0 <= ny and ny < h and m[ny][nx] != '
                q.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
                if d[ny][nx] > max_length:
                    max_length = d[ny][nx]
    return max_length

h,w = map(int, input().split())
m = []
max_len = 0
for i in range(h):
    m.append(input())
for i in range(h):
    for j in range(w):
        if m[i][j] == '.':
            length = bfs(h,w,m,i,j)
            if length > max_len:
                max_len = length
print(max_len)

Solution (Python):
H, W = list(map(int, input().split()))


graph = [list(input()) for i in range(H)]

ans = 0
for i in range(H):
    for j in range(W):
        costs = []
        for l in range(H):
            costs.append([-1] * W)
        sy = i
        sx = j
        if graph[sy][sx] == "
            continue
        costs[sy][sx] = 0
        q = [[sy, sx]]
        
        di = [1, -1, 0, 0]
        dj = [0, 0, -1, 1]

        while len(q) != 0:
            y, x = q.pop(0)

            for k in range(4):
                t = y + di[k]
                u = x + dj[k]
                if not (0<=t<H and 0<=u<W):
                    continue
                if graph[t][u] == '
                    continue
                if costs[t][u] != -1:
                    continue
                costs[t][u] = costs[y][x] + 1
                q.append([t, u])
        ans = max(ans, max([max(d) for d in costs]))
print(ans)

Solution (Python):
from collections import deque
INF = 1e9
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]


def bfs(sy,sx):
  if wall[sy][sx] == "
    return 0
  que = deque()
  que.append((sy,sx))
  d[sy][sx] = 0
  m = 0
  
  while len(que) > 0:
    y, x = que.popleft()
    
    for i in range(4):
      ny = y+dy[i]
      nx = x+dx[i]
      if 0 <= ny and ny < h and 0 <= nx and nx < w and wall[ny][nx] != "
        que.append((ny,nx))
        d[ny][nx] = d[y][x]+1
        m = max(d[ny][nx],m)
  return m
     
    
h, w = map(int, input().split())
wall = [list(input()) for _ in range(h)]

ans = 0
for i in range(h):
  for j in range(w):
    d = [[INF]*w for _ in range(h)]
    a = bfs(i,j)
    ans = max(ans,a)
print(ans)

Solution (Python):
import queue

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


def bfs():
    max_dist = 0
    while not que.empty():
        pos = que.get()
        for y, x in zip(dy, dx):
            ty = pos[0] + y
            tx = pos[1] + x
            if ty < 0 or H <= ty:
                continue
            if tx < 0 or W <= tx:
                continue
            if visited[ty][tx]:
                continue
            if S[ty][tx] == "
                continue
            que.put((ty, tx, pos[2] + 1))
            visited[ty][tx] = True
            max_dist = max(max_dist, pos[2] + 1)
    return max_dist


H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append([c for c in input()])
ans = 0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == "
            continue
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[sy][sx] = True
        que = queue.Queue()
        que.put((sy, sx, 0))
        ans = max(ans, bfs())
print(ans)

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)])
        max_d = 0

        while q:
            i, j = q.popleft()
            max_d = max(max_d, dist[i][j])
            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_d
   
    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 itertools import product
import queue
 
H, W = map(int, input().split())
road_grid = list()
for _ in range(H):
  road_grid.append(input())




furthest_so_far = -1
for y_init, x_init in product(range(H), range(W)):
    if road_grid[y_init][x_init] == "
    boundary = queue.Queue()
    boundary.put((y_init, x_init))
    steps_taken = [[-1]*W for _ in range(H)]
    steps_taken[y_init][x_init] = 0
    while not boundary.empty():
        y, x = boundary.get()
        neighbours = [(y+1, x), (y, x+1), (y-1, x), (y, x-1)]
        for (new_y, new_x) in neighbours:
            if (0 <= new_y < H and 0 <= new_x < W
                and steps_taken[new_y][new_x] == -1 and road_grid[new_y][new_x] == "."):
                steps_taken[new_y][new_x] = steps_taken[y][x] + 1
                boundary.put((new_y, new_x))
    furthest_here = max(max(row) for row in steps_taken)
    furthest_so_far = max(furthest_so_far, furthest_here)
print(furthest_so_far)