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:
#dp[][]は何回のジャンプが必要かを示す

from collections import deque
h,w = list(map(int,input().split()))
sy,sx = list(map(int,input().split()))
gy,gx = list(map(int,input().split()))


sy -= 1
sx -= 1
gy -= 1
gx -= 1


grid = [input() for _ in range(h)]
dp = [[-1 for _ in range(w)] for _ in range(h)]

dp[sy][sx] = 0

#print(dp)
pos_que = deque()
pos_que.append((sx,sy))
#print(pos_que)
ps = deque()
ps.append((sx,sy))

def area_move(pos_que):
    while pos_que:
        px,py = pos_que.popleft()
        d = dp[py][px]
        ps.append((px,py))
        for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
            px_new = px + dx
            py_new = py + dy
            if py_new < 0 or h <= py_new or px_new < 0 or w <= px_new or dp[py_new][px_new] != -1 or grid[py_new][px_new] = '#':
                continue
            else
                dp[py_new][px_new] = d
                pos_que.append((px_new,py_new))
                ps.append((px_new,py_new))
    return False




def magic_jump(n,ps):
    while ps:
        if True:
            i,j = ps.popleft()
            #print(i,j)
            if dp[j][i] == n:
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i+dx
                    new_h = j + dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_wor grid[new_h][new_w] == '#' or dp[new_h][new_w] >-1:
                        continue
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i-dx
                    new_h = j-dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w or grid[new_h][new_w] == '#' or dp[new_h][new_w] >-1:
                        continue
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                        
                        
                
def main(dp_old):
    for i in range(10000000):
        area_move(pos_que)
        if dp[gy][gx] != -1:
            return dp[gy][gx]
        magic_jump(i,ps)
        if not pos_que:
            return -1
    return -1

print(main([]))

Submission status: Runtime Error

Solution code:
#dp[][]は何回のジャンプが必要かを示す

from collections import deque
h,w = list(map(int,input().split()))
sy,sx = list(map(int,input().split()))
gy,gx = list(map(int,input().split()))


sy -= 1
sx -= 1
gy -= 1
gx -= 1


grid = [input() for _ in range(h)]
dp = [[-1 for _ in range(w)] for _ in range(h)]

dp[sy][sx] = 0

#print(dp)
pos_que = deque()
pos_que.append((sx,sy))
#print(pos_que)
ps = deque()
ps.append((sx,sy))

def area_move(pos_que):
    while pos_que:
        px,py = pos_que.popleft()
        d = dp[py][px]
        ps.append((px,py))
        for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
            px_new = px + dx
            py_new = py + dy
            if py_new < 0 or h <= py_new or px_new < 0 or w <= px_new or dp[py_new][px_new] != -1 or grid[py_new][px_new] = '#':
                continue
            else
                dp[py_new][px_new] = d
                pos_que.append((px_new,py_new))
                ps.append((px_new,py_new))
    return False




def magic_jump(n,ps):
    while ps:
        if True:
            i,j = ps.popleft()
            #print(i,j)
            if dp[j][i] == n:
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i+dx
                    new_h = j + dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_wor grid[new_h][new_w] == '#' or dp[new_h][new_w] >-1:
                        continue
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i-dx
                    new_h = j-dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w or grid[new_h][new_w] == '#' or dp[new_h][new_w] >-1:
                        continue
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                        
                        
                
def main(dp_old):
    for i in range(10000000):
        area_move(pos_que)
        if dp[gy][gx] != -1:
            return dp[gy][gx]
        magic_jump(i,ps)
        if not pos_que:
            return -1

print(main([]))

Submission status: Runtime Error

Solution code:
#dp[][]は何回のジャンプが必要かを示す

from collections import deque
h,w = list(map(int,input().split()))
sy,sx = list(map(int,input().split()))
gy,gx = list(map(int,input().split()))


sy -= 1
sx -= 1
gy -= 1
gx -= 1


grid = [input() for _ in range(h)]
dp = [[-1 for _ in range(w)] for _ in range(h)]

dp[sy][sx] = 0

#print(dp)
pos_que = deque()
pos_que.append((sx,sy))
#print(pos_que)
ps = deque()
ps.append((sx,sy))

def area_move(pos_que):
    while pos_que:
        px,py = pos_que.popleft()
        d = dp[py][px]
        ps.append((px,py))
        for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
            px_new = px + dx
            py_new = py + dy
            if py_new < 0 or h <= py_new or px_new < 0 or w <= px_new or dp[py_new][px_new] != -1:
                continue
            if grid[py_new][px_new] == '.':
                dp[py_new][px_new] = d
                pos_que.append((px_new,py_new))
                ps.append((px_new,py_new))
    return False




