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:
import sys
import math
import heapq

(h, w) = [int(x) for x in sys.stdin.readline().strip().split(" ")]
(c_h, c_w) = [int(x) for x in sys.stdin.readline().strip().split(" ")]
(d_h, d_w) = [int(x) for x in sys.stdin.readline().strip().split(" ")]

maze = []
for line in sys.stdin:
    maze.append(list(line.strip())) 

def isReachable(i, j):
    if i < 1 or i > h or j < 1 or j > w:
        return False

    c = maze[i-1][j - 1]
    if c == '#':
        return False
    else:
        return True

def distance(fp, tp):
    if not isReachable(tp[1], tp[2]):
        return None

    h_diff = math.fabs(tp[1] - fp[1])
    w_diff = math.fabs(tp[2] - fp[2])

    if h_diff + w_diff < 2:
        return 0

    if h_diff < 3 or w_diff < 3:
        return 1

def adjacents(current):
    adjs = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0:
                continue
            dst = (None, current[1] + i, current[2] + j)
            dist = distance(current, dst)
            if dist is not None:
                dst = (dist, dst[1], dst[2])
                adjs.append(dst)

    return adjs

def dijkstra(results, start):
    """Calcualte the distance from start points to all the node
    """
    cur_dist = 0
    results[start[1] - 1][start[2] -1] = cur_dist
    heap = [ (p[0] + cur_dist, p[1], p[2]) for p in  adjacents(start) ]
    heapq.heapify(heap)

    while len(heap) > 0:
        visited = heapq.heappop(heap)
        if results[visited[1] - 1][visited[2] -1] is not None:
            continue

        results[visited[1] - 1][visited[2] -1] = visited[0]
        cur_dist = visited[0]

        adjs = list(filter(lambda x: results[x[1] - 1][x[2] - 1] is None, adjacents(visited)))

        for a in [(p[0] + cur_dist, p[1], p[2]) for p in adjs]:
            heapq.heappush(heap, a)


@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main():
    results = [[None] * w for i in range(0, h)]
    start = (0, c_h, c_w)

    dijkstra(results, start)

    if results[d_h - 1][d_w -1] is None:
        print(-1)
    else:
        print(results[d_h - 1][d_w -1])

Submission status: Runtime Error

Solution code:

from collections import deque
HW = input().split()
H, W = int(HW[0]), int(HW[1])
C = input().split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    route.append(input())


visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):z
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.pop()
        elif len(warpkouho) != 0:
            tmp = warpkouho.pop()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                    check_warp(h-2+n, w-2+m, warp)
        if h == Dh-1 and w == Dw-1:
            print(visited[h][w]-1)
            return
    print(-1)
wizard()

Submission status: Runtime Error

Solution code:

from collections import deque
HW = input(),split()
H, W = int(HW[0]), int(HW[1])
C = input()split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    tmpr = input().split()
    route.append(tmp)

visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.pop()
        elif len(warpkouho) != 0:
            tmp = warpkouho.pop()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                    check_warp(h-2+n, w-2+m, warp)
        if h == Dh-1 and w == Dw-1:
            print(visited[h][w]-1)
            return
    print(-1)
wizard()

Submission status: Runtime Error

Solution code:

from collections import deque
HW = input(),split()
H, W = int(HW[0]), int(HW[1])
C = input()split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    tmpr = input().split()
    route.append(tmp)
'''
H, W = 4, 4
Ch, Cw = 1, 1
Dh, Dw= 4, 4
route = [[".",".","#","."],[".",".","#","."],[".","#",".","."],[".","#",".","."]]
'''
visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.pop()
        elif len(warpkouho) != 0:
            tmp = warpkouho.pop()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                    check_warp(h-2+n, w-2+m, warp)
        if h == Dh-1 and w == Dw-1:
            print(visited[h][w]-1)
            return
    print(-1)
wizard()

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
S=["#"*(W+4)]
S.append("#"*(W+4))
for _ in range(H):
    tmp=input()
    tmp="##"+tmp+"##"
    S.append(tmp)
S.append("#"*(W+4))
S.append("#"*(W+4))

def walk(k,alk,x,y):
    global found
    if x==D[0] and y==D[1]:
        S[x]=S[x][:y]+"{}".format(k)+S[x][y+1:]
        found=True
        return 0
    if S[x][y]==".":
        alk.append([x,y])
        S[x]=S[x][:y]+"{}".format(k)+S[x][y+1:]
        walk(k,alk,x-1,y)
        walk(k,alk,x,y-1)
        walk(k,alk,x+1,y)
        walk(k,alk,x,y+1)

