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

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    while queue:
        x, y = queue.popleft()
        if visited[x][y]:
            continue
        visited[x][y] = True

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


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

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

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp
        if answer == limit:
            print(answer)
            exit()

print(answer)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall



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

maze = [list(input()) for _ in range(H)]


cnt = 0
node_num_dic = {}
for r in range(H):
    for c in range(W):
        if maze[r][c] == '.':
            node_num_dic[(r, c)] = cnt
            cnt += 1

act = [[-1, 0], [0, -1], [1, 0], [0, 1]]
nei_graph = [[0] * (cnt) for _ in range(cnt)]

for r in range(H):
    for c in range(W):
        if maze[r][c] == '.':

            for r_x, c_x in act:
                new_r = r + r_x
                new_c = c + c_x
                if (0 <= new_r <= H - 1) and (0 <= new_c <= W - 1):
                    if maze[new_r][new_c] == '
                        continue

                    from_num = node_num_dic[(r, c)]
                    to_num = node_num_dic[(new_r, new_c)]

                    nei_graph[from_num][to_num] = 1


nei_graph = floyd_warshall(nei_graph, directed=False)

ret = 0
for r in range(cnt):
    for c in range(cnt):
        if nei_graph[r][c] != float('inf'):
            ret = max(ret, nei_graph[r][c])

print(int(ret))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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

    S = ["" for _ in range(H)]
    for i in range(H):
        S[i] = input()

    INF = float("inf")
    N = H*W
    dp = [[INF for _ in range(N)] for _ in range(N)]

    for i in range(H):
        for j in range(W):
            
            if j != W-1 and S[i][j] == "." and S[i][j+1] == ".":
                dp[(W*i)+j][(W*i)+j+1] = 1
                dp[(W*i)+j+1][(W*i)+j] = 1

            if i != H-1 and S[i][j] == "." and S[i+1][j] == ".":

                dp[(W*i)+j][(W*(i+1))+j] = 1
                dp[(W*(i+1))+j][(W*i)+j] = 1
        
            dp[(W*i)+j][(W*i)+j] = 0


    N = H*W
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

    ans = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] != INF:
                ans = max(ans, dp[i][j])
    
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import copy

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

List = [[0] * W for i in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j] == "
            List[i][j] = -1


def maze(I, J):
    L_Max = 0
    Copy_List = copy.deepcopy(List)
    Copy_List[I][J] = 1

    for a in range(1, 400):
        bre_flag = True
        for m in range(H):
            for n in range(W):
                if Copy_List[m][n] == a:
                    
                    if m - 1 >= 0:
                        if Copy_List[m - 1][n] == 0:
                            Copy_List[m - 1][n] = a + 1
                            bre_flag = False
                    if m + 1 < H:
                        if Copy_List[m + 1][n] == 0:
                            Copy_List[m + 1][n] = a + 1
                            bre_flag = False
                    if n - 1 >= 0:
                        if Copy_List[m][n - 1] == 0:
                            Copy_List[m][n - 1] = a + 1
                            bre_flag = False
                    if n + 1 < W:
                        if Copy_List[m][n + 1] == 0:
                            Copy_List[m][n + 1] = a + 1
                            bre_flag = False

        if bre_flag == True:
            L_Max = a
            
            break

    return L_Max


Max = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            Max = max(Max, maze(i, j))

print(Max-1)

