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:
def my_index(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

H,W,M=map(int,input().split())
P=list()
P_X=[0]*(H+1)
P_Y=[0]*(W+1)
for _ in range(M):
    P.append(list(map(int,input().split())))
for m in range(M):
    P_X[P[m][0]]+=1
    P_Y[P[m][1]]+=1
Max_X=max(P_X)
Max_Y=max(P_Y)
max_X=my_index(P_X,Max_X)
max_Y=my_index(P_Y,Max_Y)
m_count=0
for k in P:
    if  k[0] in max_X and k [1] in max_Y:
        m_count += 1
if m_count==len(max_X)*len(max_Y):
    answer=Max_X+Max_Y-1
else:
     answer=Max_X+Max_Y
    
print(answer)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

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

for i in range(H):
  l=list(input())
  for j in range(len(l)):
    if l[j]=='.':l[j]=-1
    if l[j]=='#':l[j]=-2
  maze.append(l)
def isIn(h,w):
  if h<0 or h>=H or w<0 or w >=W:return False
  return True
def update(maze,h,w,value,l):
  global update_list
  vectors=[[-1,0],[1,0],[0,1],[0,-1]]
  maze[h][w]=value
  update_list=l
  u=[]
  for i in range(25):
    if not isIn(h+i//5-2,w+i%5-2):continue
    if maze[h+i//5-2][w+i%5-2]>maze[h][w] or maze[h+i//5-2][w+i%5-2]==-1:
      if [h+i//5-2,w+i%5-2] not in u:
        u.append([h+i//5-2,w+i%5-2])
        maze[h+i//5-2][w+i%5-2]=value+1
  for vector in vectors:
    if not isIn(h+vector[0],w+vector[1]):continue
    if maze[h+vector[0]][w+vector[1]]>maze[h][w] or maze[h+vector[0]][w+vector[1]]==-1:
      maze[h+vector[0]][w+vector[1]]=maze[h][w]
      update(maze,h+vector[0],w+vector[1],value,l)
      
  for h,w in u:
    if maze[h][w]==value+1 and not [h,w] in update_list:
      update_list.append([h,w])
  return update_list

already=0
def calc(update_list,value):
  for h,w in update_list:
    if maze[h][w]!=-1 and maze[h][w]<value:continue
    u=update(maze,h,w,value,[])
    calc(u,value+1)

update_list=update(maze,Ch-1,Cw-1,0,[])
calc(update_list,1)
print(maze[Dh-1][Dw-1])

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
from numba import njit


mX = [0, 1, 0, -1]
mY = [1, 0, -1, 0]
zX = [2, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, -1, -1, -1, -1, -2, -2, -2, -2, -2]
zY = [2, 1, 0, -1, 2, 2, 1, -1, -2, 2, -2, 2, -2, 1, -1, 2, 1, 0, -1, 2]


@njit
def bfs(u, S, M, H, W):  # u 開始点

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()

        # 徒歩移動
        for i in range(4):
            nx, ny = u[0] + mX[i], u[1] + mY[i]

            if nx < 0 or H <= nx or ny < 0 or W <= ny or S[nx][ny] == "#":
                continue

            if M[nx][ny] == -1 or M[nx][ny] > M[u[0]][u[1]]:  # state を確認
                M[nx][ny] = M[u[0]][u[1]]  # 徒歩移動
                q.append([nx, ny])

        # 魔法移動
        for i in range(-2, 3):
            for j in range(-2, 3):
                wx = u[0] + i
                wy = u[1] + j
                if wx < 0 or H <= wx or wy < 0 or W <= wy or S[wx][wy] == "#":
                    continue
                if M[wx][wy] == -1 or M[wx][wy] > M[u[0]][u[1]] + 1:  # state を確認
                    M[wx][wy] = M[u[0]][u[1]] + 1
                    q.append([wx, wy])


def main():

    H, W = map(int, sys.stdin.readline().rstrip().split())
    Ch, Cw = map(int, sys.stdin.readline().rstrip().split())
    Dh, Dw = map(int, sys.stdin.readline().rstrip().split())

    S = []
    for i in range(H):
        S.append(sys.stdin.readline().rstrip())

    M = [[-1 for _ in range(W)] for _ in range(H)]

    if S[Ch - 1][Cw - 1] == "#":
        print(-1)
        return

    M[Ch - 1][Cw - 1] = 0
    bfs([Ch - 1, Cw - 1], S, M, H, W)

    print(M[Dh - 1][Dw - 1])


main()

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
x,y = Ch,Cw
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Cw-1][Ch-1] = 0
 
while (que or que_warp):
    while (que):
        for i in range(4):
            nx = int(que[0][1]+dx[i])
            ny = int(que[0][0]+dy[i])
            if (1<=nx<=W) and (1<=ny<=H):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((ny,nx))
                    que_warp.append((ny,nx))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][1] + ddx[i])
            ny = int(que_warp[0][0] + ddy[i])
            if (1 <= nx <= W) and (1 <= ny <= H):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((ny, nx))
        que_warp.pop(0)
 
print (res_S[Dw-1][Dh-1])

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
from numba import njit


mX = [0, 1, 0, -1]
mY = [1, 0, -1, 0]
zX = [2, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, -1, -1, -1, -1, -2, -2, -2, -2, -2]
zY = [2, 1, 0, -1, 2, 2, 1, -1, -2, 2, -2, 2, -2, 1, -1, 2, 1, 0, -1, 2]

@njit
def bfs(u, S, M, H, W):  # u 開始点

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()

        # 徒歩移動
        for i in range(4):
            nx, ny = u[0] + mX[i], u[1] + mY[i]

            if nx < 0 or H <= nx or ny < 0 or W <= ny or S[nx][ny] == "#":
                continue

            if M[nx][ny] == -1 or M[nx][ny] > M[u[0]][u[1]]:  # state を確認
                M[nx][ny] = M[u[0]][u[1]]  # 徒歩移動
                q.append([nx, ny])

        # 魔法移動
        for i in range(20):
            wx = u[0] + zX[i]
            wy = u[1] + zY[i]
            if wx < 0 or H <= wx or wy < 0 or W <= wy or S[wx][wy] == "#":
                continue
            if M[wx][wy] == -1 or M[wx][wy] > M[u[0]][u[1]] + 1:  # state を確認
                M[wx][wy] = M[u[0]][u[1]] + 1
                q.append([wx, wy])


def main():

    H, W = map(int, sys.stdin.readline().rstrip().split())
    Ch, Cw = map(int, sys.stdin.readline().rstrip().split())
    Dh, Dw = map(int, sys.stdin.readline().rstrip().split())

    S = []
    for i in range(H):
        S.append(sys.stdin.readline().rstrip())

    M = [[-1 for _ in range(W)] for _ in range(H)]

    if S[Ch - 1][Cw - 1] == "#":
        print(-1)
        return

    M[Ch - 1][Cw - 1] = 0
    bfs([Ch - 1, Cw - 1], S, M, H, W)

    print(M[Dh - 1][Dw - 1])


main()

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())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([ch-1, cw-1])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    for i in range(-1, 2):
        for j in range(-1, 2):
            if i != 0 and j != 0:
                if 0 <= x+i < h and 0 <= y < w:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x]
                        queue.appendleft((y+j, x+i))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < h and 0 <= y < w:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x] + 1
                        queue.appendleft((y+j, x+i))


if S[dh+1][dw+1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
from namba import njit


mX = [0, 1, 0, -1]
mY = [1, 0, -1, 0]
zX = [2, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, -1, -1, -1, -1, -2, -2, -2, -2, -2]
zY = [2, 1, 0, -1, 2, 2, 1, -1, -2, 2, -2, 2, -2, 1, -1, 2, 1, 0, -1, 2]

@njit
def bfs(u, S, M, H, W):  # u 開始点

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()

        # 徒歩移動
        for i in range(4):
            nx, ny = u[0] + mX[i], u[1] + mY[i]

            if nx < 0 or H <= nx or ny < 0 or W <= ny or S[nx][ny] == "#":
                continue

            if M[nx][ny] == -1 or M[nx][ny] > M[u[0]][u[1]]:  # state を確認
                M[nx][ny] = M[u[0]][u[1]]  # 徒歩移動
                q.append([nx, ny])

        # 魔法移動
        for i in range(20):
            wx = u[0] + zX[i]
            wy = u[1] + zY[i]
            if wx < 0 or H <= wx or wy < 0 or W <= wy or S[wx][wy] == "#":
                continue
            if M[wx][wy] == -1 or M[wx][wy] > M[u[0]][u[1]] + 1:  # state を確認
                M[wx][wy] = M[u[0]][u[1]] + 1
                q.append([wx, wy])


def main():

    H, W = map(int, sys.stdin.readline().rstrip().split())
    Ch, Cw = map(int, sys.stdin.readline().rstrip().split())
    Dh, Dw = map(int, sys.stdin.readline().rstrip().split())

    S = []
    for i in range(H):
        S.append(sys.stdin.readline().rstrip())

    M = [[-1 for _ in range(W)] for _ in range(H)]

    if S[Ch - 1][Cw - 1] == "#":
        print(-1)
        return

    M[Ch - 1][Cw - 1] = 0
    bfs([Ch - 1, Cw - 1], S, M, H, W)

    print(M[Dh - 1][Dw - 1])


main()

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(" "))

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1


Ss = [list(input()) for _ in range(H)]
Ss = np.array(Ss)

Ss_num = np.zeros(Ss.shape, dtype=int)
warp_counts = np.zeros(Ss.shape, dtype=int)
unvisiteds = np.zeros(Ss.shape, dtype=int)


for i in range(H):
    for j in range(W):
        Ss_num[i][j] = 1 if Ss[i][j] == "." else 0
        unvisiteds[i][j] = 1 if Ss[i][j] == "." else 0



from collections import deque
queue = deque()





queue.append((Ch, Cw))

def valid_pos(pos):
    return 0 <= pos[0] and pos[0] < H and\
        0 <= pos[1] and pos[1] < W

def pos_around(pos):
    return [
        (pos[0]-1, pos[1]),
        (pos[0],   pos[1]-1),
        (pos[0]+1, pos[1]),
        (pos[0],   pos[1]+1),
    ]

current_warp_count = 0
while True:
    
    edges = set()
    while len(queue) > 0:
        pos = queue.popleft()
        unvisiteds[pos] = 0
        warp_counts[pos] = current_warp_count

        if pos[0] == Dh and pos[1] == Dw:
            print(current_warp_count)
            exit(0)
        
        for new_pos in pos_around(pos):
            
            if valid_pos(new_pos)==False:
                continue
            
            if Ss_num[new_pos] == 1 and unvisiteds[new_pos]==1:
                queue.append(new_pos)
                unvisiteds[new_pos] = 0

            if Ss_num[new_pos] == 0:
                # print(new_pos, pos)
                edges.add(pos)

        
    # print(edges)
    warp_candidate = set()
    # search can go '.' with warp  
    for edge in edges:
        edge_h = edge[0]
        edge_w = edge[1]
        
        hmin=max(0,edge_h-2)
        hmax=min(H,edge_h+3)
        wmin=max(0,edge_w-2)
        wmax=min(W,edge_w+3)
        Ss_num_area = Ss_num[hmin:hmax,wmin:wmax]
        unvisited_area = unvisiteds[hmin:hmax,wmin:wmax]
        # print(edge)
        # print(Ss_num_area)
        # print(unvisited_area)
        mul =  Ss_num_area * unvisited_area
        

        if mul.sum().sum()>0:
            for i in range(mul.shape[0]):
                for j in range(mul.shape[1]):
                    if mul[i][j] == 1:
                        warp_candidate.add((i,j))

        
    if len(warp_candidate) == 0:
        print(-1)
        exit(0)
    
    for candidate in warp_candidate:
        queue.append(candidate)

    current_warp_count += 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())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([ch-1, cw-1])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    for i in range(-1, 2):
        for j in range(-1, 2):
            if i != 0 and j != 0:
                if 0 <= x+i < h and 0 <= y < w:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x]
                        queue.appendleft((y+j, x+i))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < h and 0 <= y < w:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == "."::
                        S[y+j][x+i] = S[y][x] + 1
                        queue.appendleft((y+j, x+i))