def warp(k,arp,x,y):
    for i in range(-2,3):
        for j in range(-2,3):
            if S[x+i][y+j]==".":
                arp.append([x+i,y+j])
                S[x+i]=S[x+i][:y+j]+"{}".format(k)+S[x+i][y+j+1:]

k=0
alk=[]
arp=[[C[0],C[1]]]
found=False
while not found:
    alk=arp
    for i in range(len(arp)):
        x,y=arp[i][0],arp[i][1]
        walk(k,alk,x,y)
        if found:
            print(k)
            break
    if found:
        break
    k+=1
    arp=[]
    for i in range(len(alk)):
        x,y=alk[i][0],alk[i][1]
        warp(k,arp,x,y)
    if len(arp)==0:
        print(-1)
        break

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

#visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #print "fro_h, fro_w, q :: ",fro_h, fro_w, q
    #print "fro_h, fro_w, q :: ",fro_h, fro_w
    #print "d :: ",d
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)]:
                d[(to_h, to_w)]=d[(fro_h, fro_w)]
                q.appendleft((to_h, to_w))
        #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]=="." and d[(fro_h, fro_w)]+1<d[(to_h, to_w)]:
                d[(to_h, to_w)]=d[(fro_h, fro_w)]
                q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import heapq

h,w=map(int,input().split())
sy,sx=map(int,input().split())
sy-=1
sx-=1
gy,gx=map(int,input().split())
gy-=1
gx-=1
board=''
for _ in range(h):
  board+=input()
