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
input =  sts.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
from collections import deque

grid =  ''
grid +=  '#' * (W+4) * 2
for h in range(H):
  S = str(input())
  grid += '#' * 2 + S + '#' * 2
grid +=  '#' * (W+4) * 2

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

Ch, Cw, Dh, Dw = Ch+1, Cw+1, Dh+1, Dw+1
usedss = [[0] * (W + 4) for _ in  range(H+4)]
      
for x in range(H+4):
  for y in range(W+4):
    if grid[x*(W+4)+y] == '#':
      usedss[x][y] = 1
      
VS = set([(Ch, Cw)])
new_VS = set([(Ch, Cw)])
usedss[Ch][Cw] = 1
      
ans = 0
while True:
  while VS:
      VS2  = set()
      for x, y in VS:
        for dx, dy in D:
          x_ = x + dx
          y_ = y + dy
          if usedss[x_][y_] == 1:
            continue
          VS2.add((x_,y_))
          new_VS.add((x_, y_))
          usedss[x_][y_] = 1
      VS = VS2
      #print(VS)
      
  if usedss[Dh][Dw]:
    print(ans)
    break
    
  if not new_VS:
    print(-1)
    break
    
  VS = set()
  for x, y in new_VS:
    for dx in range(-2, 3):
      for dy in range(-2, 3):
        x_ = x + dx
        y_ = y + dy
        if usedss[x_][y_]  == 1:
          continue
        VS.add((x_, y_))
        usedss[x_][y_] = 1
        
  ans += 1
  new_VS = set(VS)

Submission status: Runtime Error

Solution code:
from collections import deque

def is_okay(x, y, H, W):
    if x>=0 and x<=W-1:
        if y>=0 and y <=H-1:
            return True
        else:
            return False
    else:
        return False

def main():
    H, W = list(map(int, input().split()))
    Ch, Cw = list(map(int, input().split()))
    Dh, Dw = list(map(int, input().split()))
    S = []
    for i in range(H):
        S.append(list(input()))

    visited = [[False for _ in range(H)] for _ in range(W)]

    queue_global = deque([[Ch-1, Cw-1]])
    queue_local = deque()
    goal = [Dh-1, Dw-1]

    ans = 0

    while len(queue_global) > 0:
        while len(queue_global) > 0:
            queue_local.append(queue_global.popleft())
        new_visit = []
        while len(queue_local) > 0:
            x, y = queue_local.popleft()
            new_visit.append([x, y])
            visited[x][y] = True
            if [x, y] == goal:
                print(ans)
                exit()
            else:
                if x+1 < W-1 and visited[x+1][y] == False:
                    if S[y][x+1] == ".":
                        queue_local.append([x+1, y])
                if x > 0 and visited[x-1][y] == False:
                    if S[y][x-1] == ".":
                        queue_local.append([x-1, y])
                if y+1 < H-1 and visited[x][y+1] == False:
                    if S[y+1][x] == ".":
                        queue_local.append([x, y+1])
                if y > 0 and visited[x][y-1] == False:
                    if S[y-1][x] == ".":
                        queue_local.append([x, y-1])

        ans += 1
        for x,y in new_visit:
            candidates = []
            for i in range(-2,3):
		for j in range(-2,3):
                    candidates.append([x+i, y+j])
            for item in candidates:
                x_new = item[0]
                y_new = item[1]
                if is_okay(x_new, y_new, H, W):
                    if S[y_new][x_new] == ".":
                        if visited[x_new][y_new] == False:
                            queue_global.append([x_new, y_new])

    print("-1")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque
 
H, W = [int(x) for x in stdin.readline().rstrip().split()]
Si, Sj = [int(x) for x in stdin.readline().rstrip().split()]
Gi, Gj = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split() for _ in range(H)]
 
check = [[float('inf') for i in range(W)] for j in range(H)]
walk = [(0,-1), (0,1), (-1,0), (1,0)]
qu = deque([(Si-1, Sj-1, 0)])
qu_1 = deque()
check[Si-1][Sj-1] = 0
 
while qu:
    i, j, cost = qu.popleft()
    qu_1.append((i, j, cost))
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        if 0 <= i+di < H and 0 <= j+dj < W:
            if not maze[i+di][0][j+dj] == '#':
                if check[i+di][j+dj] > cost:
                    check[i+di][j+dj] = cost
                    qu.appendleft((i+di, j+dj, cost))
 
    if len(qu) == 0:
        #ワープで行けるところ
        while qu_1:
            i, j, cost = qu_1.popleft()
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if 0 <= i+di < H and 0 <= j+dj < W:
                        if not maze[i+di][0][j+dj] == '#':
                            if check[i+di][j+dj] > cost + 1:
                                check[i+di][j+dj] = cost + 1
                                qu.append((i+di, j+dj, cost+1))
 