def magic_jump(n,ps):
    while ps:
        if True:
            i,j = ps.popleft()
            #print(i,j)
            if dp[j][i] == n:
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i+dx
                    new_h = j + dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                        continue
                    if grid[new_h][new_w] == '#' or dp[new_h][new_w] >=0:
                        
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i-dx
                    new_h = j-dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                        continue
                    if grid[new_h][new_w] == '#' or dp[new_h][new_w] >-1:
                        
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                        
                        
                
def main(dp_old):
    for i in range(10000000):
        area_move(pos_que)

        if dp[gy][gx] != -1:
            return dp[gy][gx]
        magic_jump(i,ps)

        #print(i)
        if not pos_que:
            return -1

print(main([]))

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
sx,sy = map(int,input().split())
sx -= 1
sy -= 1
gx,gy = map(int,input().split())
gx -= 1
gy -= 1
route = []
for i in range(h):
  lst = list(input())
  route.append(lst)
  
brock = [['#']*w for i in range(h)]
s = 0
que = deque([])
dx = [-1,0,1,0]
dy = [0,-1,0,1]

brock[sx][sy] = 0
que.append((sx,sy))
lst = [(sx,sy)]


while que:
  
  (p,q) = que.popleft()
  if (p,q) == (gx,gy):
    print(brock[gx][gy])
    sys.exit()
  for i in range(4):
    p2,q2 = p+dx[i],q+dy[i]
    if 0 <= p2 < h and 0<= q2 < w and route[p2][q2] == '.' and brock[p2][q2] == '#':
      brock[p2][q2] = brock[p][q]
      que.append((p2,q2))
      lst.append((p2,q2))
  
  if len(que) == 0:
    
    s += 1
    for u in range(h):
      for v in range(w):
        if brock[u][v] == s-1:
          x,y = u,v
          for j in range(-2,3):
             for k in range(-2,3):
                x2 = x+j
                y2 = y+k
                if 0 <= x2 < h and 0<= y2 < w and route[x2][y2] == '.' and brock[x2][y2] == '#':
                  brock[x2][y2] = s
                  que.append((x2,y2))
            
                  
              
print(-1)

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
c = list(map(int,input().split()))
c[0] -= 1
c[1] -= 1
d = list(map(int,input().split()))
d[0] -= 1
d[1] -= 1
p = []
q = [[None for i in range(w)]for i in range(h)]
r = [[] for i in range(10**6)]
for i in range(h):
    s = input()
    s = list(s)
    p.append(s)
from collections import deque
de = deque()
de.append([c[0],c[1]])
q[c[0]][c[1]] = 0
g = 0
while q[d[0]][d[1]] == None and g < 10**6-3:
    while de:
        v = de.popleft()
        r[g].append([v[0],v[1]])
        for i in (-1,1):
            j = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
        for j in (-1,1):
            i = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
    g += 1
    while r[g-1]:
        v = r[g-1].pop()
        for i in range(-2,3):
            for j in range(-2,3):
                if (abs(i) == 1 and j = 0 ) or (abs(j) == 1 and i == 0)
                    continue
                else:
                    if 0 <= v[0]-i <= h-1:
                        if 0 <= v[1]-j <= w-1:
                            if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                                q[v[0]-i][v[1]-j] = g
                                de.append([v[0]-i,v[1]-j])
if q[d[0]][d[1]] == None:
    print(-1)
else:
    print(q[d[0]][d[1]])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)

[h,w]=list(map(int,input().split()))
[ch,cw]=list(map(int,input().split()))
[dh,dw]=list(map(int,input().split()))
chizu=[]
for i in range(h):
    chizu.append(list(input()))

chizu[ch-1][cw-1]=0
jougesayu=[[-1,0],[1,0],[0,-1],[0,1]]
warp=[]
for i in [-2,-1,0,1,2]:
    for j in [-2,-1,0,1,2]:
        if [i,j] not in jougesayu:
            warp.append([i,j])

