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


def bfs(sy, sx):
    t = ((-1,0),(0,-1),(1,0),(0,1))
    dist = [[inf]*w for i in range(h)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])
    while(q):
        y,x = q.popleft()
        d = dist[y][x]
        if (0 <= x < w) and (0 <= y < h):
            for i,j in t:
                ny,nx = y+i,x+j
                if (0 <= nx < w and 0 <= ny < h):
                    if dist[ny][nx] <= d or s[ny][nx] == "#":
                        continue
                    q.appendleft((y+i,x+j))
                    dist[ny][nx] = d
            for i in range(-2,3):
                for j in range(-2,3):
                    ny,nx = y+i,x+j
                    if (0 <= nx < w and 0 <= ny < h):
                        if dist[ny][nx] <= d+1 or s[ny][nx] == "#":
                            continue
                        q.append((i,j))
                        dist[ny][nx] = d+1
    return dist

inf = 10**9
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)]
ch, cw = ch - 1, cw - 1
dh, dw = dh - 1, dw - 1
dist = bfs(ch,cw)
ans = dist[dh][dw]
if ans == inf:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [readline() for _ in range(H)]

INF = int(1e7)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
deq = deque()
deq.append((C_h,C_w))

move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(-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)]

while len(deq):
  h,w = deq.popleft()
  if dist[h][w] != INF:
    continue
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))

print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int,input().split())
sh, sw = map(int,input().split())
gh, gw = map(int,input().split())
sh, sw, gh, gw = sh-1, sw-1, gh-1, gw-1
S = [input() for _ in range(H)]

INF = 10**9
ans = [[INF] * W for _ in range(H)]

def bfs(h0, w0):
    checked = []

    Q = deque([[h0,w0]])
    while len(Q) > 0:
        h, w = Q.popleft()
        checked.append([h,w])

        for dh, dw  in [[0,1],[0,-1],[1,0],[-1,0]]:
            nh, nw = h + dh, w + dw
            if 0 <= nh and nh < H and 0 <= nw and nw < W:
                if S[nh][nw] == "." and ans[nh][nw] == INF:
                    ans[nh][nw] = ans[h0][w0]
                    Q.append([nh, nw])
    
    for h, w in checked:
        for dh in range(-2,3):
            for dw in range(-2,3):
                nh, nw = h + dh, w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W:
                    if S[nh][nw] == "." and ans[nh][nw] == INF:
                        ans[nh][nw] = ans[h0][w0] + 1
                        next_bfs_start.append([nh,nw])

bfs_start = [[sh,sw]]
ans[sh][sw] = 0

while len(bfs_start) > 0:
    next_bfs_start = []
    for h0, w0 in bfs_start: bfs(h0,w0)
    bfs_start = next_bfs_start


if ans[gh][gw] == INF:
    print(-1)
else:
    print(ans[gh][gw])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int,input().split())
sh, sw = map(int,input().split())
gh, gw = map(int,input().split())
sh, sw, gh, gw = sh-1, sw-1, gh-1, gw-1
S = [input() for _ in range(H)]

INF = 10**9
ans = [[INF] * W for _ in range(H)]

def bfs(h0, w0):
    checked = []

    Q = deque([[h0,w0]])
    while len(Q) > 0:
        h, w = Q.popleft()
        checked.append([h,w])

        for dh, dw  in [[0,1],[0,-1],[1,0],[-1,0]]:
            nh, nw = h + dh, w + dw
            if 0 <= nh and nh < H and 0 <= nw and nw < W:
                if S[nh][nw] == "." and ans[nh][nw] == INF:
                    ans[nh][nw] = ans[h0][w0]
                    Q.append([nh, nw])
    
    for h, w in checked:
        for dh in range(-2,3):
            for dw in range(-2,3):
                nh, nw = h + dh, w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W:
                    if S[nh][nw] == "." and ans[nh][nw] == INF:
                        ans[nh][nw] = ans[h0][w0] + 1
                        next_bfs_start.append([nh,nw])

bfs_start = [[sh,sw]]
ans[sh][sw] = 0

while len(bfs_start) > 0:
    print(bfs_start)
    next_bfs_start = []
    for h0, w0 in bfs_start: bfs(h0,w0)
    bfs_start = next_bfs_start


if ans[gh][gw] == INF:
    print(-1)