#print(check)
if check[Gi-1][Gj-1] == float('inf'):
    print(-1)
else:
    print(check[Gi-1][Gj-1])
 
     
 
 
 
 
from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
Si, Sj = [int(x) for x in stdin.readline().rstrip().split()]
Gi, Gj = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split() for _ in range(H)]

check = [[float('inf') for i in range(W)] for j in range(H)]
walk = [(0,-1), (0,1), (-1,0), (1,0)]
qu = deque([(Si-1, Sj-1, 0)])
qu_1 = deque()
check[Si-1][Sj-1] = 0

while qu:
    i, j, cost = qu.popleft()
    qu_1.append((i, j, cost))
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        if 0 <= i+di < H and 0 <= j+dj < W:
            if not maze[i+di][0][j+dj] == '#':
                if check[i+di][j+dj] > cost:
                    check[i+di][j+dj] = cost
                    qu.appendleft((i+di, j+dj, cost))

    if len(qu) == 0:
        #ワープで行けるところ
        while qu_1:
            i, j, cost = qu_1.popleft()
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if 0 <= i+di < H and 0 <= j+dj < W:
                        if not maze[i+di][0][j+dj] == '#':
                            if check[i+di][j+dj] > cost + 1:
                                check[i+di][j+dj] = cost + 1
                                qu.append((i+di, j+dj, cost+1))

#print(check)
if check[Gi-1][Gj-1] == float('inf'):
    print(-1)
else:
    print(check[Gi-1][Gj-1])

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
f = [[s=="." for s in input()] for _ in range(H)]

visit = [[-1 for w in range(W)] for h in range(H)]

ch, cw = ch - 1, cw - 1
dh, dw = dh - 1, dw - 1

Q = deque([ch*1000 + cw])
visit[ch][cw] = 0

while len(Q)>0:
  hw = Q.popleft()
  h = hw // 1000
  w = hw % 1000
  for dy in range(-min(2,h), min(3, H-1-h)):
    for dx in range(-min(2,w), min(3, W-1-w)):
      if dx==0 and dy==0:
        continue
      nh = h + dy
      nw = w + dx
      if (dx==0 and abs(dy)==1) or (dy==0 and abs(dx)==1):
        if f[nh][nw]:
          if visit[nh][nw] == -1:
            visit[nh][nw] = visit[h][w]
            Q.appendleft(nh*1000+nw)
          elif visit[nh][nw] > visit[h][w]:
            visit[nh][nw] = visit[h][w]
      else:
        if f[nh][nw]:
          if visit[nh][nw] == -1:
            visit[nh][nw] = visit[h][w] + 1
            Q.append(nh*1000+nw)

print(visit[dh][dw])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

#def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h or 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
#                wpg.append((i,j))
                wpg2[i][j]=1

  for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
#wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Submission status: Runtime Error

Solution code:

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
#wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=h:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
                wpg.append((i,j))
#                wpg2[i][j]=1
                
#for i in range(h):
#    for j in range(w):
#        if wpg2[i][j]==1:
#            wpg.append((i,j))
                
wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=h:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
#                wpg.append((i,j))
                wpg2[i][j]=1
                
for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
#wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Submission status: Runtime Error

Solution code:

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[[0] for i in range(w)] for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        ww=[]
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=h:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
#                wpg.append((i,j))
                wpg2[i][j]=1
                
for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
#wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Submission status: Runtime Error

Solution code:

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg=[]
for i in range(h):
    j=0
    for ii,jj in ij:
        if 0>i+ii or i+ii>=h:
            continue
        if 0>jj:
            continue
        if s[i+ii][j+jj]==".":
            g[i][j].append((i+ii,j+jj))        
        else:
            wpg.append((i,j))        
    for j in range(1,w-1):
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
                wpg.append((i,j))        
    j=w-1
    for ii,jj in ij:
        if 0>i+ii or i+ii>=h:
            continue
        if jj>=1:
            continue
        if s[i+ii][j+jj]==".":
            g[i][j].append((i+ii,j+jj))        
        else:
            wpg.append((i,j))        

wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Submission status: Runtime Error

Solution code:
from numba import njit
from collections import deque
import sys
from sys import stdin
readline = sys.stdin.buffer.readlines