def bfs(x,y,num):
    global chizu
    for [i,j] in jougesayu:#上下左右
        if i!=0 or j!=0:#周囲の24つ調べる
            if 1<=x+i<=h and 1<=y+j<=w:#枠内ならば
                if chizu[x+i-1][y+j-1]!="#":#道があれば
                    if chizu[x+i-1][y+j-1]==".":#未到達なら数ふる
                        chizu[x+i-1][y+j-1]=num
                        bfs(x+i,y+j,num)
                    else:#到達済みなら
                        if num<chizu[x+i-1][y+j-1]:#より早ければ
                            chizu[x+i-1][y+j-1]=num
                            bfs(x+i,y+j,num)
    for [i,j] in warp:#ワープ
        if chizu[x+i-1][y+j-1]!="#":#道があれば
            if chizu[x+i-1][y+j-1]==".":#未到達なら数ふる
                chizu[x+i-1][y+j-1]=num+1
                bfs(x+i,y+j,num+1)
            else:#到達済みなら
                if num+1<chizu[x+i-1][y+j-1]:#より早ければ
                    chizu[x+i-1][y+j-1]=num+1
                    bfs(x+i,y+j,num+1)

bfs(ch,cw,0)
ans=chizu[dh-1][dw-1]
if chizu[dh-1][dw-1]=="#" or chizu[dh-1][dw-1]==".":
    ans=-1
print(ans)

Submission status: Runtime Error

Solution code:
f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")

H, W = map(int, f.readline().split())
C = list(map(lambda x: int(x)-1, f.readline().split()))
D = list(map(lambda x: int(x)-1, f.readline().split()))

Ss = [str(f.readline()) for _ in range(H)]
group = [[-1 for _ in range(W)] for _ in range(H)]

moves = [[-1,0], [1,0], [0,-1], [0,1]]

from collections import deque
todo = deque()
now_group = -1
for i in range(H):
    for j in range(W):
        if group[i][j] == -1 and Ss[i][j]==".":
            todo.append([i,j])
            now_group += 1
            group[i][j] = now_group
        while len(todo) > 0:
            checking = todo.pop()
            for move in moves:
                now = [checking[0]+move[0],checking[1]+move[1]]
                if not (0 <= now[0] <H and 0 <= now[1] <W):
                    continue
                if group[now[0]][now[1]] == -1 and Ss[now[0]][now[1]]==".":
                    todo.append(now)
                    group[now[0]][now[1]] = now_group

can_waap = [set() for _ in range(now_group+1)]

for i in range(H):
    for j in range(W):
        if group[i][j] ==-1:
            continue
        for yoko in range(-2,3):
            for tate in range(-2,3):
                now = [tate+i, yoko+j]
                if not (0<=now[0]<H and 0<=now[1]<W):
                    continue
                if group[now[0]][now[1]] == -1:
                    continue
                
                if group[i][j] != group[now[0]][now[1]]:
                    can_waap[group[i][j]].add(group[now[0]][now[1]])
                    can_waap[group[now[0]][now[1]]].add(group[i][j])
start = group[C[0]][C[1]]
goal = group[D[0]][D[1]]
import sys
import copy
seen = set([start])
nows = [start]

if start==goal:
    print(0)
    sys.exit()

for step in range(now_group+1):
    pre_nows = copy.deepcopy(nows)
    nows = []
    for pre_now in range(len(pre_nows)):
        for j in can_waap[pre_now]:
            if j not in seen:
                seen.add(j)
                nows.append(j)
                if j == goal:
                    print(step+1)
                    sys.exit()

print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import defaultdict

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []

island_map = np.zeros((H, W), dtype=np.int)
num_island = 1

for h in range(H):
    S = input()
    for w, s in enumerate(S):
        if s == '.':
            if island_map[max(h-1, 0), w] + island_map[h, max(w-1, 0)] > 0:
                if island_map[max(h-1, 0), w] == 0:
                    island_map[h, w] = island_map[h, max(w - 1, 0)]
                elif island_map[h, max(w - 1, 0)] == 0:
                    island_map[h, w] = island_map[max(h-1, 0), w]
                else:
                    island_map[h, w] = island_map[max(h-1, 0), w]
                    island_map[h, max(w-1, 0)] = island_map[max(h-1, 0), w]
            else:
                island_map[h, w] = num_island
                num_island += 1
            
start_island = island_map[Ch-1, Cw-1]
goal_island = island_map[Dh-1, Dw-1]
print('aaa')
if start_island == goal_island:
    print(0)
    exit()

pad_island_map = np.zeros((H+4, W+4), dtype=np.int)
pad_island_map[2:2+H, 2:2+W] = island_map

accessable_island_table = np.zeros((num_island-1, num_island-1), dtype=np.int)