else:
    print(ans[gh][gw])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int,input().split())
sh, sw = map(int,input().split())
gh, gw = map(int,input().split())
sh, sw, gh, gw = sh-1, sw-1, gh-1, gw-1
S = [input() for _ in range(H)]

INF = 10**9
ans = [[INF] * W for _ in range(H)]

def bfs(h0, w0):
    dh, dw = [0,-1,0,1], [1,0,-1,0]

    Q = deque([[h0,w0]])
    checked = [[h0,w0]]
    while len(Q) > 0:
        h, w = Q.popleft()
        for i in range(4):
            nh, nw = h + dh[i], w + dw[i]
            if 0 <= nh and nh < H and 0 <= nw and nw < W:
                if S[nh][nw] == "." and ans[nh][nw] == INF:
                    ans[nh][nw] = ans[h0][w0]
                    Q.append([nh, nw])
                    checked.append([nh,nw])
    
    res = []
    for h, w in checked:
        for dh in range(-2,3):
            for dw in range(-2,3):
                nh, nw = h + dh, w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W:
                    if S[nh][nw] == "." and ans[nh][nw] > ans[h0][w0] + 1:
                        ans[nh][nw] = ans[h0][w0] + 1
                        res.append([nh,nw])
    return res

ans[sh][sw] = 0
bfs_start = [[sh,sw]]
while len(bfs_start) > 0:
    next_bfs_start = []
    for h0, w0 in bfs_start:
        next_bfs_start += bfs(h0,w0)
    bfs_start = next_bfs_start

if ans[gh][gw] == INF:
    print(-1)
else:
    print(ans[gh][gw])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int,input().split())
sh, sw = map(int,input().split())
gh, gw = map(int,input().split())
sh, sw, gh, gw = sh-1, sw-1, gh-1, gw-1
S = [input() for _ in range(H)]

INF = 10**9
ans = [[INF] * W for _ in range(H)]

def bfs(h0, w0):
    dh, dw = [0,-1,0,1], [1,0,-1,0]

    Q = deque([[h0,w0]])
    checked = [[h0,w0]]
    while len(Q) > 0:
        h, w = Q.popleft()
        for i in range(4):
            nh, nw = h + dh[i], w + dw[i]
            if 0 <= nh and nh < H and 0 <= nw and nw < W:
                if S[nh][nw] == "." and ans[nh][nw] == INF:
                    ans[nh][nw] = ans[h0][w0]
                    Q.append([nh, nw])
                    checked.append([nh,nw])
    
    res = []
    for h, w in checked:
        for dh in range(-2,3):
            for dw in range(-2,3):
                nh, nw = h + dh, w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W:
                    if S[nh][nw] == "." and ans[nh][nw] > ans[h0][w0] + 1:
                        ans[nh][nw] = ans[h0][w0] + 1
                        res.append([nh,nw])
    return res

ans[sh][sw] = 0
bfs_start = [[sh,sw]]
while len(bfs_start) > 0:
    next_bfs_start = []
    for h0, w0 in bfs_start:
        next_bfs_start += bfs(h0,w0)
    bfs_start = next_bfs_start

for a in ans:
    print(a)

if ans[gh][gw] == INF:
    print(-1)
else:
    print(ans[gh][gw])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int,input().split())
sh, sw = map(int,input().split())
gh, gw = map(int,input().split())
sh, sw, gh, gw = sh-1, sw-1, gh-1, gw-1
S = [input() for _ in range(H)]

ans = [[10**9] * W for _ in range(H)]

def bfs(h0, w0):
    dh, dw = [0,-1,0,1], [1,0,-1,0]

    Q = deque([[h0,w0]])
    checked = [[h0,w0]]
    while len(Q) > 0:
        h, w = Q.popleft()
        for i in range(4):
            nh, nw = h + dh[i], w + dw[i]
            if 0 <= nh and nh < H and 0 <= nw and nw < W:
                if S[nh][nw] == "." and ans[nh][nw] == 10**9:
                    ans[nh][nw] = ans[h0][w0]
                    Q.append([nh, nw])
                    checked.append([nh,nw])
    
    res = []
    for h, w in checked:
        for dh in range(-2,3):
            for dw in range(-2,3):
                nh, nw = h + dh, w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W:
                    if S[nh][nw] == "." and ans[nh][nw] == 10**9:
                        ans[nh][nw] = ans[h0][w0] + 1
                        res.append([nh,nw])
    return res

