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 itertools import combinations
import copy
from collections import deque

# def rec(start,distance):
#     print(start)
#     distance +=1
#     # print(distance)
#     i,j = start[0],start[1]
#     if i < 0 or i >= H:
#         return
#     if j < 0 or j >= W:
#         return
#     if S1[i][j] == 1:
#         return
#     S1[i][j] = 1
#     # stopi,stopj = stop[0],stop[1]
#     if start == stop:
#         result = distance
#         print(distance)
#         return distance
#     rec((i-1,j),distance)
#     rec((i+1,j),distance)
#     rec((i,j-1),distance)
#     rec((i,j+1),distance)

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

S = np.zeros((H,W))
for i in range(H):
    scan =  input()
    # print(scan)
    for j,s in enumerate(scan):
        if s == ".":
            S[i][j] = 0
        else:
            S[i][j] = 1
# print(S)
positions = []
for i in range(H):
    for j in range(W):
        positions.append((i,j))
# print(positions)
c = combinations(positions,2)
result = 0
for pat in c:
    start = pat[0]
    stop = pat[1]
    distance = 0
    S1 = copy.deepcopy(S)
    q = deque()
    d = np.full((H,W),np.inf)
    q.append(start)
    d[start[0]][start[1]] = 0
    while len(q) > 0:
        p = q.popleft()
        # print(p)
        i,j = p[0],p[1]
        four = [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]
        if p == stop:
            break
        for f in four:
            i1,j1 = f[0],f[1]
            if 0 <= i1 < H and 0<= j1 < W and S1[i1][j1] == 0 and d[i1][j1] == np.inf:
                q.append((i1,j1))
                d[i1][j1] = d[i][j] +1
    distance = d[stop[0]][stop[1]]
    # print(distance)
    if distance != np.inf and distance > result:
        result = int(distance)

print(result)

Submission status: Runtime Error

Solution code:
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    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())

fld = [""] * H
for i in range(H):
    fld[i] = input()

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

d = [[float("inf") for i in range(H * W+1)] for i in range(H * W+1)]
for i in range(H):
    for j in range(W):
        if fld[i][j] == '#':
            continue
        for k in range(4):
            x = i + dx[k]
            y = j + dy[k]
            if x < 0 or x >= H or y < 0 or y >= W:
                continue
            if fld[x][y] == ".":
                d[i*H+j][x*H+y] = 1


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

warshall = warshall_floyd(d, H*W)
ans = 0
for val in warshall:
    for v in val:
        if v != float("inf"):
            ans = max(ans, v)

print(ans)

Submission status: Runtime Error

Solution code:
import queue
r,c=map(int,input().split())
#sy,sx=map(int,input().split())
#gy,gx=map(int,input().split())
a=[list(input()) for i in range(r)]
sy,sx = (1,1)
#gy,gx = (2,2)
def minload(sy,sx,a):
    sy-=1
    sx-=1
    #gy-=1
    #gx-=1
    q = queue.Queue()
    d=[(-1,0),(1,0),(0,-1),(0,1)]
    a[sy][sx]=0
    for i in d:
        if 0<=sy+i[0]<r and 0<=sx+i[1]<c and a[sy+i[0]][sx+i[1]]==".":
            a[sy+i[0]][sx+i[1]]=1
            q.put((sy+i[0],sx+i[1]))
    while True:
        if queue.Queue.empty(q):
            break
        y,x=q.get()
        #if y==r and x==c:
            #break
        for i in d:
            if 0<=y+i[0]<r and 0<=x+i[1]<c and a[y+i[0]][x+i[1]]==".":
                a[y+i[0]][x+i[1]]=a[y][x]+1
                q.put((y+i[0],x+i[1]))
    #print(a[gy][gx])
    max = 0
    for i in a:
        for j in i:
            if j != '#' and j !='.':
                if j > max:
                    max = j
    return(max)
ans = 0
for sy in range(1,r+1): 
    for sx in range(1,c+1):
        b = []
        for i in a:
            b.append(list(i))
        if a[sy-1][sx-1]==".":
            local_max = minload(sy,sx,b)
            #print(local_max)
            #print(b)
        if local_max > ans:
            ans = local_max
print(ans)

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
field = [list(input())for i in range(h)]
a= [[0]*w for i in range(h)]