if S[dh+1][dw+1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
def myfunc(h, w, c):
    if 0<=h and h<H+2 and 0<=w and w<W+2 and T[h][w] != '#':
        if T[h][w] == '.' or T[h][w] > c:
            T[h][w] = c
            for i in [(0,1), (0,-1), (1,0), (-1,0)]:
                myfunc(h+i[0], w+i[1], c)
            for k in range(-2, 3):
                for l in range(-2, 3):
                    myfunc(h+k, w+l, T[h][w]+1)

H, W= map(int, input().split())
CH, CW= map(int, input().split())
DH, DW= map(int, input().split())
S = ['#'+input()+'#' for _ in range(H)]
S.insert(0,'#'*(W*2))
S.append('#'*(W*2))
T = [[0] * (W+2) for _ in range(H+2)]
for i in range(H+2):
    for j in range(W+2):
        T[i][j] = S[i][j]
myfunc(CH, CW, 0)
if T[DH][DW] == '#' or T[DH][DW] == '.':
    print(-1)
else:
    print(T[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 = CH -1
CW = CW -1
DH = DH -1
DW = DW -1
S = np.array([list(input()) for i in range(H)])
countWarp = np.ones((H,W))*H*W
nowH = CH
nowW = CW
countWarp[CH,CW] = 0
q = deque([])
q.append([nowH,nowW])
for n in range(0,H*W/2):
  tmp = q.popleft()
  nowH = tmp[0]
  nowW = tmp[1]
  for i in range(-2,2+1):
    for j in range(-2,2+1):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if abs(i) + abs(j) == 1:
          if S[nowH+i,nowW+j] == '.':
            if countWarp[nowH+i,nowW+j] == H*W:
              q.append([nowH+i,nowW+j])
            countWarp[nowH+i,nowW+j] = min(countWarp[nowH,nowW],countWarp[nowH+i,nowW+j])
        if abs(i) + abs(j) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if countWarp[nowH+i,nowW+j] == H*W:
              q.append([nowH+i,nowW+j])
            countWarp[nowH+i,nowW+j] = min(countWarp[nowH,nowW]+1,countWarp[nowH+i,nowW+j])
  if len(q) == 0:
    break
if countWarp[DH,DW] == H*W:
  print(-1)
else:
  print(int(countWarp[DH,DW]))

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())
s=[]
ch-=1
cw-=1
dh-=1
dw-=1

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

d=[[10**10 for i in range(w)] for j in range(h)]
d=list(d)
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[-2,-2,-2,-2,-2,-1,-1,-1,-1, 0,0, 1, 1,1,1, 2, 2,2,2,2]
ddy=[-2,-1, 0, 1, 2,-2,-1, 1, 2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
ans=[]
d[ch][cw]=1
que=deque([ch,cw])
while que:
    p=que.popleft()
    for i in range(3):
        if i<=3:
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]           
            if nx>=0 and ny>=0 and nx<h and ny<w and s[ny][nx]!="#" and d[ny][nx]>d[p[1]][p[0]]:
                d[ny][nx]=d[p[1]][p[0]]
                que.append([ny,nx])
    for i in range(19):
        nx=p[0]+ddx[i]
        ny=p[1]+ddy[i]
        if nx>=0 and ny>=0 and nx<h and ny<w and s[ny][nx]!="#" and d[ny][nx]>d[p[0]][p[1]]+1:
            d[ny][nx]=d[p[1]][p[0]]+1
            que.append([ny,nx])

if d[dh][dw]==10**10:
    print(-1)
else:
    print(d[dh][dw])

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw =map(int,input().split())
s = [input() for i in range (h)]
dp = [[float('inf') for i in range (w)] for i in range (w)]
ch -=1
cw -=1
dw -=1
dh -=1
dp[ch][cw] = 0

def warp(H,W):
    cnt = 0
    for i in range (-1,2):
        for j in range (-1,2):
            if not abs(i) == abs(j) == 1:
                if not abs(i) == abs(j) == 0:
                    try:
                        if s[H+i][W+j] == '.':
                            if dp[H+i][W+j] == float('inf'):
                                dp[H+i][W+j] = warp(H+i,W+j)
                            dp[H][W] = min(dp[H+i][W+j],dp[H,W])
                    except IndexError:
                        cnt += 0
    for i in range(-2,3):
        for j in range (-2,3):
            if abs(i) + abs(j) >= 2:
                try:
                    if s[H+i][W+j] == '.':
                        if dp[H+i][W+j] == float('inf'):
                            dp[H+i][W+j] = warp(H+i,W+j)
                        dp[H][W] = min(dp[H+i][W+j]+1,dp[H,W])
                except IndexError:
                    cnt += 0
    return dp[H][W]
ans = warp(dh,dw)
print(ans)

Submission status: Runtime Error

Solution code:
def myfunc(h, w, c):
    if 0<=h and h<H+2 and 0<=w and w<W+2 and T[h][w] != '#':
        if T[h][w] == '.' or T[h][w] > c:
            T[h][w] = c
            for i in [(0,1), (0,-1), (1,0), (-1,0)]:
                myfunc(h+i[0], w+i[1], c)
            for k in range(-2, 3):
                for l in range(-2, 3):
                    myfunc(h+k, w+l, T[h][w]+1)

H, W= map(int, input().split())
CH, CW= map(int, input().split())
DH, DW= map(int, input().split())
S = ['#'+input()+'#' for _ in range(H)]
S.insert(0,'#'*(W*2))
S.append('#'*(W*2))
T = [[0] * (W+2) for _ in range(H+2)]
for i in range(H+2):
    for j in range(W+2):
        T[i][j] = S[i][j]
myfunc(CH, CW, 0)
if T[DH][DW] == '#' or T[DH][DW] == '.':
    print(-1)
else:
    print(T[DH][DW])

Submission status: Runtime Error

Solution code:
import copy
import math
import time
import statistics
import math
import itertools
import bisect
import sys
from decimal import *
from collections import deque


def get_int():
    return int(input())

def get_string():
    return input()

def get_int_list():
    return [int(x) for x in input().split()]

def get_string_list():
    return input().split()

def get_int_multi():
    return map(int, input().split())

def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# a_list = [0] * a
sys.setrecursionlimit(10 ** 6)

def main():
    start = time.time()

    h, w = get_int_list()
    sr, sc = get_int_list()
    er, ec = get_int_list()

    d = [[-1] * (w+2) for _ in range(h+2)]

    for i in range(h):
        wk = get_string()
        for ii in range(w):
            if wk[ii] == ".":
                d[i+1][ii+1] = 10 ** 6

    d[sr][sc] = 0
    q = deque([])
    q2= deque([])
    q.append([sr,sc])

    def idou(i,ii,cnt_mahou, flg_mahou):
        if d[i][ii] == 10 ** 6:
            q.append([i, ii])
            d[i][ii] = cnt_mahou

            if not flg_mahou:
                q2.appned([i, ii])

    ans = -1
    flg = True
    finish = False
    while flg:
        flg = False
        while q:
            wk = q.popleft()
            i = wk[0]
            ii = wk[1]
            cnt_mahou = d[i][ii]

            idou(i - 1, ii, cnt_mahou, False)
            idou(i + 1, ii, cnt_mahou, False)
            idou(i, ii - 1, cnt_mahou, False)
            idou(i, ii + 1, cnt_mahou, False)

            if d[er][ec] != 10 ** 6:
                ans = d[er][ec]
                finish = True
                break

        if finish:
            break

        while q2:
            wk = q.popleft()
            i = wk[0]
            ii = wk[1]
            # 魔法を使う
            for wk in range(-2, 3):
                for wk2 in range(-2, 3):
                    if abs(wk) + abs(wk2) > 1:
                        flg = True
                        idou(i + wk, ii + wk2, cnt_mahou + 1, True)

    print(ans)

    #print(time.time() - start)


if __name__ == '__main__':
    main()

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())
s=[]
ch-=1
cw-=1
dh-=1
dw-=1

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

d=[[10**10 for i in range(w)] for j in range(h)]
d=list(d)
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[-2,-2,-2,-2,-2,-1,-1,-1,-1, 0,0, 1, 1,1,1, 2, 2,2,2,2]
ddy=[-2,-1, 0, 1, 2,-2,-1, 1, 2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
ans=[]
d[ch][cw]=1
que=deque([ch,cw])
while que:
    p=que.popleft()
    for i in range(3):
        if i<=3:
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]           
            if nx>=0 and ny>=0 and nx<h and ny<w and s[nx][ny]!="#" and d[nx][ny]>d[p[0]][p[1]]:
                d[nx][ny]=d[p[0]][p[1]]
                que.append([nx,ny])
    for i in range(19):
        nx=p[0]+ddx[i]
        ny=p[1]+ddy[i]
        if nx>=0 and ny>=0 and nx<h and ny<w and s[nx][ny]!="#" and d[nx][ny]>d[p[0]][p[1]]+1:
            d[nx][ny]=d[p[0]][p[1]]+1
            que.append([nx,ny])

if d[dh][dw]==10**10:
    print(-1)
else:
    print(d[dh][dw])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    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
    s2 = [list(input()) for i in range(h)]
    s2[Ch][Cw] = 0
    d = deque()
    d.append([Ch, Cw])
    while d:
        nowh, noww = d.popleft()
        for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                if s2[nowh+i][noww+j] == '.':
                    s2[nowh+i][noww+j] = s2[nowh][noww]
                    d.appendleft([nowh+i, nowh+j])
                elif s2[nowh+i][noww+j] != '#':
                    if s2[nowh+i][noww+j] > s2[nowh][noww]:
                        s2[nowh+i][noww+j] = s2[nowh][noww]
                        d.append([nowh+i, noww+j])
        for i in [-2,-1,0,1,2]:
            for j in [-2,-1,0,1,2]:
                if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                    if s2[nowh+i][noww+j] == '.':
                        s2[nowh+i][noww+j] = s2[nowh][noww]+1
                        d.append([nowh+i, noww+j])
                    elif s2[nowh+i][noww+j] != '#':
                        if s2[nowh+i][noww+j] > s2[nowh][noww]+1:
                            s2[nowh+i][noww+j] = s2[nowh][noww]+1
                            d.append([nowh+i, noww+j])

    if s2[Dh][Dw] == '.':
        print(-1)
    else:
        print(s2[Dh][Dw])


if __name__ == '__main__':
    main()

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())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]
count=0
#niko(x,y,ans[y][x]+1)とする。
def niko(x,y,k,ans):
  for i in range(x-2,x+2):
    for j in range(y-2,y+2):
      if 0<=i<w and 0<=j<h:
        if maze[j][i]=="." and (ans[j][i]>k or ans[j][i]==-1):
          ans[j][i]=k
  return ans
ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]

    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if 0<=i<w and 0<=j<h:
          if (x==i and y==j+1) or (x==i+1 and y==j) or (x==i-1 and y==j) or (x==i and y==j-1) or (x==i and y==j):
            if maze[j][i]=="." and (ans[j][i]>ans[y][x] or ans[j][i]==-1):
              qu.append([x+dx[i],y+dy[i]])
              ans[y+dy[i]][x+dx[i]] = ans[y][x]
          elif maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
            ans[j][i]=(ans[y][x]+1)
            qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