ans[sh][sw] = 0
bfs_start = [[sh,sw]]
while len(bfs_start) > 0:
    next_bfs_start = []
    for h0, w0 in bfs_start:
        next_bfs_start += bfs(h0,w0)
    bfs_start = next_bfs_start

if ans[gh][gw] == 10**9:
    print(-1)
else:
    print(ans[gh][gw])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int,input().split())
sh, sw = map(int,input().split())
gh, gw = map(int,input().split())
sh, sw, gh, gw = sh-1, sw-1, gh-1, gw-1
S = [input() for _ in range(H)]

ans = [[10**9] * W for _ in range(H)]

def bfs(h0, w0):
    dh, dw = [0,-1,0,1], [1,0,-1,0]

    Q = deque([[h0,w0]])
    checked = [[h0,w0]]
    while len(Q) > 0:
        h, w = Q.popleft()
        for i in range(4):
            nh, nw = h + dh[i], w + dw[i]
            if 0 <= nh and nh < H and 0 <= nw and nw < W:
                if S[nh][nw] == "." and ans[nh][nw] == 10**9:
                    ans[nh][nw] = ans[h0][w0]
                    Q.append([nh, nw])
                    checked.append([nh,nw])
    
    res = []
    for h, w in checked:
        for dh in range(-2,3):
            for dw in range(-2,3):
                nh, nw = h + dh, w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W:
                    if S[nh][nw] == "." and ans[nh][nw] == 10**9:
                        ans[nh][nw] = ans[h0][w0] + 1
                        res.append([nh,nw])
    return res

ans[sh][sw] = 0
bfs_start = [[sh,sw]]
while len(bfs_start) > 0:
    next_bfs_start = []
    for h0, w0 in bfs_start:
        next_bfs_start += bfs(h0,w0)
    bfs_start = next_bfs_start

print(ans[gh][gw])

Submission status: Wrong Answer

Solution code:
import collections
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) - 1 for _ in [H, W, ch, cw, dh, dw]]
H += 1
W += 1
Q = collections.deque([[ch, cw]])
INF = 10**10
dist = [[INF] * W for _ in range(H)]
dist[ch][cw] = 0
while Q:
    x, y = Q.popleft()
    d = dist[x][y]
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        nx, ny = x + dx, y + dy
        if not (0 <= nx < H and 0 <= ny < W):
            continue
        if S[nx][ny] == '#':
            continue
        if dist[nx][ny] <= d:
            continue
        dist[nx][ny] = d
        Q.appendleft([nx, ny])
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '#':
                continue
            if dist[nx][ny] <= d + 1:
                continue
            dist[nx][ny] = d + 1
            Q.append([nx, ny])
ans = dist[dh][dw]
if ans == INF or ans == 0:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
h, w, si, sj, ti, tj, *s = open(0).read().split()
h, w, si, sj, ti, tj = [int(_) - 1 for _ in [h, w, si, sj, ti, tj]]
h += 1
w += 1
INF = 10**9
dist = [[INF] * w for _ in range(h)]
q = collections.deque([[si, sj]])
dist[si][sj] = 0
while q:
    i, j = q.popleft()
    d = dist[i][j]
    for ei in range(-1, 2):
        for ej in range(-1, 2):
            ni, nj = i + ei, j + ej
            if not (0 <= ni < h and 0 <= nj < w):
                continue
            if s[ni][nj] == '#':
                continue
            if dist[ni][nj] == d:
                continue
            dist[ni][nj] = d
            q.appendleft([ni, nj])
    for ei in range(-2, 3):
        for ej in range(-2, 3):
            ni, nj = i + ei, j + ej
            if not (0 <= ni < h and 0 <= nj < w):
                continue
            if s[ni][nj] == '#':
                continue
            if dist[ni][nj] <= d + 1:
                continue
            dist[ni][nj] = d + 1
            q.append([ni, nj])
ans = dist[ti][tj]
if ans == INF or ans == 0:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.appendleft((nh, nw, d))
        dst[nh][nw] = d

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.append((nh, nw, d + 1))
        dst[nh][nw] = d + 1

print(dst[eh][ew])

Submission status: Wrong Answer

