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: Wrong Answer

Solution code:
from collections import deque
H, W = [int(a) for a in input().split()]
Ch, Cw = [int(a)-1 for a in input().split()]
Dh, Dw = [int(a)-1 for a in input().split()]

S = []
dist = []

for _ in range(H):
    S.append([a for a in input()])
    dist.append([-1 for _ in range(len(S[-1]))])

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

while q:
    jump_list = []
    while q:
        v = q.popleft()
        # print('here', v)
        jump_list.append(v)
        for i in [v[0]-1, v[0]+1]:
            j = v[1]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = cost
                q.append((i, j))
        for j in [v[1]-1, v[1]+1]:
            i = v[0]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = cost
                q.append((i, j))

    # print('normal', jump_list)
    cost += 1
    q = deque(list(jump_list))
    jump_list = []
    while q:
        v = q.popleft()
        # print('here', v)
        for i in range(v[0]-2, v[0]+3):
            for j in range(v[1]-2, v[1]+3):
                if ((i == v[0] + 1) or (i == v[0] -1)) and j == 0:
                    continue
                elif ((j == v[1] + 1) or (j == v[1] -1)) and i == 0:
                    continue
                if i >= 0 and j >= 0 and i < H and j < W and i != v[0] and j != v[1] and S[i][j]=='.' and dist[i][j] == -1:
                    dist[i][j] = cost
                    jump_list.append((i, j))
    q = deque(jump_list)

# print(dist)
print(dist[Dh][Dw])

Submission status: Wrong Answer

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

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

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




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
H, W = [int(a) for a in input().split()]
Ch, Cw = [int(a)-1 for a in input().split()]
Dh, Dw = [int(a)-1 for a in input().split()]

S = []
dist = []

for _ in range(H):
    S.append([a for a in input()])
    dist.append([-1 for _ in range(len(S[-1]))])

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

while q:
    jump_list = []
    while q:
        v = q.popleft()
        # print('here', v)
        jump_list.append(v)
        for i in [v[0]-1, v[0]+1]:
            j = v[1]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = cost
                q.append((i, j))
        for j in [v[1]-1, v[1]+1]:
            i = v[0]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = cost
                q.append((i, j))

    # print('normal', jump_list)
    cost += 1
    q = deque(list(jump_list))
    jump_list = []
    while q:
        v = q.popleft()
        # print('here', v)
        for i in range(v[0]-2, v[0]+3):
            for j in range(v[1]-2, v[1]+3):
                if ((i == v[0] + 1) or (i == v[0] -1)) and j == 0:
                    continue
                elif ((j == v[1] + 1) or (j == v[1] -1)) and i == 0:
                    continue
                if i >= 0 and j >= 0 and i < H and j < W and i != v[0] and j != v[1] and S[i][j]=='.' and dist[i][j] == -1:
                    dist[i][j] = cost
                    jump_list.append((i, j))
    q = deque(jump_list)

# print(dist)
print(dist[Dh][Dw])

Submission status: Wrong Answer

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


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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from queue import Queue as Q

totreat = Q()

def voisins(x,y):
	lst = []
	for i in range(x-2,x+3):
		for j in range(y-2, y+3):
			if i!=x and j!=y : lst+=[(i,j)]
	return lst

def bfs():
	while not totreat.empty():
		x,y = totreat.get()
		# ~ print("x,y=",x,y)
		for a,b in ((x,y+1),(x,y-1),(x+1,y),(x-1,y)):
			if 0<=a<H and 0<=b<W and g[a][b]=='.' and not vis[a][b]:
				# ~ print("dec norm ",a,b)
				vis[a][b] = True
				dist[a][b] = min(dist[a][b],dist[x][y])
				totreat.put((a,b))
		for a,b in voisins(x,y):
			if 0<=a<H and 0<=b<W and g[a][b]=='.' and not vis[a][b]:
				# ~ print("dec magi ",a,b)
				vis[a][b] = True
				dist[a][b] = min(dist[a][b],1+dist[x][y])
				totreat.put((a,b))

H,W = [int(i) for i in input().split()]
CH,CW = [int(i)-1 for i in input().split()]
DH,DW= [int(i)-1 for i in input().split()]
g = [input() for i in range(H)]
vis = [[False]*W for i in range(H)]
dist = [[float('inf')]*W for i in range(H)]
dist[CH][CW] = 0
vis[CH][CW] = True
totreat.put((CH,CW))

bfs()

if not vis[DH][DW]: print("-1")
else : print(dist[DH][DW])