@njit
def num(h, w, c0, c1, d0, d1, s):
    q = deque()
    q1 = deque()
    q.append([c0-1, c1-1, 0])
    
    ans = float('inf')
    
    while q:
        a0, a1, a2 = q.popleft()
        q1.append([a0, a1, a2])
        s[a0][a1] = '#'
        if a0 == d0-1 and a1 == d1-1:
            ans = a2
            break

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x, y = a0+i, a1+j
            if not(0 <= x < h):
                continue
            elif not(0 <= y < w):
                continue
            elif not(ans > a2):
                continue
            elif s[x][y] == '.':
                q.appendleft([x, y, a2])
        if len(q) == 0:
            while q1:
                a0, a1, a2 = q1.popleft()
                for i in range(-2, 3):
                    for j in range(-2, 3):
                        x, y = a0+i, a1+j
                        if not(0 <= x < h):
                            continue
                        elif not(0 <= y < w):
                            continue
                        elif not(ans > a2+1):
                            continue
                        elif s[x][y] == '.':
                            q.append([x, y, a2+1])
    
    if ans == float('inf'):
        ans = -1
    print(ans)

if __name__ == "__main__":
    h, w = map(int, readline().split())
    c0, c1 = map(int, readline().split())
    d0, d1 = map(int, readline().split())
    s = np.array([list(stdin.readline()[:-1]) for _ in range(h)])
    num(h, w, c0, c1, d0, d1, s)

Submission status: Runtime Error

Solution code:
import queue

def main():
    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 = []
    for i in range(2):
        maze.append(['#' for j in range(4+w)])
    for i in range(h):
        maze.append(['#' for j in range(2)]+list(input())+ ['#' for j in range(2)])
    for i in range(2):
        maze.append(['#' for j in range(4+w)])

    # for i in range(len(maze)):
    #     print(''.join(maze[i]))

    maze_separate = [[0 for i in range(len(maze[0]))] for j in range(len(maze))]
    number = 1
    for i in range(len(maze_separate)):
        for j in range(len(maze_separate[i])):
            if maze[i][j]=='.' and maze_separate[i][j]==0:
                maze_separate[i][j] = number
                number += 1
                q = queue.Queue()
                q.put([i,j])
                while not q.empty():
                    x,y = q.get()
                    for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
                        if maze[x+dx][y+dy] == '.' and maze_separate[x+dx][y+dy]==0:
                            maze_separate[x+dx][y+dy] = maze_separate[x][y]
                            q.put([x+dx,y+dy])

    # for i in range(len(maze_separate)):
    #     print(maze_separate[i])

    have_been = [False for i in range(number)+3]
    have_been[0] = True
    have_been[maze_separate[Ch][Cw]] = True

    maze[Ch][Cw] = '#'
    q = queue.Queue()
    q.put([Ch,Cw,0])
    while not q.empty():
        x,y,cnt = q.get()
        # print(x,y,cnt)
        if x==Dh and y == Dw:
            print(cnt)
            return 
        else:
            for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
                if maze[x+dx][y+dy] == '.':
                   maze[x+dx][y+dy] = '#'
                   q.put([x+dx,y+dy,cnt]) 
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if maze[x+dx][y+dy] == '.' and maze_separate[x+dx][y+dy] != maze_separate[x][y] and have_been[maze_separate[x+dx][y+dy]] == False:
                        have_been[maze_separate[x+dx][y+dy]] = True
                        maze[x+dx][y+dy] = '#'
                        q.put([x+dx,y+dy,cnt+1]) 
    print(-1)
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#import numpy as np
from collections import deque

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

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

INF = 10 ** 12

#score = np.zeros((H, W), dtype=int)
#score[:, :] = INF
score = [[INF] * W for _ in range(W)]

score[Ch][Cw] = 0

candidates = deque()
candidates.append((Ch, Cw))

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 candidates:
    h, w = candidates.popleft()
    # move
    for dh, dw in walk:
        y = h + dh
        x = w + dw
        s = score[h][w]
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue        
        if maze[y][x] == '.' and score[y][x] > s:
            score[y][x] = s
            candidates.appendleft((y, x))
    # warp
    for dh, dw in warp:
        y = h + dh
        x = w + dw
        s = score[h][w]
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue
        if maze[y][x] == '.' and score[y][x] > s + 1:
            score[y][x] = s + 1
            candidates.append((y, x))

if score[Dh][Dw] == INF:
    print(-1)
else:
    print (score[Dh][Dw])

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque

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

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

INF = 10 ** 12

score = np.zeros((H, W), dtype=int)
score[:, :] = INF
score[Ch, Cw] = 0