Solution code:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1:
            dst[nh][nw] = dst[h][w]
        elif dst[h][w] < dst[nh][nw]:
            dst[nh][nw] =  dst[h][w]
        else: continue
        dq.append((nh, nw))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        if dst[nh][nw] == -1:
            dst[nh][nw] = dst[h][w] + 1
        elif dst[h][w] + 1 < dst[nh][nw]:
            dst[nh][nw] = dst[h][w] + 1
        else: continue
        dq.append((nh, nw))

print(dst[eh][ew])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

ch += 1
cw += 1
gh += 1
gw += 1

maze = ["#"*(W+4), "#"*(W+4)] + ["##" + input() + "##" for _ in range(H)] + ["#"*(W+4), "#"*(W+4)]
visited = [[-1]*(W+4) for _ in range(H+4)]
visited[ch][cw] = 0

walk = [[-1, 0], [1, 0], [0, -1], [0, 1]]
warp = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2],
        [0, -2], [0, -1], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

stack_walk = [[ch, cw]]
stack_warp = [[ch, cw]]

while stack_walk or stack_warp:
    while stack_walk:
        h, w = stack_walk.pop()
        for dh, dw in walk:
            h_next = h + dh
            w_next = w + dw
            if maze[h_next][w_next]=="." and (visited[h_next][w_next]==-1):
                visited[h_next][w_next] = visited[h][w]
                stack_walk.append([h_next, w_next])
                stack_warp.append([h_next, w_next])
    
    while len(stack_warp)!=0 and len(stack_walk)==0:
        h, w = stack_warp.pop()
        for dh, dw in warp:
            h_next = h + dh
            w_next = w + dw
            if maze[h_next][w_next]=="." and visited[h_next][w_next]==-1:
                visited[h_next][w_next] = visited[h][w] + 1
                stack_walk.append([h_next, w_next])
                stack_warp.append([h_next, w_next])

print(visited[gh][gw])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

ch += 1
cw += 1
gh += 1
gw += 1

maze = ["#"*(W+4), "#"*(W+4)] + ["##" + input() + "##" for _ in range(H)] + ["#"*(W+4), "#"*(W+4)]
visited = [[-1]*(W+4) for _ in range(H+4)]
visited[ch][cw] = 0

walk = [[-1, 0], [1, 0], [0, -1], [0, 1]]
warp = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2],
        [0, -2], [0, -1], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

stack_walk = [[ch, cw]]
stack_warp = [[ch, cw]]

while stack_walk or stack_warp:
    while stack_walk:
        h, w = stack_walk.pop()
        for dh, dw in walk:
            h_next = h + dh
            w_next = w + dw
            if maze[h_next][w_next]=="." and (visited[h_next][w_next]==-1 or visited[h_next][w_next] > visited[h][w]):
                visited[h_next][w_next] = visited[h][w]
                stack_walk.append([h_next, w_next])
                stack_warp.append([h_next, w_next])
    
    while len(stack_warp)!=0 and len(stack_walk)==0:
        h, w = stack_warp.pop()
        for dh, dw in warp:
            h_next = h + dh
            w_next = w + dw
            if maze[h_next][w_next]=="." and visited[h_next][w_next]==-1:
                visited[h_next][w_next] = visited[h][w] + 1
                stack_walk.append([h_next, w_next])
                stack_warp.append([h_next, w_next])

print(visited[gh][gw])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

ch += 1
cw += 1
gh += 1
gw += 1

maze = ["#"*(W+4), "#"*(W+4)] + ["##" + input() + "##" for _ in range(H)] + ["#"*(W+4), "#"*(W+4)]
visited = [[-1]*(W+4) for _ in range(H+4)]
visited[ch][cw] = 0

walk = [[-1, 0], [1, 0], [0, -1], [0, 1]]
warp = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2],
        [0, -2], [0, -1], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

stack_walk = [[ch, cw]]
stack_warp = [[ch, cw]]