vec = [(-1,0),(1,0),(0,1),(0,-1)]
ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":continue
        stack = [(i,j)]
        visited = [[0]*w for i in range(w)]
        a[i][j] = 0
        
        while stack:
            next = []
            for x,y in stack:
                
                if visited[x][y]:continue

                visited[x][y] = 1
                

                for tx,ty in vec:
                    nx = x+tx
                    ny = y+ty
                    if nx < 0 or ny <0 or nx >=h or ny >=w:continue
                    if field[nx][ny] == "#" :continue
                    if visited[nx][ny]:continue
                    next.append((nx,ny))
                    a[nx][ny] = a[x][y] + 1
                    
                    
            stack = next
   
        for i in range(h):
            ans = max(ans,max(a[i]))
            a[i] = [0]*w
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

from collections import deque, defaultdict

def dfs(s, t, n, g):
    Q = deque([s])
    searched = [0 for i in range(n)]
    searched[s] = 1
    depth = [0 for i in range(n)]
    while len(Q) != 0:
        v = Q.popleft()
        for i in g[v]:
            if i == t:
                depth[i] = depth[v] + 1
                # print(depth[i], s, t)
                return depth[i]
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    # print(searched[:16])



def main():
    h, w = LI()
    g = defaultdict(list)
    old_s = ["#" for _ in range(w)]
    dames = set()
    for i in range(h):
        s = S()
        # print(s)
        for j in range(w):
            if s[j] == "#":
                dames.add(i * w + j)
                continue
            if old_s[j] != "#":
                g[i * w + j].append(i * w + j - w)
                g[i * w + j - w].append(i * w + j)
            if j != w - 1 and s[j+1] != "#":
                g[i * w + j].append(i * w + j + 1)
                g[i * w + j + 1].append(i * w + j)
        old_s = s
    if h > 2:
        cands = [i for i in range(w)] + [w*i for i in range(1, h - 1)] + [w*(i+i)-1 for i in range(1, h - 1)] + [i+w*(h-1) for i in range(w)]
    else:
        cands = [0]
    min_ = 0
    # print(g)
    cands = [i for i in cands if i not in dames]
    for i in cands:
        for j in cands:
            if i > j:
                d = dfs(i, j, 500, g)
                min_ = max(min_, d)

    print(min_)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def dfs(y, x, y0, x0, d=0):
    if y < 0 or y >= H or x < 0 or x >= W:
        return

    if seen[y][x]:
        return

    seen[y][x] = True

    if maze[y][x] == "#":
        return

    if d > dist[y0][x0]:
        dist[y0][x0] = d

    dfs(y, x+1, y0, x0, d+1)
    dfs(y+1, x, y0, x0, d+1)
    dfs(y, x-1, y0, x0, d+1)
    dfs(y-1, x, y0, x0, d+1)