Submission status: Wrong Answer

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 = [" "]
for _ in range(H):
    S.append(" " + input())
INF = 100000
warp_min = [[INF] * (W + 1) for _ in range(H + 1)]
warp_min[Ch][Cw] = 0
d = deque()
d.append((Ch, Cw))
dx = (0, 1, 0, -1)
dy = (1, 0, -1, 0)
ndx = (0, 1, 0, -1, 1, -1, -1, 1)
ndy = (1, 0, -1, 0, 1, -1, 1, -1)

cnt = 0

#while warp_min[Dh][Dw] == INF:
while d:
    wall_pos = []
    pos = d.popleft()
    #next_pos = []
    for i in range(4):
        next_y = pos[0] + dy[i]
        next_x = pos[1] + dx[i]
        if next_x <= 0 or next_x > W or next_y <= 0 or next_y > H:
            continue
        if warp_min[next_y][next_x] != INF:
            continue
        if S[next_y][next_x] == ".":
            warp_min[next_y][next_x] = min(warp_min[pos[0]][pos[1]], warp_min[next_y][next_x])
            d.append((next_y, next_x))
        else:
            for i in range(8):
                warp_to_y = next_y + ndy[i]
                warp_to_x = next_x + ndx[i]
                if warp_to_x <= 0 or warp_to_x > W or warp_to_y <= 0 or warp_to_y > H:
                    continue
                if warp_min[warp_to_y][warp_to_x] != INF:
                    continue
                if S[warp_to_y][warp_to_x] == ".":
                    warp_min[warp_to_y][warp_to_x] = min(warp_min[pos[0]][pos[1]] + 1, warp_min[warp_to_y][warp_to_x])
                    d.append((warp_to_y, warp_to_x))





#for i in warp_min:
#    print(i)
if warp_min[Dh][Dw] == INF:
    warp_min[Dh][Dw] = -1
