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.



Sample input:
3 3
...
...
...


Sample output:
4

Submission status: Runtime Error

Solution code:
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):
  Q=[s]
  while Q !=[]:
    u=Q[0]
    del Q[0]
    if d[x,y]>ma:
      ma=d[x,y]
    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)
        
def main():
  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)
        BFS((sx,sy),c,d)

ma=0
main()
print(ma)

Submission status: Runtime Error

Solution code:
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[x,y]>ma:
      ma=d[x,y]
    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():
  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)
        ma=BFS((sx,sy),c,d)
  print(ma)
  
main()

Submission status: Runtime Error

Solution code:
import queue
import copy
def main():
    h,w = map(int,input().split())
    maze = []
    maze.append(['#' for i in range(w+2)])
    for i in range(h):
        tmp = input()
        tmp = list('#' + tmp + '#')
        maze.append(tmp)
    maze.append(['#' for i in range(w+2)])
    # print(maze)
    q = queue.Queue()
    dx_ = [0,1,0,-1]
    dy_ = [1,0,-1,0]
    ans = -1
    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)]
            # for a in range(1,h):
            #     for b in range(1,w):
            #         dis[a][b] = -1

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

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

                        # for i in range(len(maze)):
                        #     print(maze[i])
                        # print()
            # print("max is",max_dis)
            if ans < max_dis:
                ans = max_dis

            
    print(ans)
    return 0


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
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 dfs(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()
            # print(p)

            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] != "#" and d[ny][nx] == INF:
                    # print("next is ", nx, ny)
                    que.append([nx, ny])
                    d[ny][nx] = d[p[1]][p[0]] + 1
                    # print(d)
                    # print(que)

        cost = np.max(d)
        idx = np.unravel_index(np.argmax(d), d.shape)
        # print(idx)
        # print(cost)
        return idx, cost

    for y in range(H):
        for x in range(W):
            if maze[y][x] == '.':
                st = [x, y]
                break
        break
    
    idx, cost = dfs(st)
    # print("mid")
    # print(idx)
    idx, cost = dfs((idx[1], idx[0]))
    print(int(cost))

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
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] == "." and maze[gy][gx] == ".":
            visited = [[False for _ in range(w)] for _ in range(h)]
            max_dist = max(max_dist, bfs((sy, sx), maze, visited))
print(max_dist)

