Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappop, heappush
INF = 1e7

H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())

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

D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, sx, sy)]
heapify(PQ)
while PQ: # PQに候補がある限り
    _, ux, uy = heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heappush(PQ, (D[xx][yy], xx, yy))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


def dfs(h, w):
    seen[h][w] = True

    for dir in range(4):
        nh = h + dx[dir]
        nw = w + dy[dir]

        if nh < 0 or nh >= H or nw < 0 or nw >= W: continue
        if field[nh][nw] == "#": continue

        if seen[nh][nw]: continue

        dfs(nh, nw)


def dfs2(h, w):
    seen2[h][w] = True

    for nh in range(h+3):
        for nw in range(w+3):

            if nh < 0 or nh >= H or nw < 0 or nw >= W: continue
            if field[nh][nw] == "#": continue
            if seen2[nh][nw]: continue

            dfs2(nh, nw)


H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
field = [list(input()) for _ in range(H)]
seen = [[False] * (W) for _ in range(H)]
seen2 = [[False] * (W) for _ in range(H)]

cnt = 0
for h in range(H):
    for w in range(W):
        if seen[h][w]: continue
        if field[h][w] == "#": continue
        dfs(h, w)
        cnt += 1
dfs2(ch, cw)
if seen2[dh][dw]:
    print(cnt-1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
## dijkstraで解く

from collections import deque
import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

INF = 1 << 10
N = 10**4
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0

heapq.heappush(q,(0, (ch-1)*N+(cw-1)))
while q:
    cnt, n  = heapq.heappop(q)
    h,w = divmod(n, N)
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    # 歩いた
    for dh in range(-2,3):
        for dw in range(-2,3):            
            hn = h + dh
            wn = w + dw

            if not 0 <= wn < W: continue
            if not 0 <= hn < H: continue
            if fs[hn][wn] == "#": continue
            if dps[hn][wn] != INF:continue
            if abs(dh) + abs(dw) <= 1:
                heapq.heappush(q, (cnt, hn*N+wn))
            else:
                heapq.heappush(q, (cnt+1, hn*N+wn))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, inp().split())
    gy, gx = map(lambda x: int(x) - 1, inp().split())
    G = [inpS() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny, nx = dy + sy, dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.append((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8, nx8 = dy8 + sy, dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.append((ny8, nx8, cost + 1))

    res = ans[gy][gx] if ans[gy][gx] < INF else -1
    print(res)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:

from collections import deque
def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

    ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
    print(ans)


if __name__ == "__main__":
    reoslve()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))
ch-=1; cw-=1; dh-=1; dw-=1

def valid(i, j):
    if 0<=i<=h-1 and 0<=j<=w-1:
        return True
    else:
        return False

def bfs(i, j, ans):
    f=False
    if m[i][j]==".":
        m[i][j] = str(ans)
        f=True
    else:
        if int(m[i][j])>ans:
            m[i][j] = str(ans)
            f=True
            
    if (i,j)==(dh,dw):
        return 0
    
    if f:
        for si in range(-2, 3):
            for sj in range(-2, 3):
                if valid(i+si, j+sj) and m[i+si][j+sj]!='#':
                    if (si, sj) == (0, 0):
                        pass
                    elif (si, sj) == (-1, 0) or (si, sj) == (0, -1) or (si, sj) == (1, 0) or (si, sj) == (0, 1):
                        bfs(i+si, j+sj, ans)
                    else:
                        bfs(i+si, j+sj, ans+1)
    
bfs(ch, cw, 0)

if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])

Submission status: Runtime Error

Solution code:
H, W, M = map(int, input().split())
boms = set()
Hs = [0] * H
Ws = [0] * W
for i in range(M):
  h, w = map(lambda x: int(x) - 1, input().split())
  boms.add((h, w))
  Hs[h] += 1
  Ws[w] += 1
  
Hmax = max(Hs)
HMaxIndexs = set()
for i, h in enumerate(Hs):
  if h == Hmax:
    HMaxIndexs.add(i)

Wmax = max(Ws)
WMaxIndexs = set()
for i, w in enumerate(Ws):
  if w == Wmax:
    WMaxIndexs.add(i)