print(warp_min[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
H, W = [int(a) for a in input().split()]
Ch, Cw = [int(a)-1 for a in input().split()]
Dh, Dw = [int(a)-1 for a in input().split()]

S = []
dist = []

for _ in range(H):
    S.append([a for a in input()])
    dist.append([-1 for _ in range(len(S[-1]))])

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

while q:
    jump_list = set()
    while q:
        v = q.popleft()
        # print('here', v)
        jump_list.add(v)
        d = dist[v[0]][v[1]]
        for i in [v[0]-1, v[0]+1]:
            j = v[1]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and (dist[i][j] == -1 or dist[i][j] > d) :
                dist[i][j] = d 
                q.append((i, j))
        for j in [v[1]-1, v[1]+1]:
            i = v[0]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and (dist[i][j] == -1 or dist[i][j] > d):
                dist[i][j] = d
                q.append((i, j))

    q = deque(list(jump_list))
    jump_list = set()
    while q:
        v = q.popleft()
        # print('here', v)
        for i in range(v[0]-2, v[0]+3):
            for j in range(v[1]-2, v[1]+3):
                if ((i == v[0] + 1) or (i == v[0] -1)) and j == 0:
                    continue
                elif ((j == v[1] + 1) or (j == v[1] -1)) and i == 0:
                    continue
                else:
                    d = dist[v[0]][v[1]] + 1
                if i >= 0 and j >= 0 and i < H and j < W and i != v[0] and j != v[1] and S[i][j]=='.' and (dist[i][j] == -1 or dist[i][j] > d):
                    dist[i][j] = d
                    q.append((i, j))
                    jump_list.add((i, j))
    q = deque(list(jump_list))

# print(dist)
print(dist[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
H, W = [int(a) for a in input().split()]
Ch, Cw = [int(a)-1 for a in input().split()]
Dh, Dw = [int(a)-1 for a in input().split()]

S = []
dist = []

for _ in range(H):
    S.append([a for a in input()])
    dist.append([-1 for _ in range(len(S[-1]))])

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

while q:
    jump_list = []
    while q:
        v = q.popleft()
        # print('here', v)
        jump_list.append(v)
        d = dist[v[0]][v[1]]
        for i in [v[0]-1, v[0]+1]:
            j = v[1]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and (dist[i][j] == -1 or dist[i][j] > d) :
                dist[i][j] = d 
                q.append((i, j))
        for j in [v[1]-1, v[1]+1]:
            i = v[0]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and (dist[i][j] == -1 or dist[i][j] > d):
                dist[i][j] = d
                q.append((i, j))

    q = deque(jump_list)
    jump_list = []
    while q:
        v = q.popleft()
        # print('here', v)
        for i in range(v[0]-2, v[0]+3):
            for j in range(v[1]-2, v[1]+3):
                if ((i == v[0] + 1) or (i == v[0] -1)) and j == 0:
                    continue
                elif ((j == v[1] + 1) or (j == v[1] -1)) and i == 0:
                    continue
                else:
                    d = dist[v[0]][v[1]] + 1
                if i >= 0 and j >= 0 and i < H and j < W and i != v[0] and j != v[1] and S[i][j]=='.' and (dist[i][j] == -1 or dist[i][j] > d):
                    dist[i][j] = d
                    q.append((i, j))
                    jump_list.append((i, j))
    q = deque(jump_list)

# print(dist)
print(dist[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
H, W = [int(a) for a in input().split()]
Ch, Cw = [int(a)-1 for a in input().split()]
Dh, Dw = [int(a)-1 for a in input().split()]

S = []
dist = []

for _ in range(H):
    S.append([a for a in input()])
    dist.append([-1 for _ in range(len(S[-1]))])

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

while q:
    jump_list = []
    while q:
        v = q.popleft()
        # print('here', v)
        jump_list.append(v)
        for i in [v[0]-1, v[0]+1]:
            j = v[1]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = dist[v[0]][v[1]]
                q.append((i, j))
        for j in [v[1]-1, v[1]+1]:
            i = v[0]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = dist[v[0]][v[1]]
                q.append((i, j))

    q = deque(jump_list)
    jump_list = []
    while q:
        v = q.popleft()
        # print('here', v)
        for i in range(v[0]-2, v[0]+3):
            for j in range(v[1]-2, v[1]+3):
                if ((i == v[0] + 1) or (i == v[0] -1)) and j == 0:
                    continue
                elif ((j == v[1] + 1) or (j == v[1] -1)) and i == 0:
                    continue
                else:
                    d = dist[v[0]][v[1]] + 1
                if i >= 0 and j >= 0 and i < H and j < W and i != v[0] and j != v[1] and S[i][j]=='.' and (dist[i][j] == -1 or dist[i][j] > d):
                    dist[i][j] = d
                    q.append((i, j))
                    jump_list.append((i, j))
    q = deque(jump_list)

print(dist[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
H, W = [int(a) for a in input().split()]
Ch, Cw = [int(a)-1 for a in input().split()]
Dh, Dw = [int(a)-1 for a in input().split()]

S = []
dist = []

for _ in range(H):
    S.append([a for a in input()])
    dist.append([-1 for _ in range(len(S[-1]))])

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

while q:
    jump_list = []
    while q:
        v = q.popleft()
        # print('here', v)
        jump_list.append(v)
        for i in [v[0]-1, v[0]+1]:
            j = v[1]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = 0
                q.append((i, j))
        for j in [v[1]-1, v[1]+1]:
            i = v[0]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = 0
                q.append((i, j))

    q = deque(jump_list)
    jump_list = []
    while q:
        v = q.popleft()
        # print('here', v)
        for i in range(v[0]-2, v[0]+3):
            for j in range(v[1]-2, v[1]+3):
                if ((i == v[0] + 1) or (i == v[0] -1)) and j == 0:
                    continue
                elif ((j == v[1] + 1) or (j == v[1] -1)) and i == 0:
                    continue
                else:
                    d = dist[v[0]][v[1]] + 1
                if i >= 0 and j >= 0 and i < H and j < W and i != v[0] and j != v[1] and S[i][j]=='.' and (dist[i][j] == -1 or dist[i][j] > d):
                    dist[i][j] = d
                    q.append((i, j))
                    jump_list.append((i, j))
    q = deque(jump_list)

print(dist[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
H, W = [int(a) for a in input().split()]
Ch, Cw = [int(a)-1 for a in input().split()]
Dh, Dw = [int(a)-1 for a in input().split()]

S = []
dist = []

for _ in range(H):
    S.append([a for a in input()])
    dist.append([-1 for _ in range(len(S[-1]))])

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

while q:
    jump_list = []
    while q:
        v = q.popleft()
        # print('here', v)
        jump_list.append(v)
        for i in [v[0]-1, v[0]+1]:
            j = v[1]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = 0
                q.append((i, j))
        for j in [v[1]-1, v[1]+1]:
            i = v[0]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = 0
                q.append((i, j))

    q = deque(jump_list)
    jump_list = []
    while q:
        v = q.popleft()
        # print('here', v)
        for i in range(v[0]-2, v[0]+3):
            for j in range(v[1]-2, v[1]+3):
                if ((i == v[0] + 1) or (i == v[0] -1)) and j == 0:
                    continue
                elif ((j == v[1] + 1) or (j == v[1] -1)) and i == 0:
                    continue
                else:
                    d = dist[v[0]][v[1]] + 1
                if i >= 0 and j >= 0 and i < H and j < W and i != v[0] and j != v[1] and S[i][j]=='.' and dist[i][j] == -1:
                    dist[i][j] = d
                    q.append((i, j))
                    jump_list.append((i, j))
    q = deque(jump_list)


# print(dist)
print(dist[Dh][Dw])

Submission status: Wrong Answer

Solution code:
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

lim = 10**6

S = ['#'*(W+4)]
S.append('#'*(W+4))
for k in range(H):
  S.append('##' + input() + '##')
S.append('#'*(W+4))
S.append('#'*(W+4))

foo = [[-1 for _ in range(W+4)] for _ in range(H+4)]
rev = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      foo[k][j] = lim
      rev[k][j] = lim



foo[Ch][Cw] = 0
rev[Dh][Dw] = 0
jump = [(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-1,2),(-1,1),(-1,-1),(-1,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2)]
mv = [(1,0),(-1,0),(0,1),(0,-1)]
now = deque([])
new = deque([(Ch, Cw)])
while len(new) > 0:
  item = new.pop()
  now.append(item)
  x = item[0]
  y = item[1]
  for m in mv:
    mx = x + m[0]
    my = y + m[1]
    if rev[mx][my] == 0:
      print(0)
      exit()
    else:
      if foo[mx][my] == lim:
        foo[mx][my] = 0
        new.append((mx, my))

now_rev = deque([])
new_rev = deque([(Dh,Dw)])
while len(new_rev) > 0:
  item = new_rev.pop()
  now_rev.append(item)
  x = item[0]
  y = item[1]
  for m in mv:
    mx = x + m[0]
    my = y + m[1]
    if rev[mx][my] == lim:
      rev[mx][my] = 0
      new_rev.append((mx, my))


start = 0
while True:
  if len(now) == 0:
    print(-1)
    exit() 
  start += 1
  while len(now) > 0:
    item = now.pop()
    x = item[0]
    y = item[1]
    for j in jump:
      jx = x + j[0]
      jy = y + j[1]
      if foo[jx][jy] > start:
        foo[jx][jy] = start
        new.append((jx,jy))
  flag = True
  while len(new) > 0:
    item = new.pop()
    now.append(item)
    x = item[0]
    y = item[1]
    for m in mv:
      mx = x + m[0]
      my = y + m[1]
      if flag:
        if rev[mx][my] ==  lim:
          flag = False
        if 0 <= rev[mx][my] < lim:
          print(foo[x][y] + rev[mx][my])
          exit()
        else:
          if foo[mx][my] == lim:
            foo[mx][my] = start
            new.append((mx, my))
      else:
        if foo[mx][my] == lim:
          foo[mx][my] = start
          new.append((mx, my))

  if len(now_rev) == 0:
    print(-1)
    exit() 
  while len(now_rev) > 0:
    item = now_rev.pop()
    x = item[0]
    y = item[1]
    for j in jump:
      jx = x + j[0]
      jy = y + j[1]
      if rev[jx][jy] > start:
        rev[jx][jy] = start
        new_rev.append((jx,jy))

  flag = True
  while len(new_rev) > 0:
    item = new_rev.pop()
    now_rev.append(item)
    x = item[0]
    y = item[1]
    for m in mv:
      mx = x + m[0]
      my = y + m[1]
      if flag:
        if foo[mx][my] == lim:
          flag = False
        if 0 <= foo[mx][my] < lim:
          print(rev[x][y] + foo[mx][my])
          exit()
        else:
          if rev[mx][my] == lim:
            rev[mx][my] = start
            new_rev.append((mx, my))
      else:
        if rev[mx][my] == lim:
          rev[mx][my] = start
          new_rev.append((mx, my))

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3
def main():
    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 += [[[0,1][x=='#']for x in input()]]

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


    dy2 = []
    dx2 = []
    for y in range(-2,3):
        for x in range(-2,3):
            if abs(y)+abs(x) > 1:
                dy2 += [y]
                dx2 += [x]
    dl = len(dx2)

    q = [(CH-1, CW-1)]
    a = [(CH-1, CW-1)]
    f = True
    c = 0
    ans = -1
    while f:
        f = False
        while q:
            for y, x in q:
                t = []
                G[y][x] = 2
                for d in range(4):
                    px = x + dx[d]
                    py = y + dy[d]
                    if 0<=px<W and 0<=py<H and G[py][px] == 0:
                        G[py][px] = 2
                        t += [(py, px)]
                        a += [(py, px)]
            q = t
        b = []
        s = set()
        for y, x in a:
            for d in range(dl):
                px = x + dx2[d]
                py = y + dy2[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0 and (py,px) not in s:
                    s.add((py,px))
                    b += [(py, px)]
                    q += [(py, px)]
        # for i in G:
        #     print(i)
        # print()
        if G[DH-1][DW-1] == 2:
            ans = c
            break
        c += 1
        a = b
        if b : f = True
        
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    Ch, Cw = il()
    Dh, Dw = il()
    grid = [iss() for _ in range(H)]
    visited = [[INF] * W for _ in range(H)]
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    que = collections.deque()

    que.appendleft((Ch - 1, Cw - 1, 0))
    visited[Ch - 1][Cw - 1] = 0
    while que:
        while que:
            h, w, c = que.popleft()
            for mh, mw in move:  # 移動A: 歩いて移動
                ch, cw = h + mh, w + mw
                if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] > c:
                    visited[ch][cw] = c
                    que.appendleft((ch, cw, c))
        for wh in range(-2, 3):  # 移動B: ワープ魔法
            for ww in range(-2, 3):
                ch, cw = h + wh, w + ww
                if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] > c + 1:
                    visited[ch][cw] = c + 1
                    que.append((ch, cw, c + 1))

    ret = visited[Dh - 1][Dw - 1]
    print(-1 if ret == INF else ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    Ch, Cw = il()
    Dh, Dw = il()
    grid = [iss() for _ in range(H)]
    visited = [[INF] * W for _ in range(H)]
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    que = collections.deque()

    que.appendleft((Ch - 1, Cw - 1, 0))
    visited[Ch - 1][Cw - 1] = 0
    while que:
        while que:
            h, w, c = que.popleft()
            for mh, mw in move:  # 移動A: 歩いて移動
                ch, cw = h + mh, w + mw
                if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] > c:
                    visited[ch][cw] = c
                    que.appendleft((ch, cw, c))
        for wh in range(-2, 3):  # 移動B: ワープ魔法
            for ww in range(-2, 3):
                ch, cw = h + wh, w + ww
                if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] == INF:
                    visited[ch][cw] = c + 1
                    que.append((ch, cw, c + 1))

    ret = visited[Dh - 1][Dw - 1]
    print(-1 if ret == INF else ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h,w=map(int, input().split())
c_h,c_w=map(int, input().split())
d_h,d_w=map(int, input().split())
map=[[-1]*w for i in range(h)]
 
for gyou in range(h):
    tmp=input()
    for retu in range(w):
        if tmp[retu]=="#":map[gyou][retu]=-2
 
genzai=[[c_h-1,c_w-1]]
wapu=[[c_h-1,c_w-1]]
 
map[c_h-1][c_w-1]=0
 
def idou(gyou,retu,kaisuu):
    for i in (-1,1):
        if 0<=gyou+i and gyou+i<h:
            if map[gyou+i][retu]==-1:
                map[gyou+i][retu]=kaisuu
                genzai.append([gyou+i,retu])
                wapu.append([gyou+i,retu])
    for i in (-1,1):
        if 0<=retu+i and retu+i<w:
            if map[gyou][retu+i]==-1:
                map[gyou][retu+i]=kaisuu
                genzai.append([gyou,retu+i])
                wapu.append([gyou,retu+i])

def idou_wapu(gyou,retu,kaisuu):
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=gyou+i and gyou+i<h and 0<=retu+j and retu+j<w:
                if map[gyou+i][retu+j]==-1:
                    map[gyou+i][retu+j]=kaisuu+1
                    genzai.append([gyou+i,retu+j])

wapu_kaisuu=0

while len(genzai)!=0:
 
    while len(genzai)>0:
        idou(genzai[0][0],genzai[0][1],wapu_kaisuu)
        genzai.pop(0)
    
    while len(wapu)>0:
        idou_wapu(wapu[0][0],wapu[0][1],wapu_kaisuu)
        wapu.pop(0)
    
    wapu_kaisuu+=1

print(map[d_h-1][d_w-1])

Submission status: Wrong Answer

Solution code:
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
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  while d != deque():
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
        d.append(_p)
  # 移動B
  ans += 1
  for i in b:
    for j in b:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and not (i == 0 and j == 0) and t[_h][_w] == '.':
        d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()