for h in range(2, H+2):
    for w in range(2, W+2):
        island = pad_island_map[h, w]
        if island > 0:
            go_island = np.unique(pad_island_map[h-2:h+3, w-2:w+3]).reshape(-1)
            for i in go_island:
                if i > 0 and i != island:
                    accessable_island_table[i-1, island-1] = 1
#print(island_map)
#print(accessable_island_table)

from heapq import heappush, heappop
INF = 10 ** 9
def dijkstra(s, n): # (始点, ノード数)
    dist = [INF] * n
    hq = [(0, s)] # (distance, node)
    dist[s] = 0
    seen = [False] * n # ノードが確定済みかどうか
    while hq:
        v = heappop(hq)[1] # ノードを pop する
        seen[v] = True
        for to, cost in adj[v]: # ノード v に隣接しているノードに対して
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist

adj = [[] for _ in range(num_island-1)]
for i in range(num_island-1):
    for j in range(num_island-1):
        if accessable_island_table[i, j] == 1:
            adj[i].append((j, 1))

#print(adj)
d = dijkstra(start_island-1, num_island-1)
ans = d[goal_island-1]
if ans > 10 ** 5:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import defaultdict

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []

map_ = np.zeros((H, W), dtype=np.int)

for h in range(H):
    S.append(input())
    for w, s in enumerate(S[-1]):
        if s == '.':
            map_[h, w] = 1

island_map = np.zeros((H, W), dtype=np.int)
num_island = 1

for h in range(H):
    for w in range(W):
        if map_[h, w] == 1:
            if island_map[max(h-1, 0), w] + island_map[h, max(w - 1, 0)] > 0:
                if island_map[max(h-1, 0), w] == 0:
                    island_map[h, w] = island_map[h, max(w - 1, 0)]
                elif island_map[h, max(w - 1, 0)] == 0:
                    island_map[h, w] = island_map[max(h-1, 0), w]
                else:
                    island_map[h, w] = island_map[max(h-1, 0), w]
                    island_map[h, max(w-1, 0)] = island_map[max(h-1, 0), w]
            else:
                island_map[h, w] = num_island
                num_island += 1
            
start_island = island_map[Ch-1, Cw-1]
goal_island = island_map[Dh-1, Dw-1]
print('aaa')
if start_island == goal_island:
    print(0)
    exit()

pad_island_map = np.zeros((H+4, W+4), dtype=np.int)
pad_island_map[2:2+H, 2:2+W] = island_map

accessable_island_table = np.zeros((num_island-1, num_island-1), dtype=np.int)

for h in range(2, H+2):
    for w in range(2, W+2):
        island = pad_island_map[h, w]
        if island > 0:
            go_island = np.unique(pad_island_map[h-2:h+3, w-2:w+3]).reshape(-1)
            for i in go_island:
                if i > 0 and i != island:
                    accessable_island_table[i-1, island-1] = 1
#print(island_map)
#print(accessable_island_table)

from heapq import heappush, heappop
INF = 10 ** 9
def dijkstra(s, n): # (始点, ノード数)
    dist = [INF] * n
    hq = [(0, s)] # (distance, node)
    dist[s] = 0
    seen = [False] * n # ノードが確定済みかどうか
    while hq:
        v = heappop(hq)[1] # ノードを pop する
        seen[v] = True
        for to, cost in adj[v]: # ノード v に隣接しているノードに対して
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist

adj = [[] for _ in range(num_island-1)]
for i in range(num_island-1):
    for j in range(num_island-1):
        if accessable_island_table[i, j] == 1:
            adj[i].append((j, 1))

#print(adj)
d = dijkstra(start_island-1, num_island-1)
ans = d[goal_island-1]
if ans > 10 ** 5:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import defaultdict

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []

map_ = np.zeros((H, W), dtype=np.int)

for h in range(H):
    S.append(input())
    for w, s in enumerate(S[-1]):
        if s == '.':
            map_[h, w] = 1

island_map = np.zeros((H, W), dtype=np.int)
num_island = 1
start_island, goal_island = 0, 0

for h in range(H):
    for w in range(W):
        if map_[h, w] == 1:
            if island_map[max(h-1, 0), w] + island_map[h, max(w - 1, 0)] > 0:
                if island_map[max(h-1, 0), w] == 0:
                    island_map[h, w] = island_map[h, max(w - 1, 0)]
                elif island_map[h, max(w - 1, 0)] == 0:
                    island_map[h, w] = island_map[max(h-1, 0), w]
                else:
                    island_map[h, w] = island_map[max(h-1, 0), w]
                    island_map[h, max(w - 1, 0)] = island_map[max(h-1, 0), w]
                # island_map[h, w] = max(island_map[max(h-1, 0), w], island_map[h, max(w - 1, 0)])
            else:
                island_map[h, w] = num_island
                num_island += 1
            