candidates = deque()
candidates.append((Ch, Cw))

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 candidates:
    h, w = candidates.popleft()
    # move
    for dh, dw in walk:
        y = h + dh
        x = w + dw
        s = score[h, w]
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue        
        if maze[y][x] == '.' and score[y, x] > s:
            score[y, x] = s
            candidates.appendleft((y, x))
    # warp
    for dh, dw in warp:
        y = h + dh
        x = w + dw
        s = score[h, w]
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue
        if maze[y][x] == '.' and score[y, x] > s + 1:
            score[y, x] = s + 1
            candidates.append((y, x))

if score[Dh, Dw] == INF:
    print(-1)
else:
    print (score[Dh, Dw])

Submission status: Runtime Error

Solution code:
from collections import deque
import sys

imput = sys.stdin.readline

h,w = map(int,input().split())
sy,sx= map(int,input().split())
gy,gx= map(int,input().split())
S=[]



for i in range(h):
    S.append(input())

walk = [[1,0],[-1,0],[0,1],[0,-1]]
move = [[x,y] for x in range(-2,3) for y in range(-2,3) if [x,y] not in walk + [[0,0]]] 

dist = [[99999]*w for i in range(h)]
#visited = [[0]*w for i in range(h)]

q=deque()
q.append((sx-1,sy-1,0))
dist[sy-1][sx-1]=0
goaled = 0
endwarp=0
#while goaled==0:
while len(q):
    endwarp=0
    
    x,y,d = q.popleft()
    
#    if x==gx-1 and y==gy-1:
#        goaled=1
#        print(d)
#        break
    
#    print(x,y,d)
    for i in walk:
        if 0<=x+i[0]<w and 0<=y+i[1]<h and S[y+i[1]][x+i[0]]!="#" and if dist[y+i[1]][x+i[0]] > d:

                    dist[y+i[1]][x+i[0]] = d
                    q.appendleft((x+i[0],y+i[1],d+0))

    for i in move:
        if 0<=x+i[0]<w and 0<=y+i[1]<h and S[y+i[1]][x+i[0]]!="#" and if dist[y+i[1]][x+i[0]] > d+1:

                    dist[y+i[1]][x+i[0]] = d
                    q.append((x+i[0],y+i[1],d+1))
                        
                        
                         
    
    

if dist[gy-1][gx-1]==99999:
    print(-1)
    
else:
    print(dist[gy-1][gx-1])

Submission status: Runtime Error

Solution code:
#ABC176
#D - Wizard in Maze
import numpy as np
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)
x=0

for i in range(h):
  a.append(list(input()))

warp=0

while len(c)>0:
  ch,cw=c[0]
  c.pop(0)
  if ch==dh-1 and cw==dw-1:
    print(warp)
    x=1
    c=[]
  else:
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
      
    e=[[ch-1,cw],[ch+1,cw],[ch,cw-1],[ch,cw+1]]
    for i in e:
      ch1,cw1=i
      if i not in d and 0<=ch1<h and 0<=cw1<w:
        if a[ch1][cw1]!="#":
          c.append(i)
          d.append(i)
    if len(c)==0:
      warp=warp+1
      for i in range(5):
        ch0=ch-2+i
        for j in range(5):
          cw0=cw-2+j
          f.append([ch0,cw0])
      for i in f:
        ch1,cw1=i
        if i not in d and 0<=ch1<h and 0<=cw1<w:
          if a[ch1][cw1]!="#":
            c.append(i)
            d.append(i)
            
if x!=1:
  print(-1)

Submission status: Runtime Error

Solution code:
#ABC176
#D - Wizard in Maze
import numpy as np
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)
x,y=0,0

for i in range(h):
  a.append(list(input()))

warp=0

while len(c)>0:
  ch,cw=c[0]
  c.pop(0)
  if ch==dh-1 and cw==dw-1:
    print(warp)
    x=1
    c=[]
  else:
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
      
    e=[[ch-1,cw],[ch+1,cw],[ch,cw-1],[ch,cw+1]]
    for i in e:
      ch1,cw1=i
      if i not in d and 0<=ch1<h and 0<=cw1<w:
        if a[ch1][cw1]!="#":
          c.append(i)
          d.append(i)
    if len(c)==0:
      warp=warp+1
      for i in range(5):
        ch0=ch-2+i
        for j in range(5):
          cw0=cw-2+j
          f.append([ch0,cw0])
      for i in f:
        ch1,cw1=i
        if i not in d and 0<=ch1<h and 0<=cw1<w:
          if a[ch1][cw1]!="#":
            c.append(i)
            d.append(i)
            
if x!=1:
  print(-1)