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 queue import PriorityQueue as pq
import sys


mod = 10**9 + 7
input = sys.stdin.readline

delta_u = [(1, 0), (0, 1), (-1, 0), (0, -1)]
delta2_u = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, 2), (0, -2), (0, 2), (1, -2), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]


def main():
    #
    H, W = map(int, input().strip().split())
    Ch, Cw = map(lambda x: int(x) - 1 + 2, input().strip().split())
    Dh, Dw = map(lambda x: int(x) - 1 + 2, input().strip().split())
    GRID = []
    ANS = []
    for i in range(H + 4):
        ANS.append([mod for _ in range(W + 4)])

    GRID.append("#" * (W + 4))
    GRID.append("#" * (W + 4))
    for i in range(H):
        S = "##" + input().strip() + "##"
        GRID.append(S)
    GRID.append("#" * (W + 4))
    GRID.append("#" * (W + 4))

    # eprint('GRID ',end=':\n')
    # pprint.pprint(GRID)
    # eprint('ANS ',end=':\n')
    # pprint.pprint(ANS)

    #
    PQ = pq()
    PQ.put((0, Ch, Cw))
    while not(PQ.empty()):
        distance, Uh, Uw = PQ.get()
        distance = -distance

        # ANS[Uh][Uw] の 「スコア」 の 「更新」
        if distance >= ANS[Uh][Uw]:
            continue
        ANS[Uh][Uw] = distance

        #
        for delta_h, delta_w in delta_u:
            new_distance = distance
            new_Uh = Uh + delta_h
            new_Uw = Uw + delta_w
            if GRID[new_Uh][new_Uw] == "#":    #
                continue
            if new_distance >= ANS[new_Uh][new_Uw]:  # 「新しい距離」 が，今までに記録していたその座標における「古い距離」 よりも大きくなってしまう場合，その新しい地点はキューに追加しない()
                continue
            PQ.put((-new_distance, new_Uh, new_Uw))

        for delta_h, delta_w in delta2_u:
            new_distance = distance + 1
            new_Uh = Uh + delta_h
            new_Uw = Uw + delta_w
            if GRID[new_Uh][new_Uw] == "#":    #
                continue
            if new_distance >= ANS[new_Uh][new_Uw]:  # 「新しい距離」 が，今までに記録していたその座標における「古い距離」 よりも大きくなってしまう場合，その新しい地点はキューに追加しない()
                continue
            PQ.put((-new_distance, new_Uh, new_Uw))

    if ANS[Dh][Dw] != sys.maxsize:
        print(ANS[Dh][Dw])
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
H , W  = (int(d) for d in input().split())
Ch, Cw = (int(d)-1 for d in input().split())
Dh, Dw = (int(d)-1 for d in input().split())

M = np.array(
    [
        [True if d == "." else False for d in input()] for j in range(H)
    ]
)

move1 = [[-1,0], [1,0], [0,-1], [0,1]]
move2 = [
    [-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],
]

seen = set()
dist = np.ones([H, W], dtype=int) * 1000000
Q = [(Ch, Cw)]
seen.update(Q)
dist[Ch, Cw] = 0

while len(Q) > 0:
    P = Q.pop()
    for i in range(4):
        a = P[0]+move1[i][0]
        b = P[1]+move1[i][1]
        if a >= 0 and a < H and b >=0 and b < W and M[a, b]:
            dist[a, b] = min(dist[P], dist[a,b])
            if not (a, b) in seen:
                seen.update([(a, b)])
                Q.append((a, b))
    for i in range(20):
        a = P[0]+move2[i][0]
        b = P[1]+move2[i][1]
        if a >= 0 and a < H and b >=0 and b < W and M[a, b]:
            dist[a, b] = min(dist[P] + 1, dist[a, b])
            if not (a, b) in seen:
                seen.update([(a, b)])
                Q.append((a, b))

D = dist[Dh, Dw]
if D == 1000000:
    print(-1)
else:
    print(D)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import deque