costs=[10**18]*(w*h)
costs[sy*w+sx]=0
q=[]
heapq.heappush(q,(0,sy,sx))
while len(q)!=0:
  cost,y,x=heapq.heappop(q)
  cur_pos=y*w+x
  for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
    next_pos=cur_pos+dy*w+dx
    if 1<=y+dy<=h and 1<=x+dx<=w and board[next_pos]=='.' and costs[next_pos]>costs[cur_pos]:
      costs[next_pos]=costs[cur_pos]
      heapq.heappush(q,(cost,y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dy==0 and dx==0:
        continue
      next_pos=cur_pos+dy*w+dx
      if 1<=y+dy<=h and 1<=x+dx<=w and board[next_pos]=='.' and costs[next_pos]>costs[cur_pos]+1:
        costs[next_pos]=costs[cur_pos]+1
        heapq.heappush(q,(cost+1,y+dy,x+dx))
if costs[gy*w+gx]==10**18:
  print(-1)
else:
  print(costs[gy*w+gx])

Submission status: Runtime Error

Solution code:
from heapq import *
from sys import stdin
input=stdin.readline
n,m=map(int,input().split())
a,b=map(int,input().split())
x,y=map(int,input().split())
x=x-1
y=y-1
arr=[]
from math import inf
for i in range(n):
    arr.append(list(input().strip()))
def isvalid(x,y):
    if x<0 or y<0 or x>=n or y>=m or arr[x][y]=="#" :
        return False
    return True
vis=[[0]*m for i in range(n)]
stack=[[0,a-1,b-1]]
heapify(stack)
if x==a-1 and y==b-1 and arr[x][y]=="#":
    print(-1)
    quit()
mi=inf
ans=[[inf]*m for i in range(n)]
while(stack):
    cost,xx,yy=heappop(stack)
    if xx==x and yy==y:
        mi=min(mi,cost)
        break
    for i in [[-1,0],[1,0],[0,1],[0,-1]]:
        if isvalid(xx+i[0],yy+i[1]):
            if ans[xx+i[0]][yy+i[1]]>cost:
              	ans[xx+i[0]][yy+i[1]]=cost
                heappush(stack,[cost,xx+i[0],yy+i[1]])
    for i in range(-2,3):
        for j in range(-2,3):
            if isvalid(xx+i,yy+j):
                if ans[xx+i][yy+j]>cost+1:
                  	ans[xx+i][yy+j]=cost+1
                    heappush(stack,[cost+1,xx+i,yy+j])
       
if mi==inf:
    print(-1)
else:
    print(mi)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        WARP.append((dh,dw))

#visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="."  and d[(fro_h, fro_w)]+1<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
            q.appendleft((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

#visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="."  and d[(fro_h, fro_w)]+1<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
            q.appendleft((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
from collections import deque
f_inf = float('inf')
H, W = map(int, input().split())
ch, cw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = map(int, input().split())
dh, dw = dh-1, dw-1
S = [list(input()) for _ in range(H)]
m = [[f_inf]*W for _ in range(H)]
m[ch][cw] = 0
que = deque([])
que.appendleft([ch,cw])
while que:
  h, w = que.popleft()
  for dh, dw in ((1,0), (-1,0), (0, 1), (0, -1)):
    next_h, next_w = h + dh, w + dw
    if 0 <= next_h < H and 0 <= next_w < W and S[next_h][next_w] == ".":
        if m[next_h][next_w] > m[h][w]:
          m[next_h][next_w] = m[h][w] # 移動Aで行けるところにmの値を合わせる
          que.appendleft([next_h,next_w])
  for dh in range(-2, 3):
    for dw in range(-2, 3): # 移動Bで行ける範囲
      next_h, next_w = h + dh, w + dw
      if 0 <= next_h < H and 0 <= next_w < W and S[next_h][next_w] == ".":
        if m[next_h][next_w] > m[h][w] + 1: # h,wから移動Aですでに行けているところは更新されない
          m[next_h][next_w] = m[h][w] + 1 
          que.append([next_h, next_w]) # appendleftではなくappend 優先順位が後
print(m[dh][dw] if m[dh][dw] != f_inf else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
f_inf = float('inf')
H, W = map(int, input().split())
ch, cw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = map(int, input().split())
dh, dw = dh-1, dw-1
S = [list(input()) for _ in range(H)]
m = [[f_inf]*W for _ in range(H)]
m[ch][cw] = 0
que = deque([])
que.appendleft([ch,cw])
while que:
  print(que)
  print(m)
  h, w = que.popleft()
  for dh, dw in ((1,0), (-1,0), (0, 1), (0, -1)):
    next_h, next_w = h + dh, w + dw
    if 0 <= next_h < H and 0 <= next_w < W and S[next_h][next_w] == ".":
        if m[next_h][next_w] > m[h][w]:
          m[next_h][next_w] = m[h][w] # 移動Aで行けるところにmの値を合わせる
          que.appendleft([next_h,next_w])
  for dh in range(-2, 3):
    for dw in range(-2, 3): # 移動Bで行ける範囲
      next_h, next_w = h + dh, w + dw
      if 0 <= next_h < H and 0 <= next_w < W and S[next_h][next_w] == ".":
        if m[next_h][next_w] > m[h][w] + 1: # h,wから移動Aですでに行けているところは更新されない
          m[next_h][next_w] = m[h][w] + 1 
          que.append([next_h, next_w]) # appendleftではなくappend 優先順位が後
print(m[dh][dw] if m[dh][dw] != f_inf else -1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

#visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))


q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori,fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            alt=d[(fro_h, fro_w)]+0
            if alt<d[(to_h, to_w)]:
                d[(to_h, to_w)]=alt
                q.appendleft((alt,to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            alt=d[(fro_h, fro_w)]+1
            if alt<d[(to_h, to_w)]:
                d[(to_h, to_w)]=alt
                q.append((alt,to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
import numpy as np
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
stage = np.zeros((H,W),dtype=np.int32)
for h in range(H):
    S = input()
    for w,s in enumerate(S):
        if s=='#':
            stage[h,w] = -1
stage -= 1
H -= 1;W -= 1; CH -= 1; CW -= 1; DH -= 1; DW -= 1
from collections import deque
Q = deque([[CH,CW,0]])
while Q:
    qh,qw,qc = Q.popleft()
    for h in range(-2,3):
        for w in range(-2,3):
            # 移動なしは無視
            if h==0 and w == 0:
                pass
            # 場外判定
            elif qh+h < 0 or qh+h > H or qw + w < 0 or qw + w > W:
                pass
            # 普通の移動
            elif (h==0 and w==1) or (h==1 and w==0) or (h==0 and w==-1) or (h==-1 and w==0):
                # 未移動の場合 or 移動済の場合
                if stage[qh+h,qw+w] == -1 or stage[qh+h,qw+w] > qc:
                    stage[qh+h,qw+w] = qc
                    Q.append([qh+h,qw+w,qc])
            # ワープの移動
            else:
                if stage[qh+h,qw+w] == -1 or stage[qh+h,qw+w] > qc+1:
                    stage[qh+h,qw+w] = qc + 1
                    Q.append([qh+h,qw+w,qc+1])
print(stage[DH,DW])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit1=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
visit2=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

q=deque()
q.append((0,CH,CW))
visit1[(CH,CW)]=1
visit2[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    if fro_h==DH and fro_w==DW:
        print (kyori)
        quit()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit1[(to_h, to_w)]==0:
                    visit1[(to_h, to_w)]=1
                    q.appendleft((kyori,to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit2[(to_h, to_w)]==0:
                    visit2[(to_h, to_w)]=1
                    q.append((kyori+1, to_h, to_w))

print (-1)

Submission status: Runtime Error

Solution code:
from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[(i,j) for i in range(-2,3) for j in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        nexty,nextx=y+i,x+j
        for (i,j) in temp:
            if 0<=nexty<h and 0<=nextx<w and s[nexty][nextx]>=0:
                dist=s[nexty][nextx]
                if i*i+j*j<=1 and dist>s1:
                    s[nexty][nextx]=s1
                    que.append([nexty,nextx])
                elif dist>s1+1:
                    s[nexty][nextx]=s1+1
                    que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()

Submission status: Runtime Error

Solution code:
def main():
    h,w = map(int,input().split())
    sy,sx = map(int,input().split())
    gy,gx = map(int,input().split())
    S = []
    for _ in range(h):
        S.append(input())
    
    G = [[-1]*w for _ in range(h)]
    G_b = [[False]*w for _ in range(h)]
    v = [(1,0),(0,1),(-1,0),(0,-1)]
    ct = 0

    dq1 = deque([])
    dq1.append((sx-1,sy-1))
    G[sy-1][sx-1] = 0
    G_b[sy-1][sx-1] = True


    while dq1:

        g = set([])
        while dq1:
            x,y = dq1.popleft()
            g.add((x,y))
            for vx,vy in v:
                nx = x+vx
                ny = y+vy
                if nx>=0 and nx<w and ny>=0 and ny<h and (not G_b[ny][nx]) and S[ny][nx]==".":
                    G_b[ny][nx] = True
                    G[ny][nx] = ct
                    dq1.append((nx,ny))

        
        while g:
            x,y = g.pop()
            for i in range(-2,3):
                for j in range(-2,3):
                    if i!=0 or j!=0:
                        nx = x+i
                        ny = y+j
                        if nx>=0 and nx<w and ny>=0 and ny<h and (not G_b[ny][nx]) and S[ny][nx]==".":
                            dq1.append((nx,ny))
                            G_b[ny][nx] = True
                            G[ny][nx] = ct+1


        ct+=1
    
    print(G[gy-1][gx-1])
main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1

q=deque()
q.append((0,CH,CW))
visit[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    if fro_h==DH and fro_w==DW:
        print kyori
        quit()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                    visit[(to_h, to_w)]=1
                    q.appendleft((kyori,to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                    visit[(to_h, to_w)]=1
                    q.append((kyori+1, to_h, to_w))

print -1

Submission status: Runtime Error

Solution code:
from collections import deque

H,W = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

#input maze information
s = ["#"*(W+4)]
s.append("#"*(W+4))
for i in range(H):
    s.append("##"+input()+"##")
s.append("#"*(W+4))
s.append("#"*(W+4))

ans = [[-1]*(W+4) for _ in range(H+4)]
for i in range(H+4):
    for j in range(W+4):
        if s[i][j] == "#":
            ans[i][j] = -2 #壁があるところは−２と重みをつけておく

ch += 1
cw += 1
dh += 1
dw += 1
ans[ch][cw]=0

move = [[-1,0],[1,0],[0,1],[0,-1]]
magic = [
    [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
    [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
    [0,-2],[0,-1],[0,0],[0,1],[0,2],\
    [1,-2],[1,-1],[1,0],[1,1],[1,2],\
    [2,-2],[2,-1],[2,0],[2,1],[2,2]
    ]

list1=deque([ch,cw])
list2=deque([])

while len(list1)>0:
    x,y = list1.popleft()
    list2.append([x,y])
    for p,q in move:
        v1,v2 = x+p,y+q
        if ans[v1][v2] == -1:
            list1.append([v1,v2])
            ans[v1][v2] = ans[x][y]
    if len(list1)==0:
        while len(list2) > 0:
            x2,y2 = list2.popleft()
            for v1,v2 in magic:
                i,j = x2+v1,y2+v2
                if ans [i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    list1.append([i,j])
print(ans[dh][dw])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))

q=deque()
q.append((CH,CW))
visit[(CH,CW)]=1
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=d[(fro_h, fro_w)]+0
                q.appendleft((to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W:
            if S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
                visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
                q.appendleft((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
import math
from collections import deque

H,W = map(int, input().split())
ch,cw = map(int,input().split())
dh,dw = map(int, input().split())

#input maze information
s = ["#"*(W+4)]
s.append("#"*(W+4))
for i in range(H):
    s.append("##"+input()+"##")
s.append("#"*(W+4))
s.append("#"*(W+4))

ans = [[-1]*(W*4) for _ in range(H+4)]
for i in range(H+4):
    for j in range(W+4):
        if s[i][j] == "#":
            ans[i][j] = -2 #壁があるところは−２と重みをつけておく

ch += 1
cw += 1
dh += 1
dw += 1
ans[ch][cw]=0

move = [[-1,0],[1,0],[0,1],[0,-1]]
magic = [
    [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
    [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
    [0,-2],[0,-1],[0,0],[0,1],[0,2],\
    [1,-2],[1,-1],[1,0],[1,1],[1,2],\
    [2,-2],[2,-1],[2,0],[2,1],[2,2]
    ]

list1=deque([])
list2=deque([])
list1.append([ch,cw])

while len(list1)>0:
    x,y = list1.popleft()
    list2.append([x,y])
    for p,q in move:
        v1,v2 = x+p,y+q
        if ans[v1][v2] == -1:
            list1.append([v1,v2])
            ans[v1][v2] = ans[x][y]
    if len(list1)==0:
        while len(list2) > 0:
            x2,y2 = list2.popleft()
            for v1,v2 in magic:
                i,j = x2+v1,y2+v2
                if ans [i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    list1.append([i,j])
print(ans[dh][dw])

Submission status: Runtime Error

Solution code:
from collections import deque
import sys

INF = 10 ** 8

H, W = map(int,input().split())
CH, CW = map(int,input().split())
DH, DW = map(int,input().split())

S = []
for _ in range(H):
    S.append(list(input()))

d = [[INF for i in range(W)] for j in range(H)]

Q = deque([CH-1, CW-1, 0])
d[CH-1][CW-1] = 0

while len(Q) != 0:
    x, y, cnt = Q.popleft()
    
    if x == DH-1 and y == DW-1:
        print(cnt)
        sys.exit()
    
    for tx in range(-2, 3):
        for ty in range(-2, 3):
            nx = x + tx
            ny = y + ty
            if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] == INF:
                if abs(tx)+abs(ty) == 1:
                    d[nx][ny] = cnt
                    Q.appendleft([nx, ny, cnt])
                else:
                    d[nx][ny] = cnt + 1
                    Q.append([nx, ny, cnt + 1])

print(-1)

Submission status: Runtime Error

Solution code:
distance=[[10**10 for j in range(w)] for i in range(h)]

distance[ch][cw]=0


Q=deque()
Q.append((ch,cw))



while Q:
  p=Q.popleft()
  flag=False

  if p[0]==dh and p[1]==dw:
    break
  
  dx=[1,1,-1,-1]
  dy=[-1,1,-1,1]
  dddx=[0,0,2,-2,2,2,2,2,1,1,1,1,-2,-2,-2,-2,-1,-1,-1,-1]
  dddy=[2,-2,0,0,2,1,-1,-2,2,1,-1,-2,2,1,-1,-2,2,1,-1,-2]

  for i in range(4):
    nx=p[0]+dx[i]
    ny=p[1]+dy[i]

    if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and distance[p[0]][p[1]]<distance[nx][ny]:
      Q.appendleft((nx,ny))
      flag=True
      distance[nx][ny]=distance[p[0]][p[1]]

  if flag:
    continue

  for j in range(20):
    nnnx=p[0]+dddx[j]
    nnny=p[1]+dddy[j]

    if 0<=nnnx<h and 0<=nnny<w and maze[nnnx][nnny]!='#' and distance[p[0]][p[1]]<distance[nnnx][nnny]+1:
      Q.append((nnnx,nnny))
      distance[nnnx][nnny]=distance[p[0]][p[1]]+1


if distance[dh][dw]==10**10:
  print(-1)
  exit()


print(distance[dh][dw])