Submission status: Runtime Error

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

    dx_ = [0,1,0,-1]
    dy_ = [1,0,-1,0]
    ans = -1
    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)]
            # for a in range(1,h):
            #     for b in range(1,w):
            #         dis[a][b] = -1

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

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

                        # for i in range(len(maze)):
                        #     print(maze[i])
                        # print()
            # print("max is",max_dis)
            if ans < max_dis:
                ans = max_dis

            
    print(ans)
    return 0


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

    dx_ = [0,1,0,-1]
    dy_ = [1,0,-1,0]
    ans = -1
    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)]
            # for a in range(1,h):
            #     for b in range(1,w):
            #         dis[a][b] = -1

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

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

                        # for i in range(len(maze)):
                        #     print(maze[i])
                        # print()
            # print("max is",max_dis)
            if ans < max_dis:
                ans = max_dis

            
    print(ans)
    return 0


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
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])
				print(f"x: {x} and y: {y} and r: {r} and max: {maximum}")
				print(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
	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()

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(maze, h, w, si, sj):
    q = deque([[si, sj]])
    score = [[0] * w for i in range(h)]

    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 not score[ni][nj]:
                score[ni][nj] = score[i][j] + 1
                q.append([ni, nj])
    return max(sum(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):
        memo.append((si, sj))
        if maze[si][sj] == "#":
            continue
        scores.append(bfs(maze, h, w, si, sj))
print(max(scores))

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(maze, h, w, si, sj, gi, gj):
    memo = [[0] * w for i in range(h)]
    q = deque([[si, sj]])
    score = [[0] * w for i in range(h)]

    pattern = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while len(q) > 0:
        i, j = q.popleft()
        if i == gi and j == gj:
            return score[gi][gj]
        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 not score[ni][nj]:
                score[ni][nj] = score[i][j] + 1
                q.append([ni, nj])

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
        for gi in range(h):
            for gj in range(w):
                if maze[gi][gj] == "#" or (si == gi and sj == gj) or (gi, gj) in memo:
                    continue
                scores.append(bfs(maze, h, w, si, sj, gi, gj))
print(max(scores))

Submission status: Runtime Error

Solution code:
def bfs(maze, h, w, si, sj, gi, gj):
    memo = [[0] * w for i in range(h)]
    q = deque([[si, sj]])
    score = [[0] * w for i in range(h)]

    pattern = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while len(q) > 0:
        i, j = q.popleft()
        if i == gi and j == gj:
            return score[gi][gj]
        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 not score[ni][nj]:
                score[ni][nj] = score[i][j] + 1
                q.append([ni, nj])

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
        for gi in range(h):
            for gj in range(w):
                if maze[gi][gj] == "#" or (si == gi and sj == gj):
                    continue
                scores.append(bfs(maze, h, w, si, sj, gi, gj))
print(max(scores))

Submission status: Runtime Error

Solution code:
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[h][w] = True
        queue = [(i, j, 0)]
        while queue:
            c_i, c_j, level = queue.pop(0)
#             visited.append((c_i, c_j))
            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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
import queue

H, W = map(int, input().split())
S = [input() for i in range(H)]
q = queue.LifoQueue()
longest_path = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            g = [[999 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 S[nx][ny] == '#': continue
                    if g[nx][ny] > g[x][y] + 1:
                        g[nx][ny] = g[x][y] + 1
                        q.put((nx,ny))
        longest_path = max(longest_path, max(map(max, g)))
print(longest_path)

Submission status: Runtime Error

Solution code:

Copy
Copy
from collections import deque
h,w = map(int,input().split(" "))
s = [input() for _ in range(h)]
 
ans = 0
direcion = [(1,0),(0,1),(-1,0),(0,-1)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        que = deque([(j,i)])
        dist = [[0]*w for _ in range(h)]
        visited = set()
        visited.add((i,j))
        while que:
            j, i = que.popleft()
            for x,y in direcion:
                n_x,n_y = j+x,i+y
                if not 0 <= n_x < w: continue
                if not 0 <= n_y < h: continue
                if (n_y,n_x) in visited: continue
                if s[n_y][n_x] == "#": continue
                visited.add((n_y,n_x))
                dist[n_y][n_x] = dist[i][j] + 1
                que.append((n_x,n_y))
            ans = max(ans,max(max(row) for row in dist))
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
 
import numpy as np
import copy
from collections import deque
 
n, m = map(int, input().split())
 
# マス目と距離保存のための箱を作成
d = []
mas = []
for i in range(n):
    mas.extend(list(map(list, input().split())))
    d.append([float("nan")] * m)
 
 
def tansaku(sx, sy, d):
    local_d = copy.deepcopy(d)
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
 
    que = deque([])
    que.append((sx, sy))
    local_d[sx][sy] = 0
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        for i in range(4):
            # 移動4方向をループ
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (
                0 <= nx < n
                and 0 <= ny < m
                and mas[nx][ny] != "#"
                and not local_d[nx][ny] == local_d[nx][ny]
            ):
                # 移動できるならキューに入れ，その点の距離を p からの距離 +1 で確定する．最後Nan判定
                que.append((nx, ny))
                local_d[nx][ny] = local_d[p[0]][p[1]] + 1
    d_max = max(local_d)
    return d_max
 
 
dis = 0
for i in range(n):
  	for j in range(m):
	    dis_i = tansaku(i, j, d)
    	if dis_i > dis:
        	dis = copy.copy(dis_i) 
 
print(dis)

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [input() for _ in range(h)]

INF = 1001001001
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

def update(i, j, x):
    global dist, s, q
    if(dist[i][j] != INF): return
    dist[i][j] = x
    q.append([i, j])

res = 0
for si in range(h):
    for sj in range(w):
        if(s[si][sj] == '#'): continue
        
        dist = [[INF for _ in range(w)] for _ in range(h)]
        q = deque()
        update(si, sj, 0)
        
        while(q):
            i, j = q.popleft()
            
            for idir, jdir in zip(di, dj):
                ni = i + idir
                nj = j + jdir
                
                if(ni<0 or ni>=h or nj<0 or nj>=w): continue
                if(s[ni][nj] == '#'): continue
                
                update(ni, nj, dist[i][j]+1)
        
        for i in range(h):
            for j in range(w):
                if(dist[i][j]==INF): continue
                res = max(res, dist[i][j])
                if(res == 9): temp.append(dist)

print(res)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "#" else 0 for a in input()] + [1]
X += [1] * (W + 2)
H, W = H+2, W+2
 
def BFS(i0=0):
    Q = deque([i0])
    D = [-1] * (H * W)
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for y in (x+W, x-W, x+1, x-1):
            if X[y] == 0:
                if D[y] == -1:
                    D[y] = D[x] + 1
                    Q.append(y)
    return D
 
ma = 0
for i in range(H):
    for j in range(W):
        if X[i*W+j] == 0:
            ma = max(ma, max(BFS(i*W+j)))
print(ma)
from collections import deque
H, W = map(int, input().split())

Submission status: Runtime Error

Solution code:
from collections import deque

h,w = map(int, input().split())
PATH = "."
WALL = "#"
z=0
# 迷路の配列を作成する。
maze=list()
for a in range(h):
 mazew=list()
 mazeh = input()
 for b in range(w):
  mazew.append(mazeh[b])
 maze.append(mazew)
 print(maze)

for c in range(h):
 for d in range(w):
  for e in range(h):
   for f in range(w):
   # 地図上の未訪問地点を-1とする。
   # また、移動するごとに+1することで、スタート地点からの移動距離を保持する。
    if maze[e][f] == WALL:
     continue
    else:
     distance_visited = list()
     for l in range(h):
      distance_visited.append([-1] * w)
    # スタート地点を登録する。
     queue = deque([[c, d]])
     distance_visited[c][d] = 0
     goal_x, goal_y=e,f
     while True:
      x,y = queue.popleft()
      # ゴールの場合は終了する。
      if x == e and y==f:
       goal_x, goal_y = x, y
       break
        # 現在地点の上下左右のマスを確認する。
      for i,j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
       new_x, new_y = x + i, y + j
        # それぞれのマスが移動できる場合、かつまだ移動したことが無い場合
       if new_x>=0 and new_x<=h-1 and new_y>=0 and new_y<=w-1:
        if maze[new_x][new_y] != WALL and distance_visited[new_x][new_y] == -1:
                # そのマスのスタートからの移動距離を設定し、またキューに登録する。
         distance_visited[new_x][new_y] = distance_visited[x][y] + 1
         queue.append([new_x, new_y])
      if z<distance_visited[goal_x][goal_y]:
       z=distance_visited[goal_x][goal_y]
print(z)

Submission status: Runtime Error

Solution code:
from collections import deque
from itertools import chain

H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
inf = float('inf')


def flatten(list_of_lists):
    return chain.from_iterable(list_of_lists)


def bfs(start, end):
    distance = [[inf for i in range(W)] for j in range(H)]
    queue = deque((end, start))
    distance[end][start] = 0

    while queue:
        y, x = queue.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if 0 <= nx < W and 0 <= ny < H and M[ny][nx] != '#' and distance[ny][nx] == inf:
                queue.insert(0, (ny, nx))
                distance[ny][nx] = distance[y][x] + 1
    return distance


m = 0
for i in range(W):
    for j in range(H):
        if M[j][i] != "#":

            for length in list(flatten(bfs(i, j))):
                if length != inf and m < length:
                    m = length

print(m)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
def main():
    H, W = map(int, input().split())
    m = []
    for _ in range(H):
        l = input()
        m.append(l)
    edge = []
    v = H * W
    for i in range(H):
        for j in range(W):
            t = i * H + j
            edge.append([10 ** 9] * v)
            if m[i][j] == '.':
                if i > 0 and m[i-1][j] == '.':
                    edge[t][(i-1) * H + j] = 1
                if j > 0 and m[i][j -1] == '.':
                    edge[t][i * H + j - 1] = 1
                if i < H-1 and m[i+1][j] == '.':
                    edge[t][(i + 1)*H + j] = 1
                if j < W - 1 and m[i][j+1] == '.':
                    edge[t][i * H + j + 1] = 1
    G = csgraph_from_dense(edge, null_value=10**9)
    d = floyd_warshall(G)
    m = 0
    for i in range(v):
        for j in range(v):
            if d[i][j] != float('inf') and d[i][j] > m:
                m = d[i][j]
    print(int(m))
main()

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path, csgraph_from_dense
def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    m = [[0] * (W * H) for _ in range(W * H)]
    def loc(h, w):
        return h * W + w
    def con(h1, w1, h2, w2):
        m[loc(h1, w1)][loc(h2, w2)] = 1
        m[loc(h2, w2)][loc(h1, w1)] = 1

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            if h > 0:
                if S[h - 1][w] == '.':
                    con(h, w, h - 1, w)
            if h < H - 1:
                if S[h + 1][w] == '.':
                    con(h, w, h + 1, w)
            if w > 0:
                if S[h][w - 1] == '.':
                    con(h, w, h, w - 1)
            if w < W - 1 and S[h][w + 1] == '.':
                con(h, w, h, w + 1)
    EE = shortest_path(csgraph_from_dense(m, null_value=0))
    print(int(np.max(EE[~np.isinf(EE)])))


main()

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = []
for _ in range(h):
    maze.append(list(input()))

def clear_maze(sx, sy, maze):
    INF = -float('infinity')
    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]

    queue = deque([(sx, sy)])
    distance[sx][sy] = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    while queue:
        x, y = queue.pop()
        # if x == gx and y == gy:
        #     break
        for i in range(0, 4):
            nx, ny = x + dx[i], y + dy[i]
            if (0 <= nx < field_x_length) and (0 <= ny < field_y_length):
                if maze[nx][ny] != '#' and distance[nx][ny] == INF:
                    queue.appendleft((nx, ny))
                    distance[nx][ny] = distance[x][y] + 1
    MAX = 0
    for row in range(len(distance)):
        for col in range(len(distance)):
            MAX = max(MAX, distance[row][col])
    return MAX
    # return distance[gx][gy]

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

MAX = 0
for sx, sy in pairs:
    r = clear_maze(sx, sy, maze)
    MAX = max(MAX, r)
print(MAX)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
grid=[[c for c in input()] for _ in range(N)]
mat=[[0]*(M*N) for _ in range(N*M)]

DX=[0,0,1,-1]
DY=[-1,1,0,0]
for row in range(N):
  for col in range(M):
    if grid[row][col]=="#":
      continue
  	for dx,dy in DX,DY:
      if 0<=row+dx<N and 0<=col+dy<M:
        if grid[row+dx][col+dx]=="#":
          continue
        mat[(row+dx)*N+col+dx][dx*N+dy]=1
        mat[dx*N+dy][(row+dx)*N+col+dx]=1
for k in range(N*M):
        for i in range(N*M):
            for j in range(N*M):
                mat[i][j] = min(mat[i][j],mat[i][k] + mat[k][j])
print(max(mat))

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
 
# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(maze, sx, sy, n, m):
    # すべての点を INF で初期化
    d = [[float("inf")] * m for i in range(n)]
 
    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
 
    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
 
    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
 
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
 
    return max(d[nx][ny])
 
 
n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
 
#print(maze)
 
bfs_list = [0]
 
for i in range(n):
  for j in range(m):
    # スタートとゴールの座標を探す
      sx = i
      sy = j
      if maze[sx][sy] == "#":
      	continue
      bfs_list.append(bfs(maze, sx, sy, n, m))

print(max(bfs_list))

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
 
# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(maze, sx, sy, n, m):
    # すべての点を INF で初期化
    d = [[float("inf")] * m for i in range(n)]
 
    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
 
    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
 
    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
 
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
 
    return max(d[nx][ny])
 
 
n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
 
#print(maze)
 
bfs_list = [0]
 
for i in range(n):
  for j in range(m):
    # スタートとゴールの座標を探す
      sx = i
      sy = j
      bfs_list.append(bfs(maze, sx, sy, n, m))

print(max(bfs_list))