Solution (Python):
h, w = map(int,input().split())
grid = []
grid.append('
for _ in range(h):
    grid.append('
grid.append('
            
from collections import deque
import sys
sys.setrecursionlimit(1000000)


def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

maxstep = 0
step = [[-1] * (w+2) for _ in range(h+2)]
def bfs():
    global maxstep
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    
    que = deque([])
    que.append((s_y, s_x))
    step[s_y][s_x] = 0
    
    while que:
        y, x = que.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if step[ny][nx] == -1 and grid[ny][nx] != "
                que.append((ny, nx))
                step[ny][nx] = step[y][x] + 1

    maxstep = max(max(flatten_2dim(step)), maxstep)
    
for i in range(h+2):
    for j in range(w+2):
        if grid[i][j] == ".":
            s_y, s_x = i, j
            bfs()
            step = [[-1] * (w+2) for _ in range(h+2)]
print(maxstep)

Solution (Python):
import queue

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

s = list()
for l in range(0, h):
    line = input()
    s.append(line)

dx = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def search(start_h, start_w):
    if s[start_h][start_w] == "
        return -1

    cost = [[10000000 for i in range(0, w)] for j in range(0, h)]

    q = queue.Queue()
    q.put((start_h, start_w, 0))
    cost[start_h][start_w] = 0
    while not q.empty():
        current_h, current_w, current_c = q.get()
        

        
        for dw, dh in dx:
            next_h = current_h + dh
            next_w = current_w + dw
            next_c = current_c + 1

            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue

            if s[next_h][next_w] == "
                continue
            else:
                q.put((next_h, next_w, next_c))
                cost[next_h][next_w] = next_c

    tmp = 0
    for a in range(0, w):
        for b in range(0, h):
            if cost[b][a] > 1000:
                continue
            else:
                tmp = max(tmp, cost[b][a])

    return tmp


ans = 0
for i in range(0, w):
    for j in range(0, h):
        
        cost_tmp = search(j, i)
        ans = max(ans, cost_tmp)
        


print(ans)

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


def bfs(start):
	queue = deque([start])
	
	tekazu = [[-1 for _ in range(W+2)] for _ in range(H+2)]
	tekazu[start[0]][start[1]] = 0
	num = 0
	while queue:

		label = queue.pop()
		
			
		if c[label[0] + 1][label[1]] == "." and tekazu[label[0] + 1][label[1]] < 0:
			queue.appendleft([label[0] + 1, label[1]])
			tekazu[label[0] + 1][label[1]] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0] + 1][label[1]])

		if c[label[0] - 1][label[1]] == "." and tekazu[label[0] - 1][label[1]] < 0:
			queue.appendleft([label[0] - 1, label[1]])
			tekazu[label[0] - 1][label[1]] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0] - 1][label[1]])

		if c[label[0]][label[1] + 1] == "." and tekazu[label[0]][label[1] + 1] < 0:
			queue.appendleft([label[0], label[1] + 1])
			tekazu[label[0]][label[1] + 1] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0]][label[1] + 1])

		if c[label[0]][label[1] - 1] == "." and tekazu[label[0]][label[1] - 1] < 0:
			queue.appendleft([label[0], label[1] - 1])
			tekazu[label[0]][label[1] - 1] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0]][label[1] - 1])

	return num

ans = 0
for h in range(1, H+1):
	for w in range(1, W+1):
		if c[h][w] == ".":
			ans = max(ans, bfs([h, w]))
print(ans)

Solution (Python):
def d_maze_master(INF=float('inf')):
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    def bfs(start_row, start_col):
        diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

        def is_inside(row, col):
            return 0 <= row < H and 0 <= col < W

        queue = deque([(start_row, start_col)])
        dist = [[INF for _ in range(W)] for _ in range(H)]
        dist[start_row][start_col] = 0
        while queue:
            row, col = queue.pop()
            for dr, dc in diff:
                nr, nc = row + dr, col + dc
                if is_inside(nr, nc) and Maze[nr][nc] != '
                    queue.appendleft((nr, nc))
                    dist[nr][nc] = dist[row][col] + 1
        return dist

    ans = 0
    for start_row in range(H):
        for start_col in range(W):
            if Maze[start_row][start_col] == '
                continue
            dist = bfs(start_row, start_col)
            for row in range(H):
                for col in range(W):
                    if Maze[row][col] != '
                        ans = max(ans, dist[row][col])
    return ans

print(d_maze_master())

Solution (Python):
from collections import deque
import copy