count = 0
for bom in boms:
  if (bom[0] in HMaxIndexs) and (bom[1] in WMaxIndexs):
    count += 1
print(Hmax + Wmax - 1) if count == len(HMaxIndexs) * len(WMaxIndexs) else print(Hmax + Wmax)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: x.decode(), readlines()))
ch-=1; cw-=1; dh-=1; dw-=1

def valid(i, j):
    if 0<=i<=h-1 and 0<=j<=w-1:
        return True
    else:
        return False

def bfs(i, j, ans):
    f=False
    if m[i][j]==".":
        m[i]=m[i][:j]+str(ans)+m[i][j+1:]
        f=True
    else:
        if int(m[i][j])>ans:
            m[i]=m[i][:j]+str(ans)+m[i][j+1:]
            f=True
            
    if (i,j)==(dh,dw):
        return 0
    
    if f:
        for si in range(-2, 3):
            for sj in range(-2, 3):
                if valid(i+si, j+sj) and m[i+si][j+sj]!='#':
                    if (si, sj) == (0, 0):
                        pass
                    elif (si, sj) == (-1, 0) or (si, sj) == (0, -1) or (si, sj) == (1, 0) or (si, sj) == (0, 1):
                        bfs(i+si, j+sj, ans)
                    else:
                        bfs(i+si, j+sj, ans+1)
    
bfs(ch, cw, 0)

if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])

Submission status: Runtime Error

Solution code:
import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * (h*w) # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