while stack_walk or stack_warp:
    while stack_walk:
        h, w = stack_walk.pop()
        for dh, dw in walk:
            h_next = h + dh
            w_next = w + dw
            if maze[h_next][w_next]=="." and (visited[h_next][w_next]==-1 or visited[h_next][w_next] > visited[h][w]):
                visited[h_next][w_next] = visited[h][w]
                stack_walk.append([h_next, w_next])
                stack_warp.append([h_next, w_next])
    
    while stack_warp and not stack_walk:
        h, w = stack_warp.pop()
        for dh, dw in warp:
            h_next = h + dh
            w_next = w + dw
            if maze[h_next][w_next]=="." and visited[h_next][w_next]==-1:
                visited[h_next][w_next] = visited[h][w] + 1
                stack_walk.append([h_next, w_next])
                stack_warp.append([h_next, w_next])

print(visited[gh][gw])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

ch += 1
cw += 1
gh += 1
gw += 1

maze = ["#"*(W+4), "#"*(W+4)] + ["##" + input() + "##" for _ in range(H)] + ["#"*(W+4), "#"*(W+4)]
visited = [[-1]*(W+4) for _ in range(H+4)]
visited[ch][cw] = 0

walk = [[-1, 0], [1, 0], [0, -1], [0, 1]]
warp = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2],
        [0, -2], [0, -1], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

stack_walk = [[ch, cw]]
stack_warp = [[ch, cw]]

while stack_walk or stack_warp:
    while stack_walk:
        h, w = stack_walk.pop()
        for dh, dw in walk:
            h_next = h + dh
            w_next = w + dw
            if maze[h_next][w_next]=="." and (visited[h_next][w_next]==-1 or visited[h_next][w_next] > visited[h][w]):
                visited[h_next][w_next] = visited[h][w]
                stack_walk.append([h_next, w_next])
                stack_warp.append([h_next, w_next])
    
    while stack_warp:
        h, w = stack_warp.pop()
        for dh, dw in warp:
            h_next = h + dh
            w_next = w + dw
            if maze[h_next][w_next]=="." and visited[h_next][w_next]==-1:
                visited[h_next][w_next] = visited[h][w] + 1
                stack_walk.append([h_next, w_next])
                stack_warp.append([h_next, w_next])

print(visited[gh][gw])

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

ch += 1
cw += 1
gh += 1
gw += 1

maze = ["#"*(W+4), "#"*(W+4)] + ["##" + input() + "##" for _ in range(H)] + ["#"*(W+4), "#"*(W+4)]
visited = [[-1]*(W+4) for _ in range(H+4)]
visited[ch][cw] = 0

walk = [[-1, 0], [1, 0], [0, -1], [0, 1]]
warp = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2],
        [0, -2], [0, -1], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

stack_walk = [[ch, cw]]
stack_warp = [[ch, cw]]

while stack_walk or stack_warp:
    while stack_walk:
        h, w = stack_walk.pop()
        for dh, dw in walk:
            h_next = h + dh
            w_next = w + dw
            if maze[h_next][w_next]=="." and (visited[h_next][w_next]==-1 or visited[h_next][w_next] > visited[h][w]):
                visited[h_next][w_next] = visited[h][w]
                stack_walk.append([h_next, w_next])
                stack_warp.append([h_next, w_next])
    
    while stack_warp:
        h, w = stack_warp.pop()
        for dh, dw in warp:
            h_next = h + dh
            w_next = w + dw
            if maze[h_next][w_next]=="." and visited[h_next][w_next]==-1:
                visited[h_next][w_next] = visited[h][w] + 1
                stack_walk.append([h_next, w_next])
                stack_warp.append([h_next, w_next])

print(visited[gh][gw])

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

h, w = map(int, input().split())
ci, cj = map(lambda x: int(x) - 1, input().split())
di, dj = map(lambda x: int(x) - 1, input().split())
mapp = []
for _ in range(h):
    mapp.append(list(input()))

walk_ways = [(-1, 0), (1, 0), (0, 1), (0, -1)]
warp_ways = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]

d = deque()
cost = 0
while 1:
    while 1:
        for way in walk_ways:
            if ci + way[0] >= h or ci + way[0] < 0:
                continue
            elif cj + way[1] >= w or cj + way[1] < 0:
                continue
            elif mapp[ci + way[0]][cj + way[1]] == '#':
                continue
            elif type(mapp[ci + way[0]][cj + way[1]]) == int:
                continue
            else:
                d.appendleft((ci + way[0], cj + way[1]))
                mapp[ci + way[0]][cj + way[1]] = cost
        if not d:
            break
        ci, cj = d[0][0], d[0][1]
        d.popleft()

    for way in warp_ways:
        if ci + way[0] >= h or ci + way[0] < 0:
            continue
        elif cj + way[1] >= w or cj + way[1] < 0:
            continue
        elif mapp[ci + way[0]][cj + way[1]] == '#':
            continue
        elif type(mapp[ci + way[0]][cj + way[1]]) == int:
            continue
        else:
            d.append((ci + way[0], cj + way[1]))
            continue
    if not d:
        break

    ci, cj = d[0][0], d[0][1]
    d.popleft()
    cost += 1
    mapp[ci][cj] = cost