def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    maze = []
    dummy_row = ['#'] * (w + 4)
    maze.append(dummy_row)
    maze.append(dummy_row)
    for _ in range(h):
        row = ['#'] * 2 + list(input()) + ['#'] * 2
        maze.append(row)
    maze.append(dummy_row)
    maze.append(dummy_row)
    maze[ch + 1][cw + 1] = 0
    maze[dh + 1][dw + 1] = 'G'
    q = deque()
    q.append((ch+1, cw+1))
    r = float('inf')
    while q:
        koko = q.popleft()
        koko_y = koko[0]
        koko_x = koko[1]
        koko_num = maze[koko_y][koko_x]
        for j1 in range(koko_y - 1, koko_y + 2):
            for j2 in range(koko_x - 1, koko_x + 2):
                if maze[j1][j2] == 'G':
                    r = min(r, koko_num)
                elif maze[j1][j2] == '.':
                    maze[j1][j2] = koko_num
                    q.appendleft((j1, j2))
                elif type(maze[j1][j2]) == int:
                    if maze[j1][j2] > koko_num:
                        maze[j1][j2] = koko_num
                        q.appendleft((j1, j2))
        for i1 in range(koko_y - 2, koko_y + 3):
            for i2 in range(koko_x - 2, koko_x + 3):
                if maze[i1][i2] == 'G':
                    r = min(r, koko_num + 1)
                elif maze[i1][i2] == '.':
                    maze[i1][i2] = koko_num + 1
                    q.append((i1, i2))
                elif type(maze[i1][i2]) == int:
                    if maze[i1][i2] > koko_num + 1:
                        maze[i1][i2] = koko_num + 1
                        q.append((i1, i2))
    if r == float('inf'):
        print(-1)
    else:
        print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import deque
def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    maze = []
    dummy_row = ['#'] * (w + 4)
    maze.append(dummy_row)
    maze.append(dummy_row)
    for _ in range(h):
        row = ['#'] * 2 + list(input()) + ['#'] * 2
        maze.append(row)
    maze.append(dummy_row)
    maze.append(dummy_row)
    maze[ch + 1][cw + 1] = 0
    maze[dh + 1][dw + 1] = 'G'
    q = deque()
    q.append((ch+1, cw+1))
    r = float('inf')
    while q:
        koko = q.popleft()
        koko_y = koko[0]
        koko_x = koko[1]
        koko_num = maze[koko_y][koko_x]
        for j1 in range(koko_y - 1, koko_y + 2):
            for j2 in range(koko_x - 1, koko_x + 2):
                if maze[j1][j2] == 'G':
                    r = min(r, koko_num)
                elif maze[j1][j2] == '.':
                    maze[j1][j2] = koko_num
                    q.appendleft((j1, j2))
                elif type(maze[j1][j2]) == int:
                    if maze[j1][j2] > koko_num:
                        maze[j1][j2] = koko_num
                        q.appendleft((j1, j2))
        for i1 in range(koko_y - 2, koko_y + 3):
            for i2 in range(koko_x - 2, koko_x + 3):
                if maze[i1][i2] == 'G':
                    r = min(r, koko_num + 1)
                elif maze[i1][i2] == '.':
                    maze[i1][i2] = koko_num + 1
                    q.append((i1, i2))
                elif type(maze[i1][i2]) == int:
                    if maze[i1][i2] > koko_num + 1:
                        maze[i1][i2] = koko_num + 1
                        q.appendleft((i1, i2))
    if r == float('inf'):
        print(-1)
    else:
        print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import deque