dist = [[0] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        seen = [[False] * W for _ in range(H)]
        dfs(i, j, i, j)

ans = 0
for row in dist:
    for d in row:
        ans = max(ans, d)

print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

from collections import deque, defaultdict

def dfs(s, t, n, g):
    Q = deque([s])
    searched = [0 for i in range(n)]
    searched[s] = 1
    depth = [0 for i in range(n)]
    while len(Q) != 0:
        v = Q.popleft()
        for i in g[v]:
            if i == t:
                depth[i] = depth[v] + 1
                # print(depth[i], s, t)
                return depth[i]
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    # print(searched[:16])



def main():
    h, w = LI()
    g = defaultdict(list)
    old_s = ["#" for _ in range(w)]
    dames = set()
    for i in range(h):
        s = S()
        # print(s)
        for j in range(w):
            if s[j] == "#":
                dames.add(i * w + j)
                continue
            if old_s[j] != "#":
                g[i * w + j].append(i * w + j - w)
                g[i * w + j - w].append(i * w + j)
            if j != w - 1 and s[j+1] != "#":
                g[i * w + j].append(i * w + j + 1)
                g[i * w + j + 1].append(i * w + j)
        old_s = s
    if h > 2:
        cands = [i for i in range(w)] + [w*i for i in range(1, h - 1)] + [w*(i+i)-1 for i in range(1, h - 1)] + [i+w*(h-1) for i in range(w)]
    else:
        cands = [0]
    min_ = 0
    print(g)
    cands = [i for i in cands if i not in dames]
    for i in cands:
        for j in cands:
            if i > j:
                d = dfs(i, j, 500, g)
                min_ = max(min_, d)

    print(min_)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from scipy.misc import comb


def main():
    n, k = list(map(int, input().split()))
    a = sorted(list(map(int, input().split())))

    if k!= 0 and n/k>0.5:
        k = n - k

    conv_list = [comb(n-i-1, k-i, exact=True) for i in range(k+1)]

    max_sum = 0
    min_sum = 0
    print(a)
    print(conv_list)
    for i in range(k+1):
        max_sum += a[n-i-1] * conv_list[i]
        min_sum += a[i] * conv_list[i]
    ret = (max_sum - min_sum) %1000000007
    print(ret)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import inf
from itertools import chain

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


def flatten(list_of_lists):
    "Flatten one level of nesting"
    return chain.from_iterable(list_of_lists)


def bfs(start, end):
    distance = [[inf for i in range(W)] for j in range(H)]
    queue = [(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:
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    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())

fld = [""] * H
for i in range(H):
    fld[i] = input()

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

d = [[float("inf") for i in range(H * W)] for i in range(H * W)]
for i in range(H):
    for j in range(W):
        if fld[i][j] == '#':
            continue
        for k in range(4):
            x = i + dx[k]
            y = j + dy[k]
            if x < 0 or x >= H or y < 0 or y >= W:
                continue
            if fld[x][y] == ".":
                d[i*H+j][x*H+y] = 1


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

warshall = warshall_floyd(d, H*W)
ans = 0
for val in warshall:
    for v in val:
        if v != float("inf"):
            ans = max(ans, v)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque
import sys
input = sys.stdin.readline

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

ans = 0

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


def bfs(x, y):
    m = np.full((H, W), dtype=np.int)

    q = deque()
    q.append([y, x, 0])
    maximus = 0

    while q:
        j, i, v = q.popleft()
        m[j][i] = v
        for dd in d:
            dj = j + dd[0]
            di = i + dd[1]
            if 0 <= dj < H and 0 <= di < W and m[dj][di] == -1 and S[dj][di] == ".":
                q.append([dj, di, v+1])
                if maximus < v+1:
                    maximus = v+1

    return maximus


for j in range(H):
    for i in range(W):
        if S[j][i] != ".":
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
r, c = map(int, input().split())
 
orig_maze = [[val for val in list(input())] for _ in range(r)]

maze = [[None for _ in range(c+2)] for _ in range(r+2)]
for r_index in range(r+2):
  for c_index in range(c+2):
    if r_index == 0 or r_index == r+1 or c_index == 0 or c_index == c+1:
      maze[r_index][c_index] = "#"
    else:
      maze[r_index][c_index] = orig_maze[r_index-1][c_index-1]
      
def wfs(queue, goal):
    finish_dist = None
    while len(queue) > 0:
        a = queue.popleft()
        y = a[0]
        x = a[1]
        count = a[2]
        if checked_maze[y][x]:
            continue
 
        if a[0] == goal[0] and a[1] == goal[1]:
            finish_dist = count
            break
 
        checked_maze[y][x] = True
        if not maze[y][x] == "#":
            count += 1
            queue.append((a[0]+1, a[1], count))
            queue.append((a[0]-1, a[1], count))
            queue.append((a[0], a[1]+1, count))
            queue.append((a[0], a[1]-1, count))

    return finish_dist 
 
 
if __name__ == "__main__":
    result = 0
    for s_y in range(1, r+1):
      for s_x in range(1, c+1):
        for g_y in range(1, r+1):
          for g_x in range(1, r+1):
            if maze[s_y][s_x] == "." and maze[g_y][g_x] == ".":
              if s_y == g_y and s_x == g_x:
                finish_dist = 0
              else:
                checked_maze = [[None for _ in range(c+2)] for _ in range(r+2)]
                que = deque()
                checked_maze[s_y][s_x]= 0
                que.append((s_y, s_x, 0))
                finish_dist = wfs(que, (g_y, g_x))
            result = max(result,finish_dist)
    print(result)

Submission status: Runtime Error

Solution code:
import queue
r,c=map(int,input().split())
#sy,sx=map(int,input().split())
#gy,gx=map(int,input().split())
a=[list(input()) for i in range(r)]
sy,sx = (1,1)
#gy,gx = (2,2)
def minload(sy,sx,a):
    sy-=1
    sx-=1
    #gy-=1
    #gx-=1
    q = queue.Queue()
    d=[(-1,0),(1,0),(0,-1),(0,1)]
    a[sy][sx]=0
    for i in d:
        if 0<=sy+i[0]<r and 0<=sx+i[1]<c and a[sy+i[0]][sx+i[1]]==".":
            a[sy+i[0]][sx+i[1]]=1
            q.put((sy+i[0],sx+i[1]))
    while True:
        if queue.Queue.empty(q):
            break
        y,x=q.get()
        #if y==r and x==c:
            #break
        for i in d:
            if 0<=y+i[0]<r and 0<=x+i[1]<c and a[y+i[0]][x+i[1]]==".":
                a[y+i[0]][x+i[1]]=a[y][x]+1
                q.put((y+i[0],x+i[1]))
    #print(a[gy][gx])
    max = 0
    for i in a:
        for j in i:
            if j != '#' and j !='.':
                if j > max:
                    max = j
    return(max)
max = 0
for sy in range(1,r+1): 
    for sx in range(1,c+1):
        b = []
        for i in a:
            b.append(list(i))
        if a[sy-1][sx-1]==".":
            local_max = minload(sy,sx,b)
            #print(local_max)
            #print(b)
        if local_max > max:
            max = local_max
print(max)

Submission status: Runtime Error

Solution code:
import sys
from pprint import pprint

def warshall_floyd(d, n):
    # pprint(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

def solve(h, w, s):
    
    edges = {}
    n_node = 0

    nodes = [] 
    # pprint(nodes)
    for y in range(h):
        nodes.append([])
        for x in range(w):
            nodes[y].append(n_node)
            n_node += 1
    edges = [[float("inf") for i in range(n_node)] for j in range(n_node)]
    # pprint(nodes)
    for y in range(h):
        for x in range(w):
            for dx, dy in ((1,0), (-1,0), (0,1), (0,-1)):
                if s[y][x] != ".":
                    continue
                if 0 <= y+dy < h and 0 <= x+dx < w and s[y+dy][x+dx] == ".":
                    edges[nodes[y][x]][nodes[y+dy][x+dx]] = 1
    for i in range(n_node):
        edges[i][i] = 0
    
    dist = warshall_floyd(edges, n_node)
    # pprint(dist)
    ans = -1
    for y in range(n_node):
        for x in range(n_node):
            if dist[y][x] < float("inf"):
                ans = max(ans, dist[y][x])
    print(ans)


if __name__ == '__main__':
    h, w = map(int, sys.stdin.readline().strip().split(" "))
    s = []
    for i in range(w):
        s.append(list(sys.stdin.readline().strip()))
    # debug
    # pprint(s)
    solve(h, w, s)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

from collections import deque, defaultdict

def dfs(s, t, n, g):
    Q = deque([s])
    searched = [0 for i in range(n)]
    searched[s] = 1
    depth = [0 for i in range(n)]
    while len(Q) != 0:
        v = Q.popleft()
        for i in g[v]:
            if i == t:
                depth[i] = depth[v] + 1
                # print(depth[i], s, t)
                return depth[i]
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    # print(searched[:16])



def main():
    h, w = LI()
    g = defaultdict(list)
    old_s = ["#" for _ in range(w)]
    dames = set()
    for i in range(h):
        s = S()
        # print(s)
        for j in range(w):
            if s[j] == "#":
                dames.add(i * w + j)
                continue
            if old_s[j] != "#":
                g[i * w + j].append(i * w + j - w)
                g[i * w + j - w].append(i * w + j)
            if j != w - 1 and s[j+1] != "#":
                g[i * w + j].append(i * w + j + 1)
                g[i * w + j + 1].append(i * w + j)
        old_s = s
    if w > 2:
        cands = [i for i in range(w)] + [w*i for i in range(1, h - 1)] + [w*(i+i)-1 for i in range(1, h - 1)] + [i+w*(h-1) for i in range(w)]
    else:
        cands = [0]
    min_ = 0
    # print(g)
    cands = [i for i in cands if i not in dames]
    for i in cands:
        for j in cands:
            if i > j:
                d = dfs(i, j, 500, g)
                min_ = max(min_, d)

    print(min_)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd, deque

h,w = map(int,input().split())
M = [input().strip()+'#' for _ in range(h)]
M.append(w*'#')

start = None
for i in range(h):
    for j in range(w):
        if M[i][j] == '.':
            start = (j,i)

Q = deque()
Q.append((0, *start))
seen = set()

while Q:
    d,x,y = Q.popleft()

    if (x,y) in seen: continue
    seen.add((x,y))

    for nx,ny in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:
        if M[ny][nx] == '.':
            Q.append((d+1, nx, ny))


Q = deque()
Q.append((0, x, y))
seen = set()

while Q:
    d,x,y = Q.popleft()

    if (x,y) in seen: continue
    seen.add((x,y))

    for nx,ny in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:
        if M[ny][nx] == '.':
            Q.append((d+1, nx, ny))

print(d)

Submission status: Runtime Error

Solution code:
from collections import deque
import copy
import sys
import numpy as np
sys.setrecursionlimit(410000)

INF = 10**6

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

def solve(sy,sx):
  d = [[INF]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if maze[i][j] == '#':
        d[i][j] = -INF          
  
  que = deque()
  que.append([sx,sy])
  d[sy][sx]=0

  while len(que)>0:
    px,py = que.popleft()

    for dx,dy in ((-1,0),(0,1),(1,0),(0,-1)):
      nx = px + dx
      ny = py + dy

      if (0 <= nx and nx < w and 0<=ny and ny < h) \
          and maze[ny][nx] != '#' \
          and (d[ny][nx] == INF or d[ny][nx] > d[py][px] +1):              
        que.append((nx,ny))
        d[ny][nx] = d[py][px] +1

  return d

ans = 0
for sy in range(h):
  for sx in range(w):
    maze = copy.deepcopy(org_maze)
    if maze[sy][sx] == '.':
      f = solve(sy,sx)
      ans = max(ans, np.max(np.array(f)))
    
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd, deque

h,w = map(int,input().split())
M = [input()+'#' for _ in range(h)]
M.append(w*'#')

start = None
for i in range(h):
    for j in range(w):
        if M[i][j] == '.':
            start = (j,i)

Q = deque()
Q.append((0, *start))
seen = set()

while Q:
    d,x,y = Q.popleft()

    if (x,y) in seen: continue
    seen.add((x,y))

    for nx,ny in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:
        if M[ny][nx] == '.':
            Q.append((d+1, nx, ny))


Q = deque()
Q.append((0, x, y))
seen = set()

while Q:
    d,x,y = Q.popleft()

    if (x,y) in seen: continue
    seen.add((x,y))

    for nx,ny in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:
        if M[ny][nx] == '.':
            Q.append((d+1, nx, ny))

print(d)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

from collections import deque, defaultdict

def dfs(s, t, n, g):
    Q = deque([s])
    searched = [0 for i in range(n)]
    searched[s] = 1
    depth = [0 for i in range(n)]
    while len(Q) != 0:
        v = Q.popleft()
        for i in g[v]:
            if i == t:
                depth[i] = depth[v] + 1
                # print(depth[i], s, t)
                return depth[i]
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    # print(searched[:16])



def main():
    h, w = LI()
    g = defaultdict(list)
    old_s = ["#" for _ in range(w)]
    dames = set()
    for i in range(h):
        s = S()
        # print(s)
        for j in range(w):
            if s[j] == "#":
                dames.add(i * w + j)
            if old_s[j] != "#":
                g[i * w + j].append(i * w + j - w)
                g[i * w + j - w].append(i * w + j)
            if j != w - 1 and s[j+1] != "#":
                g[i * w + j].append(i * w + j + 1)
                g[i * w + j + 1].append(i * w + j)
        old_s = s
    if w > 2:
        cands = [i for i in range(w)] + [w*i for i in range(1, h - 1)] + [w*(i+i)-1 for i in range(1, h - 1)] + [i+w*(h-1) for i in range(w)]
    else:
        cands = [0]
    min_ = 0
    # print(g)
    cands = [i for i in cands if i not in dames]
    for i in cands:
        for j in cands:
            if i > j:
                d = dfs(i, j, 400, g)
                min_ = max(min_, d)

    print(min_)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from pprint import pprint

def warshall_floyd(d, n):
    # pprint(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

def solve(h, w, s):
    
    edges = {}
    n_node = 0

    nodes = [] 
    # pprint(nodes)
    for y in range(h):
        nodes.append([])
        for x in range(w):
            nodes[y].append(n_node)
            n_node += 1
    edges = [[float("inf") for i in range(n_node)] for j in range(n_node)]
    # pprint(nodes)
    for y in range(h):
        for x in range(w):
            for dx, dy in ((1,0), (-1,0), (0,1), (0,-1)):
                if s[y][x] != ".":
                    continue
                if 0 <= y+dy < h and 0 <= x+dx < w and s[y+dy][x+dx] == ".":
                    edges[nodes[y][x]][nodes[y+dy][x+dx]] = 1
    
    dist = warshall_floyd(edges, n_node)
    # pprint(dist)
    ans = -1
    for y in range(n_node):
        for x in range(n_node):
            if dist[y][x] < float("inf"):
                ans = max(ans, dist[y][x])
    print(ans)


if __name__ == '__main__':
    h, w = map(int, sys.stdin.readline().strip().split(" "))
    s = []
    for i in range(w):
        s.append(list(sys.stdin.readline().strip()))
    # debug
    # pprint(s)
    solve(h, w, s)

Submission status: Runtime Error

Solution code:
import queue
import copy
import numpy as np

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

maze = []
maze.append(["#" for i in range(W+2)])
for i in range(H):
    maze.append(list(input()))
    maze[i+1].insert(0,"#")
    maze[i+1].append("#")
maze.append(["#" for i in range(W+2)])

distance_template = [[-1 for i in range(W+2)] for i in range(H+2)]

ans = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if maze[i][j] != "#":
            startx,starty = i,j
            distance = np.array(distance_template)
            distance[startx][starty] = 0
            Q = queue.Queue()
            Q.put((startx, starty))
            while not Q.empty():
                x,y = Q.get()
                for i in range(0, 4):
                    nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                    if (maze[nx][ny] != "#" and distance[nx][ny] == -1):
                        Q.put((nx, ny))
                        distance[nx][ny] = distance[x][y] + 1
            maxdistance = np.unravel_index(np.argmax(distance), distance.shape)
            if ans < distance[maxdistance[0]][maxdistance[1]]:
                ans = distance[maxdistance[0]][maxdistance[1]]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
sys.setrecursionlimit(10 ** 7)
def bfs():
    cnt = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while len(Q) > 0:
        q = Q.popleft()
        y,x =  q[0], q[1]
        if cnt >= H*W:
            for i in range(H):
                if len(box[i]) == 0:
                    continue
                else:
                    ans.append(max(box[i]))
            return
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == "#" and box[ny][nx] == 0:
                cnt += 1
                box[ny][nx] = -1
            if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == "." and box[ny][nx] == 0:
                cnt += 1
                box[ny][nx] = box[y][x] + 1
                Q.append([ny,nx])


H,W = map(int,input().split())
S = [ []for _ in range(H)]
for i in range(H):
    S[i] = list(input())
ans = []
INF = 50**2
Q = deque()
#queueにスタート地点を追加
for i in range(H):
    for j in range(W):
        #各マス目に到達するために必要な移動回数
        box = [[0 for _ in range(W)] for __ in range(H)]
        box[i][j] = 0
        Q.append([i,j])
        bfs()
if len(ans)==0:
    print(0)
    exit()
print(max(ans))

Submission status: Runtime Error

Solution code:
def main():
    import networkx as nx
    import numpy as np
    h,w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    dic = {'.':0, '#':1}
    g = [[dic[i] for i in _s] for _s in s]
    graph = nx.grid_graph(dim=[h, w])
    rm_node = np.array(g)

    for (u, _) in graph.nodes(data=True):
        if rm_node[u]:
            graph.remove_node(u)
    try:
        ans1 = nx.dijkstra_path(graph, (0, 0), (h-1, w-1))
    except nx.NetworkXNoPath:
        ans1 = []
    try:
        ans2 = nx.dijkstra_path(graph, (h-1, 0), (0, w-1))
    except nx.NetworkXNoPath:
        ans2 = []
    print(max(max(len(ans1),len(ans2))-1,0))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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'#',dtype='S1')
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, [3,1], cost=0)[1:-1,1:-1]
    res[res==400]=0
    tm=np.max(res)
    if m < tm:
      m=tm
print(m)