if mapp[di][dj] == '.':
    print(-1)
else:
    print(mapp[di][dj])

Submission status: Wrong Answer

Solution code:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if -1 < dst[nh][nw] <= d: continue
        dq.appendleft((nh, nw, d))
        dst[nh][nw] = d

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        if -1 < dst[nh][nw] <= d + 1: continue
        dq.appendleft((nh, nw, d + 1))
        dst[nh][nw] = d + 1

print(dst[eh][ew])

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

h, w = map(int, input().split())
ci, cj = map(lambda x: int(x) - 1, input().split())
di, dj = map(lambda x: int(x) - 1, input().split())
mapp = []
for _ in range(h):
    mapp.append(list(input()))

walk_ways = [(-1, 0), (1, 0), (0, 1), (0, -1)]
warp_ways = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]

d = deque()
cost = 0
while 1:
    while 1:
        for way in walk_ways:
            if ci + way[0] >= h or ci + way[0] < 0:
                continue
            elif cj + way[1] >= w or cj + way[1] < 0:
                continue
            elif mapp[ci + way[0]][cj + way[1]] == '#':
                continue
            elif type(mapp[ci + way[0]][cj + way[1]]) == int:
                continue
            else:
                d.appendleft((ci + way[0], cj + way[1]))
                mapp[ci + way[0]][cj + way[1]] = cost
        if not d:
            break
        ci, cj = d[0][0], d[0][1]
        d.popleft()

    for way in warp_ways:
        if ci + way[0] >= h or ci + way[0] < 0:
            continue
        elif cj + way[1] >= w or cj + way[1] < 0:
            continue
        elif mapp[ci + way[0]][cj + way[1]] == '#':
            continue
        elif type(mapp[ci + way[0]][cj + way[1]]) == int:
            continue
        else:
            d.append((ci + way[0], cj + way[1]))
    if not d:
        break

    ci, cj = d[0][0], d[0][1]
    d.popleft()
    cost += 1
    mapp[ci][cj] = cost
if mapp[di][dj] == '.':
    print(-1)
else:
    print(mapp[di][dj])

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

h, w = map(int, input().split())
ci, cj = map(lambda x: int(x) - 1, input().split())
di, dj = map(lambda x: int(x) - 1, input().split())
mapp = []
for _ in range(h):
    mapp.append(list(input()))

walk_ways = [(-1, 0), (1, 0), (0, 1), (0, -1)]
warp_ways = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]

d = deque()
cost = 0
while 1:
    while 1:
        for way in walk_ways:
            if ci + way[0] >= h or ci + way[0] < 0:
                continue
            elif cj + way[1] >= w or cj + way[1] < 0:
                continue
            elif mapp[ci + way[0]][cj + way[1]] == '#':
                continue
            elif type(mapp[ci + way[0]][cj + way[1]]) == int:
                continue
            else:
                d.appendleft((ci + way[0], cj + way[1]))
                mapp[ci + way[0]][cj + way[1]] = cost
        if not d:
            break
        ci, cj = d[0][0], d[0][1]
        d.popleft()

    for way in warp_ways:
        if ci + way[0] >= h or ci + way[0] < 0:
            continue
        elif cj + way[1] >= w or cj + way[1] < 0:
            continue
        elif mapp[ci + way[0]][cj + way[1]] == '#':
            continue
        elif type(mapp[ci + way[0]][cj + way[1]]) == int:
            continue
        else:
            d.append((ci + way[0], cj + way[1]))
    if not d:
        break

    ci, cj = d[0][0], d[0][1]
    d.popleft()
    cost += 1
    mapp[ci][cj] = cost
print(mapp)
if mapp[di][dj] == '.':
    print(-1)
else:
    print(mapp[di][dj])

Submission status: Wrong Answer

Solution code:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
        for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])