def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    maze = []
    dummy_row = ['#'] * (w + 4)
    maze.append(dummy_row)
    maze.append(dummy_row)
    for _ in range(h):
        row = ['#'] * 2 + list(input()) + ['#'] * 2
        maze.append(row)
    maze.append(dummy_row)
    maze.append(dummy_row)
    maze[ch + 1][cw + 1] = 0
    maze[dh + 1][dw + 1] = 'G'
    q = deque()
    q.append((ch+1, cw+1))
    while q:
        koko = q.popleft()
        koko_y = koko[0]
        koko_x = koko[1]
        koko_num = maze[koko_y][koko_x]
        for j1 in range(koko_y - 1, koko_y + 2):
            for j2 in range(koko_x - 1, koko_x + 2):
                if maze[j1][j2] == 'G':
                    print(koko_num)
                    sys.exit()
                elif maze[j1][j2] == '.':
                    maze[j1][j2] = koko_num
                    q.appendleft((j1, j2))
                elif type(maze[j1][j2]) == int:
                    if maze[j1][j2] > koko_num:
                        maze[j1][j2] = koko_num
                        q.appendleft((j1, j2))
        for i1 in range(koko_y - 2, koko_y + 3):
            for i2 in range(koko_x - 2, koko_x + 3):
                if maze[i1][i2] == 'G':
                    print(koko_num + 1)
                    sys.exit()
                elif maze[i1][i2] == '.':
                    maze[i1][i2] = koko_num + 1
                    q.append((i1, i2))
                elif type(maze[i1][i2]) == int:
                    if maze[i1][i2] > koko_num + 1:
                        maze[i1][i2] = koko_num + 1
                        q.appendleft((i1, i2))
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import deque
def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    maze = []
    dummy_row = ['#'] * (w + 4)
    maze.append(dummy_row)
    maze.append(dummy_row)
    for _ in range(h):
        row = ['#'] * 2 + list(input()) + ['#'] * 2
        maze.append(row)
    maze.append(dummy_row)
    maze.append(dummy_row)
    maze[dh + 1][dw + 1] = 'G'
    maze[ch + 1][cw + 1] = 0
    q = deque()
    q.append((ch+1, cw+1))
    while q:
        koko = q.popleft()
        koko_y = koko[0]
        koko_x = koko[1]
        flag = True
        for j1 in range(-1, 2):
            for j2 in range(-1, 2):
                if maze[koko_y + j1][koko_x + j2] == 'G':
                    print(maze[koko_y][koko_x])
                    sys.exit()
                elif maze[koko_y+j1][koko_x+j2] == '.':
                    maze[koko_y + j1][koko_x + j2] = maze[koko_y][koko_x]
                    q.appendleft((koko_y + j1, koko_x + j2))
                    flag = False
        if flag:
            for i1 in range(-2, 3):
                for i2 in range(-2, 3):
                    if maze[koko_y + i1][koko_x + i2] == 'G':
                        print(maze[koko_y][koko_x] + 1)
                        sys.exit()
                    elif maze[koko_y + i1][koko_x + i2] == '.':
                        maze[koko_y + i1][koko_x + i2] = maze[koko_y][koko_x] + 1
                        q.append((koko_y + i1, koko_x + i2))
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import deque
def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    maze = []
    dummy_row = ['#'] * (w + 4)
    maze.append(dummy_row)
    maze.append(dummy_row)
    for _ in range(h):
        row = ['#'] * 2 + list(input()) + ['#'] * 2
        maze.append(row)
    maze.append(dummy_row)
    maze.append(dummy_row)
    maze[dh + 1][dw + 1] = 'G'
    maze[ch + 1][cw + 1] = 0
    q = deque()
    q.append((ch+1, cw+1))
    while q:
        koko = q.popleft()
        for j1 in range(-1, 2):
            for j2 in range(-1, 2):
                if maze[koko[0]+j1][koko[1]+j2] == 'G':
                    print(maze[koko[0]][koko[1]])
                    sys.exit()
                elif maze[koko[0]+j1][koko[1]+j2] == '.':
                    maze[koko[0] + j1][koko[1] + j2] = maze[koko[0]][koko[1]]
                    q.appendleft((koko[0]+j1, koko[1]+j2))
                elif type(maze[koko[0]+j1][koko[1]+j2]) == int:
                    if maze[koko[0]+j1][koko[1]+j2] > maze[koko[0]][koko[1]]:
                        maze[koko[0] + j1][koko[1] + j2] = maze[koko[0]][koko[1]]
                        q.appendleft((koko[0] + j1, koko[1] + j2))
        for i1 in range(-2, 3):
            for i2 in range(-2, 3):
                if maze[koko[0]+i1][koko[1]+i2] == 'G':
                    print(maze[koko[0]][koko[1]] + 1)
                    sys.exit()
                elif maze[koko[0]+i1][koko[1]+i2] == '.':
                    maze[koko[0] + i1][koko[1] + i2] = maze[koko[0]][koko[1]] + 1
                    q.append((koko[0]+i1, koko[1]+i2))
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h , w = map(int, input().split())
start_y, start_x = map(int, input().split())
end_y, end_x = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
cost = [[float('inf') for i in range(w)] for j in range(h)]