start_island = island_map[Ch-1, Cw-1]
goal_island = island_map[Dh-1, Dw-1]

if start_island == goal_island:
    print(0)
    exit()

pad_island_map = np.zeros((H+4, W+4), dtype=np.int)
pad_island_map[2:2+H, 2:2+W] = island_map

accessable_island_table = np.zeros((num_island-1, num_island-1), dtype=np.int)

for h in range(2, H+2):
    for w in range(2, W+2):
        island = pad_island_map[h, w]
        if island > 0:
            go_island = np.unique(pad_island_map[h-2:h+3, w-2:w+3]).reshape(-1)
            for i in go_island:
                if i > 0 and i != island:
                    accessable_island_table[i-1, island-1] = 1
print(island_map)
print(accessable_island_table)

from heapq import heappush, heappop
INF = 10 ** 9
def dijkstra(s, n): # (始点, ノード数)
    dist = [INF] * n
    hq = [(0, s)] # (distance, node)
    dist[s] = 0
    seen = [False] * n # ノードが確定済みかどうか
    while hq:
        v = heappop(hq)[1] # ノードを pop する
        seen[v] = True
        for to, cost in adj[v]: # ノード v に隣接しているノードに対して
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist

adj = [[] for _ in range(num_island-1)]
for i in range(num_island-1):
    for j in range(num_island-1):
        if accessable_island_table[i, j] == 1:
            adj[i].append((j, 1))

#print(adj)
d = dijkstra(start_island-1, num_island-1)
ans = d[goal_island-1]
if ans > 10 ** 5:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import defaultdict

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []

map_ = np.zeros((H, W), dtype=np.int)

for h in range(H):
    S.append(input())
    for w, s in enumerate(S[-1]):
        if s == '.':
            map_[h, w] = 1

#print(map_)
island_map = np.zeros((H, W), dtype=np.int)
num_island = 1
start_island, goal_island = 0, 0

for h in range(H):
    for w in range(W):
        if map_[h, w] == 1:
            if island_map[max(h-1, 0), w] + island_map[h, max(w - 1, 0)] > 0:
                island_map[h, w] = max(island_map[max(h-1, 0), w], island_map[h, max(w - 1, 0)])
            else:
                island_map[h, w] = num_island
                num_island += 1
            if (h + 1) == Ch and (w + 1) == Cw:
                start_island = island_map[h, w]
            if (h + 1) == Dh and (w + 1) == Dw:
                goal_island = island_map[h, w]

if start_island == goal_island:
    print(0)
    exit()

pad_island_map = np.zeros((H+4, W+4), dtype=np.int)
pad_island_map[2:2+H, 2:2+W] = island_map

accessable_island_table = np.zeros((num_island-1, num_island-1), dtype=np.int)

for h in range(2, H+2):
    for w in range(2, W+2):
        island = pad_island_map[h, w]
        if island > 0:
            go_island = np.unique(pad_island_map[h-2:h+3, w-2:w+3]).reshape(-1)
            for i in go_island:
                if i > 0 and i != island:
                    accessable_island_table[i-1, island-1] = 1

#print(accessable_island_table)

from heapq import heappush, heappop
INF = 10 ** 9
def dijkstra(s, n): # (始点, ノード数)
    dist = [INF] * n
    hq = [(0, s)] # (distance, node)
    dist[s] = 0
    seen = [False] * n # ノードが確定済みかどうか
    while hq:
        v = heappop(hq)[1] # ノードを pop する
        seen[v] = True
        for to, cost in adj[v]: # ノード v に隣接しているノードに対して
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist

adj = [[] for _ in range(num_island-1)]
for i in range(num_island-1):
    for j in range(num_island-1):
        if accessable_island_table[i, j] == 1:
            #print(i, j)
            adj[i].append((j, 1))

#print(adj)
d = dijkstra(start_island-1, num_island-1)
ans = d[goal_island-1]
if ans > 10 ** 5:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x:int(x)-1, input().split())    #0indexにして受け取る
dh, dw = map(lambda x:int(x)-1, input().split())
s = [input() for _ in range(h)]
#距離(スタートからijまでの総コスト)
MAX_DIST = 10**9
dist = [[MAX_DIST]*w for _ in range(h)]
dist[ch][cw] = 0
#両端キュー
dq = deque()
dq.append((ch, cw, dist[ch][cw]))