#for i in ans:
#  print(*i)

Submission status: Runtime Error

Solution code:
from collections import deque

#スタート位置、ゴール位置の指定がある場合
def bfs(sy,sx,group_num):
    #移動距離　最小値に更新していく

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

    que.append((sy, sx))
    maze[sy][sx] = group_num

    while que:
        p = que.popleft()

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

            if 0<=nx<C and 0<=ny<R and maze[ny][nx] == ".":
                #全周を超えない　&　壁でない　&　未探索である
                que.append((ny, nx))
                maze[ny][nx] = group_num
                group[group_num].append([ny,nx])


R, C = map(int,input().split())
cy, cx = map(int,input().split())
dy, dx = map(int,input().split())
cy-=1
cx-=1
dy-=1
dx-=1

maze = [list(input()) for _ in range(R)]
group = []
group_num = 0

c_group = 0
d_group = 0

for i in range(R):
    for j in range(C):
        if maze[i][j] == ".":
            group.append([[i,j]])
            que = deque([])
            bfs(i,j,group_num)

            if i==cy and j == cx:
                c_group = group_num
            if i==dy and j == dx:
                d_group = group_num

            group_num += 1

worp_point = [set()]*group_num

def worp(y,x,num):
    for i in range(max(0,y-4),min(R-1,y+4)):
        for j in range(max(0,x-4),min(C-1,x+4)):
            a1 = maze[i][j]
            if a1 != "#" and a1!=num:
                worp_point[num].add(a1)