def bfs():
    que = deque()
    que.append((start_x-1, start_y-1,0))
    finished = set()
    while que:
        x, y, c = que.popleft()
        if (x, y) in finished:
            continue
        finished.add((x,y))
        if not ((0 <= y < h) and (0 <= x < w)) :
            continue
        if grid[y][x] == '#':
            continue
        if cost[y][x] <= c:
            continue
        cost[y][x] = c
        for n_x, n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
            if (n_x,n_y) not in finished:
                que.appendleft((n_x, n_y, c))
                finished.add((n_x, n_y))
        for i in range(-2,3):
            for j in range(-2,3):
                if (x+i,y+j) not in finished:
                    que.append((x+i,y+j,c+1))
bfs()

if cost[end_y-1][end_x-1] == float('inf'):
    print(-1)
    exit()
print(cost[end_y-1][end_x-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

h , w = map(int, input().split())
start_y, start_x = map(int, input().split())
end_y, end_x = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
cost = [[float('inf') for i in range(w)] for j in range(h)]

def bfs():
    que = deque()
    que.append((start_x-1, start_y-1,0))
    finished = set()
    while que:
        x, y, c = que.popleft()
        if (x, y) in finished:
            continue
        if not ((0 <= y < h) and (0 <= x < w)) :
            continue
        if grid[y][x] == '#':
            continue
        if cost[y][x] <= c:
            continue
        cost[y][x] = c
        for n_x, n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
            if (n_x,n_y) not in finished:
                que.appendleft((n_x, n_y, c))
                finished.add((n_x, n_y))
        for i in range(-2,3):
            for j in range(-2,3):
                if (x+i,y+j) not in finished:
                    que.append((x+i,y+j,c+1))
bfs()
if cost[end_y-1][end_x-1] == float('inf'):
    print(-1)
    exit()
print(cost[end_y-1][end_x-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

h , w = map(int, input().split())
start_y, start_x = map(int, input().split())
end_y, end_x = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
cost = [[float('inf') for i in range(w)] for j in range(h)]

def bfs():
    que = deque()
    que.append((start_x-1, start_y-1,0))
    finished = set()
    while que:
        x, y, c = que.popleft()
        if not ((0 <= y < h) and (0 <= x < w)) :
            continue
        if grid[y][x] == '#':
            continue
        if cost[y][x] <= c:
            continue
        cost[y][x] = c
        for n_x, n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
            if (n_x,n_y) not in finished:
                que.appendleft((n_x, n_y, c))
                finished.add((n_x,n_y))
        for i in range(-2,3):
            for j in range(-2,3):
                if (x+i,y+j) not in finished:
                    que.append((x+i,y+j,c+1))
                    finished.add((x+i,y+j))

bfs()
if cost[end_y-1][end_x-1] == float('inf'):
    print(-1)
    exit()
print(cost[end_y-1][end_x-1])

Submission status: Wrong Answer

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

def main():
    h, w = map(int,input().split())
    h += 4
    w += 4
    C_h, C_w = map(int,input().split())
    C_h += 1
    C_w += 1
    D_h, D_w = map(int,input().split())
    D_h += 1
    D_w += 1
    S = ["#"*w for hh in range(h)]
    for hh in range(2, h-2):
        S[hh] = "##" + input() + "##"
    queue=deque([C_h*w + C_w])
    ans = [100000000]*(h*w)
    ans[C_h*w + C_w] = 0
    while queue:
        node = queue.popleft()
        node_h = node//w
        for xnode in (node - 1, node + 1, node + w, node - w):
            xnode_h = xnode//w
            xnode_w = xnode%w
            if S[xnode_h][xnode_w] == "." and ans[xnode] != 0:
                ans[xnode] = 0
                queue.append(xnode)
    queue = deque([C_h*w + C_w])
    visited = [False]*(h*w)
    visited[C_h*w + C_w] = True
    while queue:
        node = queue.popleft()
        node_h = node//w
        node_w = node%w
        for xnode_h in (node_h - 2, node_h - 1, node_h, node_h + 1, node_h + 2):
            for xnode_w in (node_w - 2, node_w - 1, node_w, node_w + 1, node_w + 2):
                xnode = xnode_h*w + xnode_w
                if S[xnode_h][xnode_w] == "." and not visited[xnode]:
                    ans[xnode] = min(ans[xnode], ans[node] + 1)
                    queue.append(xnode)
                    visited[xnode] = True
#    for i in range(h):
#        print(ans[w*i:w*(i+1)])
    gnode = D_h*w + D_w
    if visited[gnode]:
        print(ans[D_h*w + D_w])
    else:
        print(-1)
        
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

def main():
    h, w = map(int,input().split())
    h += 4
    w += 4
    C_h, C_w = map(int,input().split())
    C_h += 1
    C_w += 1
    D_h, D_w = map(int,input().split())
    D_h += 1
    D_w += 1
    S = ["#"*w for hh in range(h)]
    for hh in range(2, h-2):
        S[hh] = "##" + input() + "##"
    queue=deque([C_h*w + C_w])
    ans = [-1]*(h*w)
    ans[C_h*w + C_w] = 0
    while queue:
        node = queue.popleft()
        node_h = node//w
        for xnode in (node - 1, node + 1, node + w, node - w):
            xnode_h = xnode//w
            xnode_w = xnode%w
            if S[xnode_h][xnode_w] == "." and ans[xnode] == -1:
                ans[xnode] = 0
                queue.append(xnode)
    queue = deque([C_h*w + C_w])
    visited = [False]*(h*w)
    visited[C_h*w + C_w] = True
    while queue:
        node = queue.popleft()
        node_h = node//w
        node_w = node%w
        for xnode_h in (node_h - 2, node_h - 1, node_h, node_h + 1, node_h + 2):
            for xnode_w in (node_w - 2, node_w - 1, node_w, node_w + 1, node_w + 2):
                xnode = xnode_h*w + xnode_w
                if S[xnode_h][xnode_w] == "." and not visited[xnode]:
                    if ans[xnode] == -1: #魔法1で行けてない
                        ans[xnode] = ans[node] + 1
                    else:
                        ans[xnode] = min(ans[xnode], ans[node] + 1)
                    queue.append(xnode)
                    visited[xnode] = True
    print(ans[D_h*w + D_w])
        
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

def main():
    h, w = map(int,input().split())
    h += 4
    w += 4
    C_h, C_w = map(int,input().split())
    C_h += 1
    C_w += 1
    D_h, D_w = map(int,input().split())
    D_h += 1
    D_w += 1
    S = ["#"*w for hh in range(h)]
    for hh in range(2, h-2):
        S[hh] = "##" + input() + "##"
    queue=deque([C_h*w + C_w])
    ans = [-1]*(h*w)
    ans[C_h*w + C_w] = 0
    while queue:
        node = queue.popleft()
        node_h = node//w
        for xnode in (node - 1, node + 1, node + w, node - w):
            xnode_h = xnode//w
            xnode_w = xnode%w
            if S[xnode_h][xnode_w] == "." and ans[xnode] == -1:
                ans[xnode] = 0
                queue.append(xnode)
            if xnode == D_h*w + D_w:
                print(0)
                sys.exit()
    queue = deque([C_h*w + C_w])
    visited = [False]*(h*w)
    visited[C_h*w + C_w] = True
    while queue:
        node = queue.popleft()
        node_h = node//w
        node_w = node%w
        for xnode_h in (node_h - 2, node_h - 1, node_h, node_h + 1, node_h + 2):
            for xnode_w in (node_w - 2, node_w - 1, node_w, node_w + 1, node_w + 2):
                xnode = xnode_h*w + xnode_w
                if S[xnode_h][xnode_w] == "." and not visited[xnode]:
                    if ans[xnode] == -1:
                        ans[xnode] = ans[node] + 1
                    else:
                        ans[xnode] = min(ans[xnode], ans[node] + 1)
                    queue.append(xnode)
                    visited[xnode] = True
                if xnode == D_h*w + D_w:
                    print(ans[xnode])
                    sys.exit()
    print(-1)
        
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

def main():
    h, w = map(int,input().split())
    h += 4
    w += 4
    C_h, C_w = map(int,input().split())
    C_h += 1
    C_w += 1
    D_h, D_w = map(int,input().split())
    D_h += 1
    D_w += 1
    S = ["#"*w for hh in range(h)]
    for hh in range(2, h-2):
        S[hh] = "##" + input() + "##"
    queue=deque([C_h*w + C_w])
    ans = [-1]*(h*w)
    ans[C_h*w + C_w] = 0
    while queue:
        node = queue.popleft()
        node_h = node//w
        for xnode in (node - 1, node + 1, node + w, node - w):
            xnode_h = xnode//w
            xnode_w = xnode%w
            if S[xnode_h][xnode_w] == "." and ans[xnode] == -1:
                ans[xnode] = 0
                queue.append(xnode)
            if xnode == D_h*w + D_w:
                print(0)
                break
    else:
        queue = deque([C_h*w + C_w])
        visited = [False]*(h*w)
        visited[C_h*w + C_w] = True
        while queue:
            node = queue.popleft()
            node_h = node//w
            node_w = node%w
            for xnode_h in (node_h - 2, node_h - 1, node_h, node_h + 1, node_h + 2):
                for xnode_w in (node_w - 2, node_w - 1, node_w, node_w + 1, node_w + 2):
                    xnode = xnode_h*w + xnode_w
                    if S[xnode_h][xnode_w] == "." and not visited[xnode]:
                        if ans[xnode] == -1:
                            ans[xnode] = ans[node] + 1
                        else:
                            ans[xnode] = min(ans[xnode], ans[node] + 1)
                        queue.append(xnode)
                        visited[xnode] = True
                    if xnode == D_h*w + D_w:
                        print(ans[xnode])
                        sys.exit()
        print(-1)
        
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
G[sy][sx] = '#'
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    d = D[y][x]
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx+dy==0:
            G[y][x] = '#'
        elif any((ny<0, h<=ny, nx<0, w<=nx)):
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1 and D[ny][nx] > d:
            G[ny][nx] = '#'
            D[ny][nx] = d
            Q.append((ny, nx))
        elif D[ny][nx] > d+1:
            D[ny][nx] = d+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
G[sy][sx] = '#'
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    d = D[y][x]
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if any((ny<0, h<=ny, nx<0, w<=nx)):
            continue
        elif G[ny][nx] == '#':
            continue
        elif dx+dy==0:
            G[y][x] = '#'
        elif abs(dy)+abs(dx)<=1 and D[ny][nx] > d:
            G[ny][nx] = '#'
            D[ny][nx] = d
            Q.append((ny, nx))
        elif D[ny][nx] > d+1:
            D[ny][nx] = d+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx+dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] > D[y][x]+1:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = []
for _ in range(h):
    G.append(list(input()))
D = [[10**6]*w for i in range(h)]
D[sy][sx] = 0
Q = deque()
Q.append((sy, sx))

while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx+dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dx)+abs(dy)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] > D[y][x]+1:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Submission status: Wrong Answer

Solution code:
from itertools import product
from collections import deque
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x, space=1):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
        self.space = space
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join(''.join(f'{{: >{self.space}}}'.format(x) for x in row) for row in self.grid) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def bfs_01(G, start, goal):
    Q = deque([start])
    x, y = start
    D = Grid(G.grid, function=lambda x:-9 if x=='#' else 10, space=4)
    D[y, x] = 0
    
    walk = list(zip([1, 0, -1, 0], [0, 1, 0, -1]))
    warp = [(dx, dy) for dx, dy in product(range(-2, 3), repeat=2)
            if abs(dx)+abs(dy) >= 2]
    while Q:
        x, y = Q.pop()
        if G[y, x] == '!':
            continue
        d = D[y, x]
        G[y, x] = '!'
        
        for dx, dy in walk:
            nx, ny = x+dx, y+dy
            if G.is_valid_xy(nx, ny) and G[ny, nx]=='.' and D[ny, nx] > d:
                D[ny, nx] = d
                Q.append((nx, ny))
        for dx, dy in warp:
            nx, ny = x+dx, y+dy                
            if G.is_valid_xy(nx, ny) and G[ny, nx]=='.' and D[ny, nx] > d+1:
                D[ny, nx] = d+1
                Q.appendleft((nx, ny))
    x, y = goal
    return D[y, x]

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
grid = Grid([input() for s in range(h)], space=4)
ans = bfs_01(grid, (sx, sy), (gx, gy))
print(ans if ans != 10**6 else -1)