#01-BFS
while dq:
    i, j, d = dq.popleft()
    #コスト0で追加されたキューが，コスト1として追加されたとき評価しない
    if d > dist[i][j]:
        continue
    #歩いて移動
    d = dist[i][j]
    for i2, j2 in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):
        #範囲外へは進めない
        if not (0 <= i2 < h and 0 <= j2 < w):
            continue
        #壁へは進めない
        if s[i2][j2] == '#':
            continue
        #距離が小さければ更新
        if d < dist[i2][j2]:
            dist[i2][j2] = d
            #キューの先頭に追加
            dq.appendleft((i2,j2))

    #ワープ移動
    d += 1
    for ei in range(-2,3):
        i2 = i+ei
        #範囲外へは進めない
        if not 0 <= i2 < h:
            continue
        for ej in range(-2,3):
            j2 = j+ej
            #範囲外へは進めない
            if not 0 <= j2 < w:
                continue
            #同じ地点へのワープは無視
            if (i2,j2) == (i,j):
                continue
            #壁へは進めない
            if s[i2][j2] == '#':
                continue
            #距離が小さければ更新
            if d < dist[i2][j2]:
                dist[i2][j2] = d
                #キューの末尾に追加
                dq.append((i2, j2))

if MAX_DIST == dist[dh][dw] :
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Runtime Error

Solution code:
from collections import deque

class BFS:
    def __init__(self, H, W, S, C, D):
        self.H = H
        self.W = W
        self.S = S
        # 魔法使いの場所
        self.C = C
        # 目的地
        self.D = D

        # 盤面上のセルの状態
        # -1: 未到達
        # 0 : 魔法0回で到達
        # 1 : 魔法1回で到達
        # 2 : 魔法2回で到達, and so on...
        self.board_states = [[-1] * W for i in range(H)]
        self.board_states[C[0]][C[1]] = 0
        self.queue = deque([C])
        self.remain_cells = [C]

    def is_legal_move(self, move):
        h = move[0]
        w = move[1]

        if h < 0 or h >= self.H or w < 0 or w >= self.W:
            return False
        return self.S[h][w] == "."

    def is_not_visited(self, move):
        h = move[0]
        w = move[1]
        return self.board_states[h][w] == -1

    def walk(self):
        next_queue = deque([])
        while len(self.queue) > 0:
            if len(self.queue) == 0 and len(next_queue) > 0:
                self.queue = next_queue

            move = self.queue.popleft()

            up = (move[0]-1, move[1])
            down = (move[0]+1, move[1])
            left = (move[0], move[1]-1)
            right = (move[0], move[1]+1)

            next_moves = list(filter(self.is_legal_move, [up, down, left, right]))

            for next_move in next_moves:
                if self.is_not_visited(next_move):
                    self.queue.append(next_move)
                    self.remain_cells.append(next_move)
                    self.set_boart_states(next_move, self.get_boart_states(move))

    def set_boart_states(self, move, value):
        self.board_states[move[0]][move[1]] = value

    def get_boart_states(self, move):
        return self.board_states[move[0]][move[1]]

    def print_board_states(self):
        for l in self.board_states:
            print(l)

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, input().split())
D_h -= 1
D_w -= 1

S = [ [None] * W for i in range(H) ]
for i in range(H):
    l = input()
    for j, s in enumerate(l):
        S[i][j] = s

bfs = BFS(H, W, S, (C_h, C_w), (D_h, D_w))

while (True):
    bfs.walk()
    if len(bfs.remain_cells) == 0:
        break
    
    while len(bfs.remain_cells) > 0:
        move = bfs.remain_cells.pop()
        for i in range(-2, 3):
            for j in range(-2, 3):
                next_move = (move[0]+i, move[1]+j)
                if not bfs.is_legal_move(next_move):
                    continue

                if bfs.is_not_visited(next_move):
                    bfs.queue.append(next_move)
                    bfs.set_boart_states(next_move, bfs.get_boart_states(move) + 1)
                elif (not bfs.is_not_visited(nextmove)) and bfs.get_boart_states(next_move) > bfs.get_boart_states(move) + 1:
                    bfs.queue.append(next_move)
                    bfs.set_boart_states(next_move, bfs.get_boart_states(move) + 1)

print(bfs.get_boart_states((D_h, D_w)))