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 copy import deepcopy
temp=list(map(int, input().split()))
R=temp[0]
C=temp[1]

color=np.zeros((R,C)).astype(int)

for i in range(R):
  temp=input()
  a=np.zeros(C).astype(int)
  for j in range(C):
      if temp[j]=='
        a[j]=1
      else:
        a[j]=0
  color[i]=a
  
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<R and v[1]>=0 and v[1]<C:
        adj.append(v)
  return adj  

def BFS(s,c,d):
  ma=0
  Q=[s]
  while Q !=[]:
    u=Q[0]
    del Q[0]
    if d[u[0],u[1]]>ma:
      ma=d[u[0],u[1]]
    for v in Adj(u):  
      if c[v[0],v[1]]==0:
        c[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.append(v)
  return ma
        
def main():
  ma=0
  for sx in range(R):
    for sy in range(C):
      if color[sx,sy]==0:
        d=np.zeros((R,C)).astype(int)
        c=deepcopy(color)
        c[sx,sy]=1
        ma=max(BFS((sx,sy),c,d),ma)
  print(ma)

main()

Solution (Python):
from collections import deque

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

for _ in range(h):
    s = str(input())
    new_s = ['
    for x in s:
        new_s.append(x)
    new_s.append('
    S.append(new_s)
S.append(['

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

max_length = 0

for zahyou in Possible_list:
    dq = deque()
    Visited = [-1 for _ in range(len(Possible_list))]
    Visited[Possible_list.index(zahyou)] = 0
    dq.append(zahyou)
    
    while dq:
        now = dq.popleft()
        
        Adj_possible = []
        if (now[0]-1, now[1]) in Possible_list:
            Adj_possible.append((now[0]-1, now[1]))
        if (now[0]+1, now[1]) in Possible_list:
            Adj_possible.append((now[0]+1, now[1]))
        if (now[0], now[1]-1) in Possible_list:
            Adj_possible.append((now[0], now[1]-1))
        if (now[0], now[1]+1) in Possible_list:
            Adj_possible.append((now[0], now[1]+1))
        
        for next_zahyou in Adj_possible:
            if Visited[Possible_list.index(next_zahyou)] != -1:
                continue
            Visited[Possible_list.index(next_zahyou)] = Visited[Possible_list.index(now)] + 1
            dq.append(next_zahyou)
    
    max_length = max(max_length, max(Visited))

print(max_length)

Solution (Python):
import queue
import copy
def main():
    h,w = map(int,input().split())
    maze = []
    maze.append(['
    for i in range(h):
        tmp = input()
        tmp = list('
        maze.append(tmp)
    maze.append(['
    

    dx_ = [0,1,0,-1]
    dy_ = [1,0,-1,0]
    ans = -1
    q = queue.Queue()
    for i in range(1,h+1):
        for j in range(1,w+1):
            new_maze = copy.deepcopy(maze)
            
            dis = [[-1 for a in range(w+2)]for b in range(h+2)]
            
            
            

            if new_maze[i][j]=='.':
                dis[i][j]=0
                q.put([i,j])
            max_dis = -1
            while(not q.empty()):
                [x,y] = q.get()
                new_maze[x][y]='
                
                if max_dis < dis[x][y]:
                    max_dis = dis[x][y]

                for dx,dy in zip(dx_,dy_):
                    
                    if dis[x+dx][y+dy] == -1 and new_maze[x+dx][y+dy] != '
                        
                        dis[x+dx][y+dy] = dis[x][y]+1
                        q.put([x+dx,y+dy])
                        

                        
                        
                        
            
            if ans < max_dis:
                ans = max_dis

            
    print(ans)
    return 0


if __name__ == "__main__":
    main()

Solution (Python):
h, w = map(int, input().split())
maze = [input() for _ in [0] * h]
visited = [[0] * w for _ in [0] * h]


def bfs(start, visited, maze, lim_y, lim_x):
    queue = [start]
    visited[start[0]][start[1]] = 1
    distance = {(start[0], start[1]): 0}
    while queue:
        y, x = queue.pop(0)
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            y_, x_ = y + i, x + j
            if -1 < y_ < lim_y and -1 < x_ < lim_x and maze[y_][x_] == '.' and visited[y_][x_] == 0:
                queue.append([y_, x_])
                visited[y_][x_] = 1
                distance[(y_, x_)] = distance[(y, x)] + 1
    return max(distance.values())


max_distance = 0

all_yx = [[j, i] for i in range(w) for j in range(h)]

for start in all_yx:
    if maze[start[0]][start[1]] == '.':
        max_distance = max(max_distance, bfs(
            start, visited, maze, h, w))
        visited = [[0] * w for _ in [0] * h]

print(max_distance)

Solution (Python):
import copy

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

max_steps = 0

for i in range(h):
    for j in range(w):
        maze_search = copy.deepcopy(maze)
        if maze_search[i][j] == "
            continue
        
        maze_search[i][j] = 0
        numbered_area = [[i, j]]
        step_num = 0
        
        while True:
            
            if not numbered_area:
                if step_num - 1 > max_steps:
                    max_steps = step_num - 1
                break

            step_num += 1
            
            numbered_area_new = []
            for point in numbered_area:
                if point[0] < h - 1 and maze_search[point[0] + 1][point[1]] == ".":
                    maze_search[point[0] + 1][point[1]] = step_num
                    numbered_area_new.append([point[0] + 1, point[1]])
                
                if point[0] > 0 and maze_search[point[0] - 1][point[1]] == ".":
                    maze_search[point[0] - 1][point[1]] = step_num
                    numbered_area_new.append([point[0] - 1, point[1]])
                
                if point[1] < w - 1 and maze_search[point[0]][point[1] + 1] == ".":
                    maze_search[point[0]][point[1] + 1] = step_num
                    numbered_area_new.append([point[0], point[1] + 1])
                
                if point[1] > 0 and maze_search[point[0]][point[1] - 1] == ".":
                    maze_search[point[0]][point[1] - 1] = step_num
                    numbered_area_new.append([point[0], point[1] - 1])
            
            numbered_area = copy.deepcopy(numbered_area_new)
                
print(max_steps)

Solution (Python):
from queue import Queue

def bfs(HW, q, x, y):
    num = 0
    mem = [[-1]*(W+1) for i in range(H+1)]
    max_dist = 0
    mem[x][y] = 0
    while not q.empty():
        current = q.get()
        if current[0] >= H or current[0] < 0 or current[1] >= W or current[1] < 0:
            continue
        if HW[current[0]][current[1]] == '
            continue
        dist = mem[current[0]][current[1]]
        max_dist = max(max_dist, dist)
        if mem[current[0]+1][current[1]] == -1:
            mem[current[0]+1][current[1]] = dist+1
            q.put([current[0]+1,current[1]])
        if mem[current[0]][current[1]+1] == -1:
            mem[current[0]][current[1]+1] = dist+1
            q.put([current[0],current[1]+1])
        if mem[current[0]-1][current[1]] == -1:
            mem[current[0]-1][current[1]] = dist+1
            q.put([current[0]-1,current[1]])
        if mem[current[0]][current[1]-1] == -1:
            mem[current[0]][current[1]-1] = dist+1
            q.put([current[0],current[1]-1])
    return max_dist


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

HW = [[''] * W for i in range(H)]
for i in range(H):
    h = str(input())
    HW[i] = h

ans = 0
for si in range(H):
    for sj in range(W):
        if HW[si][sj] == '
            continue
        q = Queue()
        q.put([si,sj,0])
        ans = max(ans, bfs(HW, q, si, sj))
print(ans)

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

def resolve():
    H, W = map(int, input().split())

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

    def bfs(st):

        INF = -1
        d = np.full((H, W), INF)

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

        que = deque()
        que.append(st)
        d[st[1]][st[0]] = 0

        while len(que):
            p = que.popleft()
            

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

                if nx >= 0 and nx < W and ny >= 0 and ny < H and maze[ny][nx] != "
                    
                    que.append([nx, ny])
                    d[ny][nx] = d[p[1]][p[0]] + 1
                    
                    

        cost = np.max(d)
        
        
        
        return cost

    max_cost = 0
    for y in range(H):
        for x in range(W):
            if maze[y][x] == '.':
                st = [x, y]
                cost = bfs(st)
                if cost > max_cost:
                    max_cost = cost 
    
    
    
    
    print(int(max_cost))

if __name__ == "__main__":
    resolve()

Solution (Python):
import queue
INF = 100000000

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

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

def bfs(sx, sy):
    d = [[-1 for i in range(W)] for j in range(H)]
    d[sx][sy] = 0
    max_d = 0

    q = queue.Queue()
    q.put([sx, sy])

    while not q.empty():
        p = q.get()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx) & (nx < H) & (0 <= ny) & (ny < W):
                if (S[nx][ny] != "
                    d[nx][ny] = d[p[0]][p[1]] + 1
                    q.put([nx, ny])
                    max_d = max(max_d, d[nx][ny])

    return max_d

res = 0
for sx in range(H):
    for sy in range(W):
        if S[sx][sy] == ".":
            res = max(res, bfs(sx, sy))

print(res)

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines







from collections import deque

def main():
	h,w=map(int,input().split())
	s=[list("
	s=[list("
	
	ans=0
	
	for i in range(1,h+1):
		for j in range(1,w+1):
			cnt = ccnt=0
			
			if s[i][j]==".":
				sumi=set()
				Q=deque()
				Q.append((i, j, cnt))
				while Q:
					x,y,cnt=Q.popleft()
					ccnt=max(cnt,ccnt)
					if (x,y) not in sumi:
						sumi.add((x, y))
						if s[x-1][y]==".":
							if (x-1,y) not in sumi:
								Q.append((x-1,y,cnt+1))
						if s[x+1][y]==".":
							if (x+1,y) not in sumi:
								Q.append((x+1,y,cnt+1))
						if s[x][y-1]==".":
							if (x,y-1) not in sumi:
								Q.append((x,y-1,cnt+1))
						if s[x][y+1]==".":
							if (x,y+1) not in sumi:
								Q.append((x,y+1,cnt+1))
							
			ans=max(ans,ccnt)
	
	print(ans)
	
	

if __name__ == "__main__":
	main()

Solution (Python):
def bfs(start, maze, visited):
    queue = [start]
    visited[start[0]][start[1]] = True
    dist = {(start[0], start[1]): 0}
    max_dist = 0
    while queue:
        y, x = queue.pop(0)
        for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            x_, y_ = x + i, y + j
            if y_ >= 0 and y_ < h and x_ >= 0 and x_ < w and maze[y_][x_] == "." and not visited[y_][x_]:
                queue.append((y_, x_))
                visited[y_][x_] = True
                dist[y_, x_] = dist[y, x] + 1
                max_dist = max(max_dist, dist[y_, x_])
    return max_dist


h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
max_dist = 0
for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] == ".":
            visited = [[False for _ in range(w)] for _ in range(h)]
            max_dist = max(max_dist, bfs((sy, sx), maze, visited))
print(max_dist)

Solution (Python):
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
INF = 10 ** 3
(H, W) = list(map(int,input().split()))


S = []
N = H * W
c = [[INF for j in range(N)] for u in range(N)]
d = [[INF for j in range(H*W)] for u in range(H*W)]

for k in range(N):
    c[k][k] = 0
    d[k][k] = 0

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



def vindex(i,j):
    global W
    return W * (i-1) + j -1


for i in range(1,H+1):
    for j in range(1,W+1):
        index = vindex(i,j)
        s = S[i-1][j-1]
        
        if i != 1:
            index_t = vindex(i-1,j)
            sup = S[i-2][j-1]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
                
        if i != H:
            index_t = vindex(i+1,j)
            sup = S[i][j-1]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
        if j != 1:
            index_t = vindex(i,j-1)
            sup = S[i-1][j-2]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
        if j != W:
            index_t = vindex(i,j+1)
            sup = S[i-1][j]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1




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

ans = 0 
for i in range(N):
    for j in range(N):

        if (d[i][j] != INF and d[i][j] > ans):
            ans = d[i][j]

print(ans)

Solution (Python):
from collections import deque

m,n = map(int,list(input().split()))

dirr = ((1,0),(0,1),(-1,0),(0,-1))


def valid(tmp,maze,seen):
    x = tmp[0]
    y = tmp[1]
    if x<0 or y<0 or x>=len(maze) or y>=len(maze[0]) or (tmp in seen) or maze[x][y] == '
        return False
    return True

def bfs(maze,i,j):    
    seen = {(i,j)}
    q = deque()
    q.append((i,j))

    tmpMoves = 0

    while q:
        gen = deque()
        while q:
            curr = q.pop()
            for d in dirr:
                x = curr[0]+d[0]
                y = curr[1]+d[1]
                tmp = (x,y)
                if valid(tmp,maze,seen):
                    gen.append(tmp)
                    seen.add(tmp)

        if not gen:break
        tmpMoves+=1        
        q = gen

    return tmpMoves
    

maze = [['.' for _ in range(n) ] for _ in range(m)]
for i in range(m):
    maze[i] = list(input())


max_moves = 0

for i in range(m):
    for j in range(n):
        if maze[i][j] == '
        ans = bfs(maze,i,j)        
        max_moves = max(ans,max_moves)

print(max_moves)

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


def bfs(h, w):  
    dist = [[-1] * W for iii in range(H)]  
    check_que = deque()
    dist[h][w] = 0
    check_que.append((i, j))
    d = 0
    for m in range(H):
        for n in range(W):
            if S[m][n] == "
                dist[m][n] = -2
    while check_que:
        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 > h_prime or h_prime >= H or 0 > w_prime or w_prime >= W:
                continue
            if dist[h_prime][w_prime] == -1:
                dist[h_prime][w_prime] = d + 1
                check_que.append((h_prime, w_prime))
    return d


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            dis = bfs(i, j)
            if ans < dis:
                ans = dis
print(ans)

Solution (Python):
def warshall_floyd(n, 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

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

s = [float("inf") for i in range(h)]
for i in range(h):
    s[i] = list(input())

n = h*w

d = [[float("inf") for i in range(n)] for j in range(n)]


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

for y in range(h):
    for x in range(w):
        if s[y][x] == '
            continue
        if y-1 >= 0 and s[y-1][x] != '
            d[y*w + x][(y-1)*w+x] = 1
        if y+1 < h and s[y+1][x] != '
            d[y*w + x][(y+1)*w+x] = 1
        if x-1 >= 0 and s[y][x-1] != '
            d[y*w+x][y*w+x-1] = 1
        if x+1 < w and s[y][x+1] != '
            d[y*w+x][y*w+x+1] = 1

d = warshall_floyd(n, d)

ans = 0

for i in range(n):
    for j in range(n):
        if d[i][j] != float("inf"):
            ans = max(ans, d[i][j])

print(ans)

Solution (Python):
def main():
	maximum = 0
	global h, w
	h, w = map(int, input().split())
	street = [[True if z=="." else False for z in input()] for y in range(h)]
	for y in range(h):
		for x in range(w):
			if get(x, y, street):
				r = bfs(x, y, [i[::] for i in street])
				
				
				maximum = max(maximum, r)
	print(maximum)
	return		

def get(x, y, l):
	return l[y][x]

def setter(x, y, z, l):
	l[y][x] = z

def bfs(x, y, visited):
	queue = [(x, y, 0)]
	maximum = 0
	setter(x, y, False, visited)
	for x, y, d in queue:
		if x>0 and get(x-1, y, visited):
			queue.append((x-1, y, d+1))
			setter(x-1, y, False, visited)
		if x<w-1 and get(x+1, y, visited):
			queue.append((x+1, y, d+1))
			setter(x+1, y, False, visited)
		if y>0 and get(x, y-1, visited):
			queue.append((x, y-1, d+1))
			setter(x, y-1, False, visited)
		if y<h-1 and get(x, y+1, visited):
			queue.append((x, y+1, d+1))
			setter(x, y+1, False, visited)
		maximum = max(maximum, d)
	return maximum



main()

Solution (Python):
def main():
	maximum = 0
	global h, w
	h, w = map(int, input().split())
	street = [[None for i in range(w)] for j in range(h)]
	for y in range(h):
		line = input()
		for x, z in enumerate(line):
			street[y][x] = True if z=="." else False
	for y in range(h):
		for x in range(w):
			if get(x, y, street):
				r = bfs(x, y, [i[::] for i in street])
				
				
				maximum = max(maximum, r)
	print(maximum)
	return		

def get(x, y, l):
	return l[y][x]

def setter(x, y, z, l):
	l[y][x] = z

def bfs(x, y, visited):
	queue = [(x, y, 0)]
	maximum = 0
	setter(x, y, False, visited)
	for x, y, d in queue:
		if x>0 and get(x-1, y, visited):
			queue.append((x-1, y, d+1))
			setter(x-1, y, False, visited)
		if x<w-1 and get(x+1, y, visited):
			queue.append((x+1, y, d+1))
			setter(x+1, y, False, visited)
		if y>0 and get(x, y-1, visited):
			queue.append((x, y-1, d+1))
			setter(x, y-1, False, visited)
		if y<h-1 and get(x, y+1, visited):
			queue.append((x, y+1, d+1))
			setter(x, y+1, False, visited)
		maximum = max(maximum, d)
	return maximum



main()

Solution (Python):
from collections import deque

def bfs(maze, h, w, si, sj):
    q = deque([[si, sj]])
    score = [[-1] * w for i in range(h)]
    score[si][sj] = 0
    pattern = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while len(q) > 0:
        i, j = q.popleft()
        for move in pattern:
            ni, nj= i + move[0], j + move[1]
            if ni < 0 or h <= ni or nj < 0 or w <= nj:
                continue
            p = maze[ni][nj]
            if p == '
                continue
            if p == '.' and score[ni][nj] == -1:
                score[ni][nj] = score[i][j] + 1
                q.append([ni, nj])
    return max(map(max, score))

h, w = map(int, input().split())
maze = [input() for i in range(h)]
scores = []
for si in range(h):
    for sj in range(w):
        if maze[si][sj] == "
            continue
        scores.append(bfs(maze, h, w, si, sj))
print(max(scores))

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

ans = 0
for sh in range(H):
    for sw in range(W):
        
        if G[sh][sw] == '
            continue

        
        dist = [[-1] * W for i in range(H)]
        dist[sh][sw] = 0
        que = deque([[sh, sw]])

        while que:
            nh, nw = que.pop()
            for dh, dw in directions:
                
                if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
                    continue

                
                if G[nh + dh][nw + dw] == '
                    continue

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

                dist[nh + dh][nw + dw] = dist[nh][nw] + 1
                que.appendleft([nh + dh, nw + dw])

        ans = max(ans, max([max(d) for d in dist]))

print(ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0

for h in range(H):
  for w in range(W):
    if m[h][w] == "
    q = deque([(h, w, 0)])
    used = set()
    while q:
      h, w, c = q.popleft()
      if (h, w) in used: continue
      ans = max(ans, c)
      if 0 <= h-1 and m[h-1][w] == "." and (h-1, w) not in used: q.append((h-1, w, c+1))
      if h+1 < H  and m[h+1][w] == "." and (h+1, w) not in used: q.append((h+1, w, c+1))
      if 0 <= w-1 and m[h][w-1] == "." and (h, w-1) not in used: q.append((h, w-1, c+1))
      if w+1 < W  and m[h][w+1] == "." and (h, w+1) not in used: q.append((h, w+1, c+1))
      used.add((h, w))
print(ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0

for h in range(H):
  for w in range(W):
    if m[h][w] == "
    q = deque([(h, w, 0)])
    used = set()
    while q:
      h, w, c = q.popleft()
      if (h, w) in used: continue
      ans = max(ans, c)
      if 0 <= h-1 and m[h-1][w] == "." and (h-1, w) not in used: q.append((h-1, w, c+1))
      if h+1 < H  and m[h+1][w] == "." and (h+1, w) not in used: q.append((h+1, w, c+1))
      if 0 <= w-1 and m[h][w-1] == "." and (h, w-1) not in used: q.append((h, w-1, c+1))
      if w+1 < W  and m[h][w+1] == "." and (h, w+1) not in used: q.append((h, w+1, c+1))
      used.add((h, w))
print(ans)

Solution (Python):

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

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

Solution (Python):
def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


INF = float('inf')

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

N = H * W
d = [[INF] * N for _ in range(N)]
for k in range(N):
    d[k][k] = 0

for y in range(H):
    for x in range(W):
        if S[y][x] == '
            continue
        if y - 1 >= 0 and S[y - 1][x] != '
            d[y * W + x][(y - 1) * W + x] = 1
        if y + 1 < H and S[y + 1][x] != '
            d[y * W + x][(y + 1) * W + x] = 1
        if x - 1 >= 0 and S[y][x - 1] != '
            d[y * W + x][y * W + x - 1] = 1
        if x + 1 < W and S[y][x + 1] != '
            d[y * W + x][y * W + x + 1] = 1

warshall_floyd(N, d)

result = 0 
for i in range(N):
    for j in range(N):
        if d[i][j] != INF and d[i][j] > result:
            result = d[i][j]

print(result)

Solution (Python):
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(input()))
res = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] != '.':
            continue
        visited = [[False for _ in range(w)] for _ in range(h)]
        visited[i][j] = True
        queue = [(i, j, 0)]
        while queue:
            c_i, c_j, level = queue.pop(0)

            for n_i, n_j in ((c_i - 1, c_j), (c_i + 1, c_j), (c_i, c_j - 1), (c_i, c_j + 1)):
                if 0 <= n_i < h and 0 <= n_j < w and grid[n_i][n_j] == '.' and visited[n_i][n_j] == False:
                    queue.append((n_i, n_j, level + 1))
                    visited[n_i][n_j] = True
        res = max(res, level)
print(res)

Solution (Python):
import queue

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

max_dist = 0
for h in range(H):
    for w in range(W):
        q = queue.Queue()
        visited=[[False for w in range(W)] for h in range(H)]
        q.put((h, w))
        visited[h][w]=True
        distance = {}
        distance[(h, w)]=0

        while not q.empty():
            x, y = q.get()
            if S[x][y]=='
                continue

            if 0<=x-1 and x-1<=H-1 and 0<=y and y<=W-1:
                if visited[x-1][y]==False and S[x-1][y]=='.':
                    visited[x-1][y]=True
                    q.put((x-1,y))
                    distance[(x-1,y)]=distance[(x,y)]+1
            if 0<=x and x<=H-1 and 0<=y-1 and y-1<=W-1:
                if visited[x][y-1]==False and S[x][y-1]=='.':
                    visited[x][y-1]=True
                    q.put((x,y-1))
                    distance[(x,y-1)]=distance[(x,y)]+1
            if 0<=x+1 and x+1<=H-1 and 0<=y and y<=W-1:
                if visited[x+1][y]==False and S[x+1][y]=='.':
                    visited[x+1][y]=True
                    q.put((x+1,y))
                    distance[(x+1,y)]=distance[(x,y)]+1
            if 0<=x and x<=H-1 and 0<=y+1 and y+1<=W-1:
                if visited[x][y+1]==False and S[x][y+1]=='.':
                    visited[x][y+1]=True
                    q.put((x,y+1))
                    distance[(x,y+1)]=distance[(x,y)]+1
        temp_max_dist = max(distance.values())
        if max_dist<temp_max_dist:
            max_dist = temp_max_dist
print(max_dist)

Solution (Python):



from collections import deque
import numpy as np

INF = pow(10, 8) * (-1)


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


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


def bfs(sx, sy):
  d = [[INF for i in range(W)] for j in range(H)] 
  d_arry = np.array(d)
  que = deque()
  
  que.append([sx, sy])
  d_arry[sx][sy] = 0

  
  while len(que):
    
    pop_pair = que.popleft()
    
    for i in range(4):
      nx = pop_pair[0] + dx[i]
      ny = pop_pair[1] + dy[i]
    
      if 0 <= nx and nx < H and 0 <= ny and ny < W and maze[nx][ny] != '
        que.append([nx, ny])
        d_arry[nx][ny] = d_arry[pop_pair[0]][pop_pair[1]] + 1
    
  return d_arry.max()


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

print(max_distance)

Solution (Python):
import queue

H, W = map(int, input().split())
S = [input() for i in range(H)]
q = queue.Queue()
longest_path = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            g = [[0 if S[k][l] == '.' else -1 for l in range(W)] for k in range(H)]
            q.put((i,j))
            g[i][j] = 0
            while not(q.empty()):
                x, y = q.get()
                for nx, ny in [(x+1, y),(x-1, y),(x, y+1),(x, y-1)]:
                    if nx < 0 or nx > H-1 or ny < 0 or ny > W-1: continue
                    if g[nx][ny] != 0: continue
                    if nx == i and ny == j: continue
                    g[nx][ny] = g[x][y] + 1
                    q.put((nx,ny))
            '''
            print('===========')
            for line in g:
                print(line)
            '''     
            longest_path = max(longest_path, max(map(max, g)))
print(longest_path)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
s = [input() for _ in range(h)]
ans = 0
dir = ((1,0),(0,1),(-1,0),(0,-1))

def bfs(x,y):
  dis_map = [[None if s[i][j] == '.' else -1 for j in range(w)] for i in range(h)]
  q = deque()
  dis_map[y][x] = 0
  q.append((x,y))
  while q:
    i,j = q.popleft()
    for dx,dy in dir:
      ni = i+dx
      nj = j+dy
      if 0 <= ni <= w-1 and 0 <= nj <= h-1:
        if dis_map[nj][ni] == None:
          dis_map[nj][ni] = dis_map[j][i] + 1
          q.append((ni,nj))
  ans =  max(max(dis) for dis in dis_map)
  return ans
  


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

Solution (Python):
from queue import Queue
H, W = map(int, input().split())
MAP = []
for h in range(H):
    MAP.append(input())
MAXIMUM = 0
arrows = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for h in range(H):
    for w in range(W):
        MAX = 0
        Q = Queue()
        CNTS = [[0] * W for h in range(H)]
        RIREKI = [['W'] * W for h in range(H)]
        if MAP[h][w] == '.':
            Q.put((h, w))
        else:
            continue
        while not Q.empty():
            T = Q.get()
            y, x = T[0], T[1]
            
            for arrow in arrows:

                if not ((0 <= y + arrow[0] < H) and (0 <= x + arrow[1] < W)):
                    continue
                
                if MAP[y + arrow[0]][x + arrow[1]] == '.' and RIREKI[y + arrow[0]][x + arrow[1]] == 'W':
                    
                    CNTS[y + arrow[0]][x + arrow[1]] = CNTS[y][x] + 1
                    if MAX < CNTS[y + arrow[0]][x + arrow[1]]:
                        MAX = CNTS[y + arrow[0]][x + arrow[1]]
                    RIREKI[y + arrow[0]][x + arrow[1]] = 'G'
                    Q.put((y + arrow[0], x + arrow[1]))
                else:
                    continue
                RIREKI[y][x] = 'B'
        if MAXIMUM < MAX:
            MAXIMUM = MAX
print(MAXIMUM)