h,w = map(int,input().split())
c = list(map(int,input().split()))
d = list(map(int,input().split()))
maze = [list(input()) for i in range(h)]
# eのインデックスはi*w+j
e = [[] for _ in range(h*w)]
for i in range(h):
    for j in range(w):
        if j<w-1 and maze[i][j] == "." and maze[i][j+1] == ".":
            e[i*w+j].append((0, i*w+j+1))
            e[i*w+j+1].append((0, i*w+j)) # 有向グラフでは削除
        if i<h-1 and maze[i][j] == "." and maze[i+1][j] == ".":
            e[i*w+j].append((0, (i+1)*w+j))
            e[(i+1)*w+j].append((0, i*w+j)) # 有向グラフでは削除
        for x in range(3):
            for y in range(3):
                if i+x<h and j+y<w and maze[i+x][j+y] == ".":
                    e[i*w+j].append((1, (i+x)*w+j+y))
                    e[(i+x)*w+j+y)].append((1, i*w+j)

# print(dijkstra(1))
ans = dijkstra((c[0]-1)*w+(c[1]-1))[(d[0]-1)*w+(d[1]-1)]
if ans == float("inf"):
    print(-1)
    exit()
print(ans)

Submission status: Runtime Error

Solution code:
import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * (h*w) # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

h,w = map(int,input().split())
c = list(map(int,input().split()))
d = list(map(int,input().split()))
maze = [list(input()) for i in range(h)]
# eのインデックスはi*w+j
e = [[] for _ in range(h*w)]
for i in range(h):
    for j in range(w):
        if j<w-1 and maze[i][j] == "." and maze[i][j+1] == ".":
            e[i*w+j].append((0, i*w+j+1))
            e[i*w+j+1].append((0, i*w+j)) # 有向グラフでは削除
        if i<h-1 and maze[i][j] == "." and maze[i+1][j] == ".":
            e[i*w+j].append((0, (i+1)*w+j))
            e[(i+1)*w+j].append((0, i*w+j)) # 有向グラフでは削除
        for x in range(-2,3):
            for y in range(-2,3):
                if i+x<h and j+y<w and maze[i+x][j+y] == ".":
                    e[i*w+j].append((1, (i+x)*w+j+y))

# print(dijkstra(1))
ans = dijkstra((c[0]-1)*w+(c[1]-1))[(d[0]-1)*w+(d[1]-1)]
if ans == float("inf"):
    print(-1)
    exit()
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Ch, Cw = Ch-1, Cw-1
    addr_c = Ch*W+Cw
    Dh, Dw = map(int, input().split())
    Dh, Dw = Dh-1, Dw-1
    addr_d = Dh*W+Dw
    #print(addr_c, addr_d)
    g = np.full((H*W, H*W), np.inf)
    S = []  #S[h][w]でアクセス すなわちx,y
    for _ in range(H):
        S.append([True if x=='.' else False for x in input()])
    for x, y in itertools.product(range(H), range(W)):
        addr = x*W + y
        if not S[x][y]:
            continue
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[xx][yy]:
                #print(f"{x},{y} -> {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 0
                g[addr2, addr] = 0
        for xx, yy in [(x-2,y+2),(x-1,y+2),(x,y+2),(x+1,y+2),(x+2,y+2),(x-2,y+1),(x-1,y+1),(x+1,y+1),(x+2,y+1),(x-2,y),(x+2,y),
            (x-2,y-1),(x-1,y-1),(x+1,y-1),(x+2,y-1),(x-2,y-2),(x-1,y-2),(x,y-2),(x+1,y-2),(x+2,y-2),]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[xx][yy]:
                #print(f"{x},{y} => {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 1
                g[addr2, addr] = 1
    #print(g)
    #G2_masked = np.ma.masked_invalid(g)
    #print(G2_masked)
    #print(type(G2_masked))
    G2_sparse = csgraph_from_dense(g, null_value=np.inf)
    #print(G2_sparse)
    #print(type(G2_sparse))
    path = shortest_path(G2_sparse, indices=addr_c)
    if path[addr_d] != np.inf:
        print(int(path[addr_d]))
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
#import sys
#sys.setrecursionlimit(6000)

def bfs01(start_h, start_w, S, H, W):
    path = deque()
    path.append((start_h, start_w, 0))  #x, y, cost
    cost0 = set()
    cost1 = set()
    scores = [[10**18]*(W+1)]*(H+1)
    scores[start_h][start_w] = 0
    #BFS
    while path:
        x, y, cost = path.pop()
        if (x,y) in cost0:
            continue
        elif (x,y) in cost1 and cost==1:
            continue
        #print((x, y, cost))
        if cost==0:
            cost0.add((x,y))
        elif cost==1:
            cost1.add((x,y))
        else:
            assert False
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>H or yy>W:
                continue
            if scores[xx][yy] <= scores[x][y]:
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[xx][yy]:
                path.append((xx, yy,0))
                scores[xx][yy] = scores[x][y]
        for xx, yy in [(x-2,y+2),(x-1,y+2),(x,y+2),(x+1,y+2),(x+2,y+2),(x-2,y+1),(x-1,y+1),(x+1,y+1),(x+2,y+1),(x-2,y),(x+2,y),
            (x-2,y-1),(x-1,y-1),(x+1,y-1),(x+2,y-1),(x-2,y-2),(x-1,y-2),(x,y-2),(x+1,y-2),(x+2,y-2),]:
            if xx<0 or yy<0 or xx>H or yy>W:
                continue
            if scores[xx][yy] <= scores[x][y] + 1:
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[xx][yy]:
                path.appendleft((xx, yy,1))
                scores[xx][yy] = scores[x][y] + 1
    return scores

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [[False]*(W+1)]  #S[h][w]でアクセス
    for _ in range(H):
        S.append([False] + [True if x=='.' else False for x in input()])
    scores = bfs01(Ch, Cw, S, H, W)
    if scores[Dw][Dh] == 10**18:
        print(-1)
    else:
        print(scores[Dw][Dh])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
#import sys
#sys.setrecursionlimit(6000)

def bfs01(start_h, start_w, S, H, W):
    path = deque()
    path.append((start_h, start_w, 0))  #x, y, cost
    cost0 = set()
    cost1 = set()
    scores = [[10**18]*(H+1)]*(W+1)
    scores[start_h][start_w] = 0
    #BFS
    while path:
        x, y, cost = path.pop()
        if (x,y) in cost0:
            continue
        elif (x,y) in cost1 and cost==1:
            continue
        #print((x, y, cost))
        if cost==0:
            cost0.add((x,y))
        elif cost==1:
            cost1.add((x,y))
        else:
            assert False
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>H or yy>W:
                continue
            if scores[xx][yy] <= scores[x][y]:
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[xx][yy]:
                path.append((xx, yy,0))
                scores[xx][yy] = scores[x][y]
        for xx, yy in [(x-2,y+2),(x-1,y+2),(x,y+2),(x+1,y+2),(x+2,y+2),(x-2,y+1),(x-1,y+1),(x+1,y+1),(x+2,y+1),(x-2,y),(x+2,y),
            (x-2,y-1),(x-1,y-1),(x+1,y-1),(x+2,y-1),(x-2,y-2),(x-1,y-2),(x,y-2),(x+1,y-2),(x+2,y-2),]:
            if xx<0 or yy<0 or xx>H or yy>W:
                continue
            if scores[xx][yy] <= scores[x][y] + 1:
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[xx][yy]:
                path.appendleft((xx, yy,1))
                scores[xx][yy] = scores[x][y] + 1
    return scores

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [[False]*(W+1)]  #S[h][w]でアクセス
    for _ in range(H):
        S.append([False] + [True if x=='.' else False for x in input()])
    scores = bfs01(Ch, Cw, S, H, W)
    if scores[Dw][Dh] == 10**18:
        print(-1)
    else:
        print(scores[Dw][Dh])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Ch, Cw = Ch-1, Cw-1
    addr_c = Ch*W+Cw
    Dh, Dw = map(int, input().split())
    Dh, Dw = Dh-1, Dw-1
    addr_d = Dh*W+Dw
    #print(addr_c, addr_d)
    g = np.full((H*W, H*W), np.inf)
    S = []  #S[h][w]でアクセス すなわちx,y
    for _ in range(H):
        S.append([True if x=='.' else False for x in input()])
    exit()
    for x, y in itertools.product(range(H), range(W)):
        addr = x*W + y
        if not S[y][x]:
            continue
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[xx][yy]:
                #print(f"{x},{y} -> {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 0
                g[addr2, addr] = 0
        for xx, yy in [(x-2,y+2),(x-1,y+2),(x,y+2),(x+1,y+2),(x+2,y+2),(x-2,y+1),(x-1,y+1),(x+1,y+1),(x+2,y+1),(x-2,y),(x+2,y),
            (x-2,y-1),(x-1,y-1),(x+1,y-1),(x+2,y-1),(x-2,y-2),(x-1,y-2),(x,y-2),(x+1,y-2),(x+2,y-2),]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[xx][yy]:
                #print(f"{x},{y} => {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 1
                g[addr2, addr] = 1
    #print(g)
    #G2_masked = np.ma.masked_invalid(g)
    #print(G2_masked)
    #print(type(G2_masked))
    G2_sparse = csgraph_from_dense(g, null_value=np.inf)
    #print(G2_sparse)
    #print(type(G2_sparse))
    path = shortest_path(G2_sparse, indices=addr_c)
    if path[addr_d] != np.inf:
        print(int(path[addr_d]))
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
#import sys
#sys.setrecursionlimit(6000)

def bfs01(start_h, start_w, S, H, W):
    path = deque()
    path.append((start_h, start_w, 0))  #x, y, cost
    cost0 = set()
    cost1 = set()
    scores = [[10**18]*(H+1)]*(W+1)
    scores[start_h][start_w] = 0
    #BFS
    while path:
        x, y, cost = path.pop()
        if (x,y) in cost0:
            continue
        elif (x,y) in cost1 and cost==1:
            continue
        #print((x, y, cost))
        if cost==0:
            cost0.add((x,y))
        elif cost==1:
            cost1.add((x,y))
        else:
            assert False
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>H or yy>W:
                continue
            if scores[xx][yy] <= scores[x][y]:
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[xx][yy]:
                path.append((xx, yy,0))
                scores[xx][yy] = scores[x][y]
            for xx, yy in [(x-2,y+2),(x-1,y+2),(x,y+2),(x+1,y+2),(x+2,y+2),(x-2,y+1),(x-1,y+1),(x+1,y+1),(x+2,y+1),(x-2,y),(x+2,y),
                (x-2,y-1),(x-1,y-1),(x+1,y-1),(x+2,y-1),(x-2,y-2),(x-1,y-2),(x,y-2),(x+1,y-2),(x+2,y-2),]:
                continue
            if scores[xx][yy] <= scores[x][y] + 1:
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[xx][yy]:
                path.appendleft((xx, yy,1))
                scores[xx][yy] = scores[x][y] + 1
    return scores

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [[False]*(W+1)]  #S[h][w]でアクセス
    for _ in range(H):
        S.append([False] + [True if x=='.' else False for x in input()])  #ここでRE
    scores = bfs01(Ch, Cw, S, H, W)
    if scores[Dw][Dh] == 10**18:
        print(-1)
    else:
        print(scores[Dw][Dh])




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Ch, Cw = Ch-1, Cw-1
    addr_c = Ch*W+Cw
    Dh, Dw = map(int, input().split())
    Dh, Dw = Dh-1, Dw-1
    addr_d = Dh*W+Dw
    #print(addr_c, addr_d)
    g = np.full((H*W, H*W), np.inf)
    S = []  #S[h][w]でアクセス すなわちx,y
    for _ in range(H):
        S.append([True if x=='.' else False for x in input()])
    
    for x, y in itertools.product(range(H), range(W)):
        addr = x*W + y
        if not S[y][x]:
            continue
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[xx][yy]:
                #print(f"{x},{y} -> {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 0
                g[addr2, addr] = 0
        for xx, yy in [(x-2,y+2),(x-1,y+2),(x,y+2),(x+1,y+2),(x+2,y+2),(x-2,y+1),(x-1,y+1),(x+1,y+1),(x+2,y+1),(x-2,y),(x+2,y),
            (x-2,y-1),(x-1,y-1),(x+1,y-1),(x+2,y-1),(x-2,y-2),(x-1,y-2),(x,y-2),(x+1,y-2),(x+2,y-2),]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[xx][yy]:
                #print(f"{x},{y} => {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 1
                g[addr2, addr] = 1
    #print(g)
    #G2_masked = np.ma.masked_invalid(g)
    #print(G2_masked)
    #print(type(G2_masked))
    G2_sparse = csgraph_from_dense(g, null_value=np.inf)
    #print(G2_sparse)
    #print(type(G2_sparse))
    path = shortest_path(G2_sparse, indices=addr_c)
    if path[addr_d] != np.inf:
        print(int(path[addr_d]))
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Ch, Cw = Ch-1, Cw-1
    addr_c = Ch*W+Cw
    Dh, Dw = map(int, input().split())
    Dh, Dw = Dh-1, Dw-1
    addr_d = Dh*W+Dw
    #print(addr_c, addr_d)
    g = np.full((H*W, H*W), np.inf)  #ここでRE
    S = []  #S[w][h]でアクセス すなわちy,x
    for _ in range(W):
        S.append([True if x=='.' else False for x in input()])
    
    for x, y in itertools.product(range(H), range(W)):
        addr = x*W + y
        if not S[y][x]:
            continue
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[yy][xx]:
                #print(f"{x},{y} -> {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 0
                g[addr2, addr] = 0
        for xx, yy in [(x-2,y+2),(x-1,y+2),(x,y+2),(x+1,y+2),(x+2,y+2),(x-2,y+1),(x-1,y+1),(x+1,y+1),(x+2,y+1),(x-2,y),(x+2,y),
            (x-2,y-1),(x-1,y-1),(x+1,y-1),(x+2,y-1),(x-2,y-2),(x-1,y-2),(x,y-2),(x+1,y-2),(x+2,y-2),]:
            if xx<0 or yy<0 or xx>=H or yy>=W:
                continue
            if S[yy][xx]:
                #print(f"{x},{y} => {xx}, {yy}")
                addr2 = xx*W + yy
                g[addr, addr2] = 1
                g[addr2, addr] = 1
    #print(g)
    #G2_masked = np.ma.masked_invalid(g)
    #print(G2_masked)
    #print(type(G2_masked))
    G2_sparse = csgraph_from_dense(g, null_value=np.inf)
    #print(G2_sparse)
    #print(type(G2_sparse))
    path = shortest_path(G2_sparse, indices=addr_c)
    if path[addr_d] != np.inf:
        print(int(path[addr_d]))
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
#import sys
#sys.setrecursionlimit(6000)

def bfs01(start_h, start_w, S, H, W):
    path = deque()
    path.append((start_h, start_w, 0))  #x, y, cost
    cost0 = set()
    cost1 = set()
    scores = [[10**18]*(H+1)]*(W+1)
    scores[start_w][start_h] = 0
    #BFS
    while path:
        x, y, cost = path.pop()
        if (x,y) in cost0:
            continue
        elif (x,y) in cost1 and cost==1:
            continue
        #print((x, y, cost))
        if cost==0:
            cost0.add((x,y))
        elif cost==1:
            cost1.add((x,y))
        else:
            assert False
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>H or yy>W:
                continue
            if scores[yy][xx] <= scores[y][x]:
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[yy][xx]:
                path.append((xx, yy,0))
                scores[yy][xx] = scores[y][x]
            for xx, yy in [(x-2,y+2),(x-1,y+2),(x,y+2),(x+1,y+2),(x+2,y+2),(x-2,y+1),(x-1,y+1),(x+1,y+1),(x+2,y+1),(x-2,y),(x+2,y),
                (x-2,y-1),(x-1,y-1),(x+1,y-1),(x+2,y-1),(x-2,y-2),(x-1,y-2),(x,y-2),(x+1,y-2),(x+2,y-2),]:
                continue
            if scores[yy][xx] <= scores[y][x] + 1:
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[yy][xx]:
                path.appendleft((xx, yy,1))
                scores[yy][xx] = scores[y][x] + 1
    return scores

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [[False]*(W+1)]  #S[w][h]でアクセス すなわちy,x
    for _ in range(W):
        S.append([False] + [True if x=='.' else False for x in input()])
    exit()
    scores = bfs01(Ch, Cw, S, H, W)
    if scores[Dw][Dh] == 10**18:
        print(-1)
    else:
        print(scores[Dw][Dh])




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
#import sys
#sys.setrecursionlimit(6000)

def bfs01(start_h, start_w, S, H, W):
    path = deque()
    path.append((start_h, start_w, 0))  #x, y, cost
    cost0 = set()
    cost1 = set()
    scores = [[10**18]*(H+1)]*(W+1)
    scores[start_w][start_h] = 0
    #BFS
    while path:
        x, y, cost = path.pop()
        if (x,y) in cost0:
            continue
        elif (x,y) in cost1 and cost==1:
            continue
        #print((x, y, cost))
        if cost==0:
            cost0.add((x,y))
        elif cost==1:
            cost1.add((x,y))
        else:
            assert False
        for xx, yy in [(x,y+1), (x, y-1), (x+1, y), (x-1, y)]:
            if xx<0 or yy<0 or xx>H or yy>W:
                continue
            if scores[yy][xx] <= scores[y][x]:
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[yy][xx]:
                path.append((xx, yy,0))
                scores[yy][xx] = scores[y][x]
        for xx, yy in [(x-2,y+2),(x-1,y+2),(x,y+2),(x+1,y+2),(x+2,y+2),(x-2,y+1),(x-1,y+1),(x+1,y+1),(x+2,y+1),(x-2,y),(x+2,y),
            (x-2,y-1),(x-1,y-1),(x+1,y-1),(x+2,y-1),(x-2,y-2),(x-1,y-2),(x,y-2),(x+1,y-2),(x+2,y-2),]:
                continue
            if scores[yy][xx] <= scores[y][x] + 1:
                continue
            #print(f"xx, yy={xx},{yy}")
            if S[yy][xx]:
                path.appendleft((xx, yy,1))
                scores[yy][xx] = scores[y][x] + 1
    return scores

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [[False]*(W+1)]  #S[w][h]でアクセス すなわちy,x
    for _ in range(W):
        S.append([False] + [True if x=='.' else False for x in input()])
    exit()
    scores = bfs01(Ch, Cw, S, H, W)
    if scores[Dw][Dh] == 10**18:
        print(-1)
    else:
        print(scores[Dw][Dh])




if __name__ == "__main__":
    main()