for i in range(group_num):
    for j in range(len(group[i])):
        worp(group[i][j][0],group[i][j][1],i)

ans = float("inf")
worp_cnt = [float("inf")]*group_num
cnt = 0

deque = deque(worp_point[c_group])

def bfs2(num,cnt):
    s = worp_point[num]
    while s:
        a2 = s.pop()
        worp_cnt[a2] = min(worp_cnt[a2],cnt+1)
        bfs2(a2,cnt+1)

bfs2(c_group,0)

if worp_cnt[d_group] != float("inf"):
    print(worp_cnt[d_group])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
e = 10**-9

for i in range(3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(e)
data = []
rs = []
cs = []
for pu in range(n):
    ux,uy = divmod(pu,w)
    if ss[ux][uy]=="#":
        continue
    for xx,yy,vv in zip(dx,dy,vvs):
        x,y = ux+xx, uy+yy
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
        u = x*w + y
        data.append(vv)
        rs.append(pu)
        cs.append(u)
assert False
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(n, n))
ans = scipy.sparse.csgraph.dijkstra(m, indices=start, directed=False) # startからの最短路木を求める
if ans[goal]>10**9:
    print(-1)
else:
    print(int(ans[goal]))

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = list(map(int, input().split()))
Sh, Sw = list(map(int, input().split()))
Dh, Dw = list(map(int, input().split()))
S = [list(str(input().split()))[2:-2] for _ in range(H)]
D = [[0] * 5 for _ in range(H)]
wall, road = ['#', '.']
def is_Road_judgement(now, dir_, over_wall_list): # 壁判定処理
    if not (0 <= now[0] + dir_[0] < H and 0 <= now[1] + dir_[1] < W): # up
        return False
    if S[now[0] + dir_[0]][now[1] + dir_[1]] == road:
        return True
    
    # ワープできる場所があるならリストにスタックしておく
    over_vec = [dir_[0] * 2, dir_[1] * 2]
    is_left_to_right = True # 横に動くか縦に動くか
    if over_vec[0] == 0:
        is_left_to_right = False
    for i in range(-1, 1):
        if is_left_to_right:
            if now[0] + over_vec[0] < 0 and 0 <= now[1] + i < W and\
            S[now[0] + over_vec[0]][now[1] + i] == road:
                over_wall_list.append((now[0] + over_vec[0], now[1] + i))
        else:
            if now[0] + i < 0 and 0 <= now[1] + over_vec[1] < W and\
            S[now[0] + i][now[1] + over_vec[1]] == road:
                over_wall_list.append((now[0] + i, now[1] + over_vec[1]))
    return False

# 0: 未訪問 1:訪問予定 2: 訪問後
is_Goal = False
now_h, now_w = [Sh - 1, Sw - 1]
goal_h, goal_w = [Dh - 1, Dw - 1]
D[now_h][now_w] = 1
q = deque()
q.append((now_h, now_w))
while len(q):
    now = q.pop()
    over_wall_list = []
    # 上下左右に移動できるか調べる
    dir_all = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for dir_ in dir_all:
        if is_Road_judgement(now, dir_, over_wall_list):
            D[now[0] + dir_[0]][now[1] + dir_[1]] = 1
            q.append((now[0] + dir_[0], now[1] + dir_[1]))

    # ワープ先もあるなら訪問予定に入れる
    for warp_p in over_wall_list:
        D[warp_p[0]][warp_p[1]] = 1
        q.append((warp_p[0], warp_p[1]))
    D[now_h][now_w] = 2
    
    # ゴール判定
    if now[0] == goal_h and now[1] == goal_w:
        is_Goal = True
        break
print('Yes') if is_Goal else print('No')