h, w = map(int,input().split())
li = [["
li += [["
li += [["

ans = 0

for i in range(h+2):
    for j in range(w+2):
        if li[i][j] == ".":
            li[i][j] = -1

for i in range(h+2):
    for j in range(w+2):
        if li[i][j] == "
            continue
        meiro = copy.deepcopy(li)
        d = deque([(i,j)])
        meiro[i][j] = 0

        while len(d) != 0:
            s,t = d.popleft()
            step = meiro[s][t]
            if meiro[s+1][t] == -1:
                meiro[s+1][t] = step + 1
                d.append((s+1,t))
            if meiro[s-1][t] == -1:
                meiro[s-1][t] = step + 1
                d.append((s-1,t))
            if meiro[s][t+1] == -1:
                meiro[s][t+1] = step + 1
                d.append((s,t+1))
            if meiro[s][t-1] == -1:
                meiro[s][t-1] = step + 1
                d.append((s,t-1))
            ans = max(ans,step)

print(ans)

Solution (Python):
import sys
from collections import deque

H, W = map(int, input().split())
S = [input() for a in range(H)]
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

answer = 0

for s_y in range(H):
  for s_x in range(W):
    if S[s_y][s_x] == '.':
      d = [[ 0 for b in range(W)] for a in range(H)]
      e = [[ 0 for b in range(W)] for a in range(H)]
      q = deque([[s_y, s_x]])
      e[s_y][s_x] = 1
      while len(q) > 0:
        y, x = q.popleft()
        for i in range(4):
          ny = y + dy[i]
          nx = x + dx[i]
          if 0 <= nx and nx <= W-1 and 0 <= ny and ny <= H-1 and S[ny][nx] == '.' and e[ny][nx] == 0:
            q.append([ny, nx])
            d[ny][nx] = d[y][x]+1
            e[ny][nx] = 1
      for i in range(H):
        answer = max(answer, max(d[i]))
print(answer)

Solution (Python):
import queue

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

s = []
for i in range(h):
	tmp = input()
	s.append(tmp)

max = 0

def next(x, y, num):
	relist = []
	if x > 0 and s[x-1][y] == '.' and map[x-1][y] == '.':
		relist.append((x-1,y,num+1))
	if y > 0 and s[x][y-1] == '.' and map[x][y-1] == '.':
		relist.append((x,y-1,num+1))
	if x < h-1 and s[x+1][y] == '.' and map[x+1][y] == '.':
		relist.append((x+1,y,num+1))
	if y < w-1 and s[x][y+1] == '.' and map[x][y+1] == '.':
		relist.append((x,y+1,num+1))
	return relist

for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			map = s.copy()
			q = queue.Queue()
			q.put((i, j, 0))
			map[i] = map[i][:j] + '
			while q.empty() == False:
				x, y, num = q.get()
				if num > max:
					max = num
					xy = (i, j)
				list = next(x, y, num)
				for nx, ny, nnum in list:
					q.put((nx,ny,nnum))
					map[nx] = map[nx][:ny] + '

print(max)

Solution (Python):
from collections import deque

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

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = []
    maze.append(['
    for i in range(H):
      maze.append(['
    maze.append((['
    
    ans = -1
    for x in range(1,H+1):
      for y in range(1,W+1):
        if maze[x][y] =='.':
          visited = [[-1]*(W+2) for j in range(H+2)]
          ans = max(ans,bfs(maze,visited,x,y))
          
    print(ans)

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

ans = 0

hjkl = [(0, -1), (1, 0), (-1, 0), (0, 1)]
def bfs(h, w):
    parents = [[0] * W for _ in range(H)]
    queue = deque()
    queue.append((h, w))
    parents[h][w] = 1
    while queue:
        pos = queue.popleft()
        now_dist = parents[pos[0]][pos[1]]
        for i, j in hjkl:
            y, x = pos[0] + i, pos[1] + j
            
            if 0 <= y <= H-1 and 0 <= x <= W-1 and not parents[y][x] and S[y][x] == ".":
                parents[y][x] = now_dist + 1
                queue.append((y, x))
                tmp_ans = now_dist
    return tmp_ans
                
for h in range(H):
    for w in range(W):
        if S[h][w] == "
            continue
        else:
            now = bfs(h, w)
            if now > ans:
                ans = now

print(ans)

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):
H,W = map(int,input().split())
S = []
for h in range(H):
    S.append(input())
from collections import deque
ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "
            Q = deque([])
        else:
            Q = deque([[h,w]])
        count_map = [[-1 for _ in range(W)] for __ in range(H)]
        count_map[h][w] = 0
        while Q:
            q = Q.popleft()
            cnt = count_map[q[0]][q[1]] + 1
            if q[0]-1 >= 0:
                if S[q[0]-1][q[1]] == "." and count_map[q[0]-1][q[1]] == -1:
                    count_map[q[0]-1][q[1]] = cnt
                    Q.append([q[0]-1,q[1]])
            if q[1]-1 >= 0:
                if S[q[0]][q[1]-1] == "." and count_map[q[0]][q[1]-1] == -1:
                    count_map[q[0]][q[1]-1] = cnt
                    Q.append([q[0],q[1]-1])
            if q[0]+1 <= H-1:
                if S[q[0]+1][q[1]] == "." and count_map[q[0]+1][q[1]] == -1:
                    count_map[q[0]+1][q[1]] = cnt
                    Q.append([q[0]+1,q[1]])
            if q[1]+1 <= W-1:
                if S[q[0]][q[1]+1] == "." and count_map[q[0]][q[1]+1] == -1:
                    count_map[q[0]][q[1]+1] = cnt
                    Q.append([q[0],q[1]+1])
        temp_max = 0
        for cm in count_map:
            temp_max = max(temp_max,max(cm))
        ans = max(ans,temp_max)
print(ans)

Solution (Python):
h,w = map(int,input().split())
maze = [["
import copy

def f(i,j):
  arr = []
  if done[i][j+1] == 0 and maze[i][j+1] == ".":
    arr.append([i,j+1])
    done[i][j+1] = 1
  if done[i][j-1] == 0 and maze[i][j-1] == ".":
    arr.append([i,j-1])
    done[i][j-1] = 1
  if done[i+1][j] == 0 and maze[i+1][j] == ".":
    arr.append([i+1,j])
    done[i+1][j] = 1
  if done[i-1][j] == 0 and maze[i-1][j] == ".":
    arr.append([i-1,j])
    done[i-1][j] = 1
  return arr

ans = 0

for i in range(1,h+1):
  for  j in range(1,w+1):
    if maze[i][j] == "
      continue
    done = [[1]*(w+2)]+[[1]+[0]*w +[1] for _ in range(h)]+[[1]*(w+2)]
    next_wait = [[i,j]]
    done[i][j] = 1
    cnt = 0
    while next_wait:
      wait = copy.copy(next_wait)
      next_wait = []
      
      while wait:
        now = wait.pop()
        next_wait += f(now[0],now[1])
      cnt += 1
    ans = max(ans,cnt)
print(max(0,ans-1))

Solution (Python):
import queue

h, w = map(int, input().split())
maze = [[(False, False, False, False) for _ in range(w)] for _ in range(h)]
inputs = [list(map(lambda x: x == "

def bfs(x, y):
    q = queue.Queue()
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[x][y] = True
    q.put((x, y, 0))

    max_length = 0

    while not q.empty():
        vx, vy, length = q.get()
        if inputs[vx][vy]:
            continue
        max_length = max(max_length, length)
        print(x, y, vx, vy)
        (ue, migi, hidari, shita) = maze[vx][vy]
        if not ue:
            if not visited[vx - 1][vy]:
                visited[vx - 1][vy] = True
                q.put((vx - 1, vy, length + 1))
        if not migi:
            if not visited[vx][vy + 1]:
                visited[vx][vy + 1] = True
                q.put((vx, vy + 1, length + 1))
        if not hidari:
            if not visited[vx][vy - 1]:
                visited[vx][vy - 1] = True
                q.put((vx, vy - 1, length + 1))
        if not shita:
            if not visited[vx + 1][vy]:
                visited[vx + 1][vy] = True
                q.put((vx + 1, vy, length + 1))
    
    return max_length

for x in range(h):
    for y in range(w):
        ue = (x == 0) or inputs[x - 1][y]
        migi = (y == w - 1) or inputs[x][y + 1]
        hidari = (y == 0) or inputs[x][y - 1]
        shita = (x == h - 1) or inputs[x + 1][y]

        maze[x][y] = (ue, migi, hidari, shita)

result = 0

def bfs(x, y):
    q = queue.Queue()
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[x][y] = True
    q.put((x, y, 0))

    max_length = 0

    while not q.empty():
        vx, vy, length = q.get()
        max_length = max(max_length, length)
        (ue, migi, hidari, shita) = maze[vx][vy]
        if not ue:
            if not visited[vx - 1][vy]:
                visited[vx - 1][vy] = True
                q.put((vx - 1, vy, length + 1))
        if not migi:
            if not visited[vx][vy + 1]:
                visited[vx][vy + 1] = True
                q.put((vx, vy + 1, length + 1))
        if not hidari:
            if not visited[vx][vy - 1]:
                visited[vx][vy - 1] = True
                q.put((vx, vy - 1, length + 1))
        if not shita:
            if not visited[vx + 1][vy]:
                visited[vx + 1][vy] = True
                q.put((vx + 1, vy, length + 1))
    
    return max_length

for x in range(h):
    for y in range(w):
        point = maze[x][y]
        if not inputs[x][y] and sum(point) >= 2:
            result = max(result, bfs(x, y))

print(result)

Solution (Python):
import queue

def solve(maze, start):
    if maze[start[0]][start[1]] == '
        return 0

    q = queue.Queue()
    q.put((start, 0))

    h = len(maze)
    w = len(maze[0])

    memo = [[False] * w for _ in range(h)]
    memo[start[0]][start[1]] = True

    ans = 0

    while not q.empty():
        p, i = q.get()
        ans = i

        if p[0] < h-1 and not memo[p[0] + 1][p[1]] and maze[p[0] + 1][p[1]] == '.':
            q.put(((p[0] + 1, p[1]), i + 1))
            memo[p[0] + 1][p[1]] = True

        if p[0] > 0 and not memo[p[0] - 1][p[1]] and maze[p[0] - 1][p[1]] == '.':
            q.put(((p[0] - 1, p[1]), i + 1))
            memo[p[0] - 1][p[1]] = True

        if p[1] < w-1 and not memo[p[0]][p[1] + 1] and maze[p[0]][p[1] + 1] == '.':
            q.put(((p[0], p[1] + 1), i + 1))
            memo[p[0]][p[1] + 1] = True

        if p[1] > 0 and not memo[p[0]][p[1] - 1] and maze[p[0]][p[1] - 1] == '.':
            q.put(((p[0], p[1] - 1), i + 1))
            memo[p[0]][p[1] - 1] = True

    return ans


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

maze = []
for i in range(h):
    s = list(input())
    maze.append(s)

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, solve(maze, (i, j)))

print(ans)

Solution (Python):
from collections import deque
H,W = map(int,input().split())

S = []

def bfs(maze,sy, sx):
    visited = [[-1 for i in range(W)] for j in range(H)]
    queue = deque()
    queue.append([sy, sx])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <=new_y<=H-1 and 0<= new_x<=W-1:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    maxa = 0
    for i in range(H):
        maxa = max(maxa,max(visited[i]))
    for i in range(H):
        if maxa in visited[i]:
            ret = [i,visited[i].index(maxa)]
            break
    return ret
def bfs2(maze,sy, sx):
    visited = [[-1 for i in range(W)] for j in range(H)]
    queue = deque()
    queue.append([sy, sx])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <=new_y<=H-1 and 0<= new_x<=W-1:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    maxa = 0
    for i in range(H):
        maxa = max(maxa,max(visited[i]))
    return maxa
    

for i in range(H):
    s = list(input())
    S.append(s)
ans2 = []
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            start = [i,S[i].index('.')]
            ret = bfs(S,start[0],start[1])
            ans = bfs2(S,ret[0],ret[1])
            ans2.append(ans)

print(max(ans2))

Solution (Python):
import math
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall


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

S = []










for i in range(H):
    tmp = list(input())
    S.append([t for t in tmp])

d = [[10**9 for _ in range(H*W)] for _ in range(H*W) ]
for i in range((H)*W):
    if i == H*W-1:
        pass 
    elif i % W == W-1:
        if S[i//W][i%W] == ".":
            if S[i//W+1][i%W] == ".":
                d[i][i+W] = 1
                d[i+W][i] = 1
    elif i > (H-1)*W-1:
        if S[i//W][i%W] == ".":
            if S[i//W][i%W+1] == ".":
                d[i][i+1] = 1
                d[i+1][i] = 1

    else:
        if S[i//W][i%W] == ".":
            if S[i//W+1][i%W] == ".":
                d[i][i+W] = 1
                d[i+W][i] = 1
            if S[i//W][i%W+1] == ".":
                d[i][i+1] = 1
                d[i+1][i] = 1
n = H*W


G = csgraph_from_dense(d, null_value=10**9)
x = floyd_warshall(G)

ans = 0
for x_ in x:
    for xx in x_:
        if xx < 10000 and xx > ans:
            ans = xx
print(int(ans))

Solution (Python):



INF = 10**9

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

    from collections import deque
    d = deque()
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                d.append([i, j])

    ans = 0
    while len(d) != 0:
        x, y = d.popleft()
        
        sc = [[-1] * (w) for i in range(h)]
        sc[x][y] = 0
        
        dd = deque()
        dd.append([x,y])

        while len(dd) != 0:
            
            
            ix, iy = dd.popleft()
            for k in range(4):
                i = dx[k]
                j = dy[k]
                
                if 0 <= ix+i < h and 0 <= iy+j < w:
                    if s[ix+i][iy+j] == '.':
                        if sc[ix+i][iy+j] == -1:
                            sc[ix+i][iy+j] = sc[ix][iy]+1   
                            dd.append([ix+i, iy+j])
                    
                            
        
        
        
        ans = max(ans, max([max(i) for i in sc]))
    
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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


def bfs(h, w, s, s_h, s_w):
    if s[s_h][s_w] == '
        return 0
    d_max = 0
    pas = [[-1 for _ in range(w)] for _ in range(h)]
    dist = [[-1 for _ in range(w)] for _ in range(h)]
    dist[s_h][s_w], pas[s_h][s_w] = 0, 's'
    que = deque()
    que.append((s_h, s_w))
    while len(que) > 0:
        q = que.popleft()
        near = [(q[0]+1, q[1]), (q[0], q[1]+1), (q[0]-1, q[1]), (q[0], q[1]-1)]
        for i in near:
            if (i[0] < 0) | (i[0] >= h) | (i[1] < 0) | (i[1] >= w):
                continue
            if (dist[i[0]][i[1]] == -1) & (s[i[0]][i[1]] == '.'):
                dist[i[0]][i[1]] = dist[q[0]][q[1]] + 1
                pas[i[0]][i[1]] = q
                que.append(i)
                d_max = max(dist[q[0]][q[1]] + 1, d_max)
    return d_max


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

Solution (Python):
def warshall_floyd(V, E):
    INF = 10 ** 9
    d = [[0 for _ in range(V + 1)]] + [[0] + [INF for j in range(V)] for i in range(V)]
    for i in range(V + 1):
        d[i][i] = 0
    for i, j in E:
        d[i][j] = 1
        d[j][i] = 1
    for k in range(1, V + 1):
        for i in range(1, V):
            for j in range(i, V + 1):
                dk = d[i][k] + d[k][j]
                if d[i][j] > dk:
                    d[i][j] = dk
                    d[j][i] = dk
    return d


h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
n = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            n += 1
            s[i][j] = n
        else:
            s[i][j] = 0


E = []
for i in range(h):
    for j in range(w):
        p = s[i][j]
        if p > 0:
            if j < w - 1:
                p1 = s[i][j + 1]
                if p1 > 0:
                    E.append([p, p1])
            if i < h - 1:
                p2 = s[i + 1][j]
                if p2 > 0:
                    E.append([p, p2])

ans = 0
INF = 10 ** 9
D = warshall_floyd(n, E)
ans = max(list(map(max, D)))
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
import numpy as np
from heapq import heappop, heappush
 
H,W = map(int,readline().split())
grid = np.full((H+2,W+2),b'
grid[1:-1,1:-1] = np.frombuffer(read(),'S1').reshape(H,-1)[:,:W]
INF = 400
def shortest(grid, start, cost=0):
    dist = np.array([[INF for _ in range(W+2)] for _ in range(H+2)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    st = [(cost, start)]
    dist[start[0]][start[1]]=0
    while(st):
        c, [sx, sy] = heappop(st)
        for a, b in zip(dx, dy):
            x = sx + a
            y = sy + b
            if grid[x][y]==b'
              continue
            dxy = dist[sx][sy] + 1
            if dist[x][y] <= dxy:
                continue
            dist[x][y] = dxy
            heappush(st, (dist[x][y], [x, y]))
    return dist

m=0
for i in range(1,H+1):
  for j in range(1,W+1):
    if grid[i,j]==b'
      continue
    res=shortest(grid, [i,j], cost=0)[1:-1,1:-1]
    res[res==400]=0
    tm=np.max(res)
    if m < tm:
      m=tm
print(m)