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 = map(int,input().split())
INF = H+W
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
maze = []
maze.append(['#']*(W+2))
for i in range(H):
    maze.append(['#']+list(input())+['#'])
maze.append(['#']*(W+2))
dis = [[INF]*(W+2) for _ in range(H+2)]
d = deque()
nextd = []
dis[Ch][Cw] = 0
d.append((Ch,Cw))
dy = [0,1,0,-1]
dx = [1,0,-1,0]
cur = 0
while d:
    while d:
        y,x = d.popleft()
        if dis[y][x] == cur:
            for i in range(4):
                newy = y+dy[i]
                newx = x+dx[i]
                if maze[newy][newx] == '.':
                    if dis[newy][newx] > cur:
                        dis[newy][newx] = cur
                        d.append((newy,newx))
            for DY in range(-2,3):
                for DX in range(-2,3):
                    if abs(DX)+abs(DY) >= 2:
                        newy = y+DY
                        newx = x+DX
                        if newy <= H and newy >= 1 and newx <= W and newx >= 1: 
                            if maze[newy][newx] == '.':
                                if dis[newy][newx] > cur+1:
                                    dis[newy][newx] = cur+1
                                    nextd.append((newy,newx))
    cur += 1
    d = deque(nextd)
    nextd = []
if dis[Dh][Dw] == INF:
    print(-1)
else:
    print(dis[Dh][Dw])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h, w = LI()
    ch, cw = LI()
    dh, dw = LI_()
    # from time import time
    # st = time()
    s = SR(h)
    q = deque()
    c = defaultdict(lambda :inf)
    q.append((ch-1, cw-1))
    c[(ch - 1, cw - 1)] = 0
    nq = deque()
    nq.append((ch-1,cw-1))
    while 1:
        while q:
            nh, nw = q.popleft()
            now = c[(nh, nw)]
            for mh, mw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                mh += nh
                mw += nw
                if 0 <= mh < h and 0 <= mw < w and c[(mh, mw)] > now and s[mh][mw] == ".":
                    c[(mh, mw)] = now
                    q.appendleft((mh, mw))
                    nq.append((mh, mw))
        while nq:
            nh, nw = nq.popleft()
            now = c[(nh, nw)]
            for i in range(-2, 3):
                i += nh
                if 0 <= i < h:
                    si = s[i]
                    for j in range(-2, 3):
                        j += nw
                        if 0 <= i < h and 0 <= j < w and c[(i, j)] > now + 1 and si[j] == ".":
                            c[(i, j)] = now + 1
                            q.append((i, j))
        if len(q) == 0:
            break
    print(-1 if c[(dh, dw)] == inf else c[(dh, dw)])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(map(str, list(input()))) for i in range(H)]
floor = [[0] * W for i in range(H)]
floor[Ch-1][Cw-1] = 1


def water(x, y):

    if floor[y][x] != 0:

        # 上
        if y + 1 < H:
            if S[y + 1][x] != "#" and floor[y + 1][x] == 0:
                floor[y + 1][x] = floor[y][x]
                water(x, y + 1)
        # 下
        if y - 1 >= 0:
            if S[y - 1][x] != "#" and floor[y - 1][x] == 0:
                floor[y - 1][x] = floor[y][x]
                water(x, y - 1)
        # 右
        if x + 1 < W:
            if S[y][x + 1] != "#" and floor[y][x + 1] == 0:
                floor[y][x + 1] = floor[y][x]
                water(x + 1, y)
        # 左
        if x - 1 >= 0:
            if S[y][x - 1] != "#" and floor[y][x - 1] == 0:
                floor[y][x - 1] = floor[y][x]
                water(x - 1, y)


def warp(x, y, i):
    for Y in range(max(y - 2, 0), min(y + 2, H-1)+1):
        for X in range(max(x - 2, 0), min(x + 2, W-1)+1):
            if S[Y][X] != "#" and floor[Y][X] == 0:
                floor[Y][X] = i + 1
                water(X,Y)


# スタート地点に水を流す
water(Cw-1, Ch-1)
#print(floor)

# ワープ回数
for i in range(1, 100):
    for y in range(H):
        for x in range(W):
            if floor[y][x] == i:
                warp(x, y, i)
                water(x, y)

    if floor[Dh-1][Dw-1] != 0:
        print(floor[Dh-1][Dw-1]-1)
        #print(floor)
        sys.exit()

print("-1")

Submission status: Wrong Answer

Solution code:
import heapq
import sys
H, W = map(int, input().split())
C = tuple(int(x) - 1 for x in input().split())
D = tuple(int(x) - 1 for x in input().split())
S = [sys.stdin.readline() + "###" for _ in range(H)]
S.append("#" * (W + 3))
S.append("#" * (W + 3))

todo = []
heapq.heappush(todo, (0, C))
done = set()
while todo:
    count, p = heapq.heappop(todo)
    if p == D:
        print(count)
        break
    done.add(p)
    h, w = p
    pdone = {p}
    for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nh, nw = (h + dh, w + dw)
        if S[nh][nw] == "#":
            continue
        np = (nh, nw)
        pdone.add(np)
        if np in done:
            continue
        heapq.heappush(todo, (count, np))
    for nh in range(h - 2, h + 2 + 1):
        for nw in range(w - 2, w + 2 + 1):
            if S[nh][nw] == "#":
                continue
            np = (nh, nw)
            if np in done or np in pdone:
                continue
            heapq.heappush(todo, (count + 1, np))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

def solve():
    from collections import deque
    import heapq

    H, W = list(map(int, input().split()))
    Ch, Cw = list(map(int, input().split()))
    Ch, Cw = Ch-1, Cw-1
    Dh, Dw = list(map(int, input().split()))
    Dh, Dw = Dh-1, Dw-1
    S = []
    for _ in range(H):
        s = input()
        S.append(list(s))

    que = []
    heapq.heapify(que)
    heapq.heappush(que, [0, Ch, Cw])  # [ワープ回数, h座標, w座標]
    visited = set()
    while len(que) != 0:
        n, y, x = heapq.heappop(que)
        visited.add((y, x))

        # ゴールか？
        if y == Dh and x == Dw:
            print(n)
            return

        # 上下左右移動可能ならばqueに入れる
        for ny, nx in ([y-1, x], [y+1, x], [y, x-1], [y, x+1]):
            if 0 < ny < H and 0 < nx < W and not (ny, nx) in visited and S[ny][nx] == ".":
                heapq.heappush(que, [n, ny, nx])
        # ワープ可能位置をqueに入れる
        for ny, nx in ([y-2, x-2], [y-2, x-1], [y-2, x], [y-2, x+1], [y-2, x+2],
                       [y-1, x-2], [y-1, x-1], [y-1, x+1], [y-1, x+2],
                       [y, x-2], [y, x+2],
                       [y+2, x-2], [y+2, x-1], [y+2, x], [y+2, x+1], [y+2, x+2],
                       [y+1, x-2], [y+1, x-1], [y+1, x+1], [y+1, x+2]):
            if 0 < ny < H and 0 < nx < W and not (ny, nx) in visited and S[ny][nx] == ".":
                heapq.heappush(que, [n+1, ny, nx])

    # ゴールはたどり着かなかったよ・・・
    print(-1)
    return


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
INF = H+W
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
maze = []
maze.append(['#']*(W+2))
for i in range(H):
    maze.append(['#']+list(input())+['#'])
maze.append(['#']*(W+2))
dis = [[INF]*(W+2) for _ in range(H+2)]
d = deque()
nextd = []
dis[Ch][Cw] = 0
d.append((Ch,Cw))
dy = [0,1,0,-1]
dx = [1,0,-1,0]
cur = 0
while d:
    while d:
        y,x = d.popleft()
        if dis[y][x] == cur:
            for i in range(4):
                newy = y+dy[i]
                newx = x+dx[i]
                if maze[newy][newx] == '.':
                    if dis[newy][newx] > cur:
                        dis[newy][newx] = cur
                        d.append((newy,newx))
            for DY in range(-2,3):
                for DX in range(-2,3):
                    if abs(DX)+abs(DY) >= 2:
                        newy = y+DY
                        newx = x+DX
                        if newy <= H and newy >= 1 and newx <= W and newx >= 1: 
                            if maze[newy][newx] == '.':
                                if dis[newy][newx] > cur+1:
                                    dis[newy][newx] = cur+1
                                    nextd.append((newy,newx))
    cur += 1
    d = deque(nextd)
    nextd = []
print(dis[Dh][Dw])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
H, W = map(int, input().split())
sx, sy = map(int, input().split())
sx -= 1
sy -= 1
gx, gy = map(int, input().split())
gx -= 1
gy -= 1
map = [list(input()) for i in range(H)]
cost_map = [[10**5]*W for i in range(H)]
d = deque()
cost_map[sx][sy] = 0
d.append([sx, sy])
while d:
    cx, cy = d.pop()
    if cx==gx and cy==gy:
        break
    ccost = cost_map[cx][cy]
    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        nx = cx + dx
        ny = cy + dy
        if 0<=nx<H and 0<=ny<W:
            if map[nx][ny]=="." and ccost < cost_map[nx][ny]:
                cost_map[nx][ny] = ccost
                d.append([nx, ny])
    dxy = [[-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]]
    for dx, dy in dxy:
        nx = cx + dx
        ny = cy + dy
        if 0<=nx<H and 0<=ny<W:
            if map[nx][ny]=="." and (ccost + 1) < cost_map[nx][ny]:
                cost_map[nx][ny] = ccost + 1
                d.appendleft([nx, ny])
if cost_map[gx][gy] == 1000:
    print(-1)
else:
    print(cost_map[gx][gy])

Submission status: Wrong Answer

Solution code:
import sys

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(map(str, list(input()))) for i in range(H)]
floor = [[0] * W for i in range(H)]
floor[Ch-1][Cw-1] = 1


def water(x, y):

    if floor[y][x] != 0:

        # 上
        if y + 1 < H:
            if S[y + 1][x] != "#" and floor[y + 1][x] == 0:
                floor[y + 1][x] = floor[y][x]
                water(x, y + 1)
        # 下
        if y - 1 >= 0:
            if S[y - 1][x] != "#" and floor[y - 1][x] == 0:
                floor[y - 1][x] = floor[y][x]
                water(x, y - 1)
        # 右
        if x + 1 < W:
            if S[y][x + 1] != "#" and floor[y][x + 1] == 0:
                floor[y][x + 1] = floor[y][x]
                water(x + 1, y)
        # 左
        if x - 1 >= 0:
            if S[y][x - 1] != "#" and floor[y][x - 1] == 0:
                floor[y][x - 1] = floor[y][x]
                water(x - 1, y)


def warp(x, y, i):
    for Y in range(max(y - 2, 0), min(y + 2, H-1)+1):
        for X in range(max(x - 2, 0), min(x + 2, W-1)+1):
            if S[Y][X] != "#" and floor[Y][X] == 0:
                floor[Y][X] = i + 1
                water(X,Y)


# スタート地点に水を流す
water(Cw-1, Ch-1)
print(floor)

# ワープ回数
for i in range(1, 100):
    for y in range(H):
        for x in range(W):
            if floor[y][x] == i:
                warp(x, y, i)
                water(x, y)

    if floor[Dh-1][Dw-1] != 0:
        print(floor[Dh-1][Dw-1]-1)
        print(floor)
        sys.exit()

print("-1")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
    s.append(input().rstrip('\n'))

d = [[10 ** 18 for i in range(w)] for j in range(h)]

stack = deque([[ch-1, cw-1, 0]])

while stack:
    curh, curw, cnt = stack.popleft()
    if d[curh][curw] <= cnt:
        continue
    else:
        d[curh][curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh > 0 and nh < h and nw > 0 and nw < w and s[nh][nw] == '.':
            stack.append([nh, nw, cnt])
    for nh in range(curh-2, curh+3):
        if nh != curh and nh > 0 and nh < h:
            for nw in range(curw-2,curw+3):
                if nw != curw and nw > 0 and nw < w and s[nh][nw] == '.':
                     stack.append([nh, nw, cnt+1])

if d[gh-1][gw-1] == 10 ** 18:
    print(-1)
else:
    print(d[gh-1][gw-1])

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(h, w, maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx, 0]])
    visited[sy][sx] = 0
    while queue:
        y, x, worp = queue.popleft()
        if [y, x] == [gy, gx]:
            return worp
        walkable = False
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + k
            if new_y < 0 or new_y >= h or new_x < 0 or new_x >= w:
                continue
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x, worp])
                walkable = True

        if walkable is False:
            for s, t in (
                [1, 1],
                [1, -1],
                [-1, 1],
                [-1, -1],
                [2, 0],
                [2, 1],
                [2, -1],
                [2, 2],
                [2, -2],
                [1, 2],
                [1, -2],
                [0, 2],
                [0, -2],
                [-1, 2],
                [-1, -2],
                [-2, 0],
                [-2, 1],
                [-2, -1],
                [-2, 2],
                [-2, -2],
            ):
                new_y, new_x = y + s, x + t
                if new_y < 0 or new_y >= h or new_x < 0 or new_x >= w:
                    continue
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x, worp + 1])
    return -1


if __name__ == "__main__":
    h, w = map(int, input().split())
    ch, cw = map(lambda x: int(x) - 1, input().split())
    dh, dw = map(lambda x: int(x) - 1, input().split())
    s = [list(input()) for i in range(h)]
    visited = [[-1] * w for j in range(h)]
    print(bfs(h, w, s, visited, ch, cw, dh, dw))

Submission status: Wrong Answer

Solution code:
#create date: 2020-08-22 21:07

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    inf = 10**10
    h, w = na()
    ch, cw = na()
    ddh, ddw = na()
    g = '#' * (w + 4)
    g += '#' * (w + 4)
    for _ in range(h):
        g += '##' + ns() + '##'
    g += '#' * (w + 4)
    g += '#' * (w + 4)
    maze = [[inf] * (w+1) for i in range(h+1)]
    q = deque([(ch, cw)])
    maze[ch][cw] = 0
    move = (1, 0), (0, 1), (-1, 0), (0, -1)
    jump = (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)
    #print(len(g), g)

    while q:
        #print(q, maze)
        nh, nw = q.popleft()
        for ih, iw in move:
            dh, dw = nh + ih, nw + iw
            #print(dh, dw, dh*(w+4) + dw+1)
            if g[(dh-1+2)*(w+4) + dw+1] == ".":
                #print(dh, dw, dh*(w+4) + dw+1, g[:(dh-1+2)*(w+4) + dw+1+1])
                if maze[dh][dw] == inf:
                    q.append((dh, dw))
                    maze[dh][dw] = min(maze[dh][dw], maze[nh][nw])
        for ih, iw in jump:
            dh, dw = nh + ih, nw + iw
            if g[(dh-1+2)*(w+4) + dw+1] == ".":
                if maze[dh][dw]  > maze[nh][nw]+1:
                    q.append((dh, dw))
                    maze[dh][dw] = min(maze[dh][dw], maze[nh][nw]+1)
    if maze[ddh][ddw] == inf:
        print(-1)
    else:
        print(maze[ddh][ddw])



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
ch, cw = map(lambda x: int(x)-1, input().split())
dh, dw = map(lambda x: int(x)-1, input().split())
S = [list(input()) for _ in range(h)]

from collections import deque
# 座標, 座標, ワープカウント
q = deque([[ch, cw, 0]])
wall = deque()
visited = [[-1] * w for _ in range(h)]
visited[ch][cw] = 1
ans = -2
while True:
    while q:
        i, j, wc = q.popleft()
        if i == dh and j == dw:
            ans = wc
            break
        for mi, mj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            ni, nj = i + mi, j + mj
            if 0 <= nj < w and 0 <= ni < h:
                if S[ni][nj] == '.' and visited[ni][nj] == -1:
                    visited[ni][nj] = 1
                    q.append([ni, nj, wc])
                elif S[ni][nj] == '#':
                    wall.append([i, j, wc])
                    break
    else:
        if not wall:
            ans = -1
    if ans > -2:
        break

    while wall:
        i, j, wc = wall.popleft()
        for wi, wj in ((-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)):
            ni, nj = i+wi, j+wj
            if (0 <= nj < w and 0 <= ni < h and
                S[ni][nj] == '.' and visited[ni][nj] == -1):
                visited[ni][nj] = 1
                q.append([ni, nj, wc+1])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

h,w = list(map(int,input().split()))
s1,s2 = list(map(int,input().split()))
f1,f2 = list(map(int,input().split()))

s1,s2 = s1-1,s2-1
f1,f2 = f1-1,f2-1

Q = [(s1,s2)]
V = [[0]*w for _ in range(h)]
G = []
ALL = [(s1,s2)]
V[s1][s2] = 1

for _ in range(h):
  tmp = list(input().rstrip())
  G.append(tmp)

count = 0
best = 0

while True:
  while Q:
    new_Q = []
    for node in Q:
      i,j = node[0], node[1]
      if i-1>0:
        if V[i-1][j]==0 and G[i-1][j]=='.':
          V[i-1][j]=1
          new_Q.append((i-1,j))
          ALL.append((i-1,j))

      if j-1>0:
        if V[i][j-1]==0 and G[i][j-1]=='.':
          V[i][j-1]=1
          new_Q.append((i,j-1))
          ALL.append((i,j-1))

      if i+1<h:
        if V[i+1][j]==0 and G[i+1][j]=='.':
          V[i+1][j]=1
          new_Q.append((i+1,j))
          ALL.append((i+1,j))

      if j+1<w:
        if V[i][j+1]==0 and G[i][j+1]=='.':
          V[i][j+1]=1
          new_Q.append((i,j+1))
          ALL.append((i,j+1))

    Q = new_Q

  if V[f1][f2]==1:
    print(count)
    break
  else:
    temp = sum(sum(kk) for kk in V) 
    count += 1
    part= []
    
    for node in ALL:
      i,j = node[0], node[1]
      
      for x in range(i-2,i+3):
        for y in range(j-2,j+3):
          if x>-1 and y>-1 and x<h and y<w:
            if G[x][y] == '.':
              V[x][y] = 1
              part.append((x,y))
              
    part = list(set(part))
    ALL = list(part)

    if temp==best:
      print(-1)
      break
    else:
      best = temp

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int ,input().split())
    Dh, Dw = map(int, input().split())

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

    maze = list()
    arrived = [[0 for i in range(W)] for j in range(H)]
    arrived[Ch][Cw] = 1

    for i in range(H):
        maze.append(list(input()))

    ans = 0
    while (Ch != Dh) and (Cw != Dw):

        update_flag = 0

        if Cw + 1 < W and maze[Ch][Cw + 1] == "." and arrived[Ch][Cw + 1] == 0:
            Cw += 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Ch + 1 < H and maze[Ch + 1][Cw] == "." and arrived[Ch + 1][Cw] == 0:
            Ch += 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Cw - 1 > 0 and maze[Ch][Cw - 1] == "." and arrived[Ch][Cw - 1] == 0:
            Cw -= 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Ch - 1 > 0 and maze[Ch - 1][Cw] == "." and arrived[Ch - 1][Cw] == 0:
            Ch -= 1
            arrived[Ch][Cw] = 1
            update_flag = 1

        if update_flag == 0:
            find = 0

            for i in range(2, -3, -1):
                for j in range(2, -3, -1):
                    x = Cw + j
                    y = Ch + i

                    if 0 <= y < H and 0 <= x < W:
                        if y == Dh and x == Dw:
                            Ch = Dh
                            Cw = Dw
                            find = 1
                            ans += 1
                            update_flag = 1
                            break

                if find == 1:
                    break

            if update_flag == 0:
                for i in range(2, -3, -1):
                    for j in range(2, -3, -1):
                        x = Cw + j
                        y = Ch + i

                        if 0 <= y < H and 0 <= x < W:
                            if maze[y][x] == ".":
                                Ch = y
                                Cw = x
                                find = 1
                                ans += 1
                                break

                    if find == 1:
                            break
                    elif find == 0:
                        print(-1)
                        exit()
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
C = LIST()
D = LIST()
S = [input() for i in range(H)]

visited = [[False] * W for i in range(H)]
dist = [[INF] * W for i in range(H)]
q = deque([(C[0]-1, C[1]-1)])

dist[C[0]-1][C[1]-1] = 0
visited[C[0]-1][C[1]-1] = True
dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]
warp = [[-1] * W for i in range(H)]
warp[C[0]-1][C[1]-1] = 0
warp_time = 0
warp_stock = deque([])
while q:
    while q:
        ch, cw = q.popleft()
        warp_stock.append([ch, cw])

        dh = [0, 1, 0, -1]
        dw = [1, 0, -1, 0]


        for i in range(4):
            nh = ch + dh[i]
            nw = cw + dw[i]
            if 0 <= nh < H and 0 <= nw < W:
                if visited[nh][nw] == False and S[nh][nw] != "#":
                    dist[nh][nw] = dist[ch][cw] + 1
                    visited[nh][nw] = True
                    warp[nh][nw] = warp_time
                    q.append([nh, nw])
    while warp_stock:
        ch, cw = warp_stock.popleft()
        for dh in [-2, -1, 0, 1, 2]:
            for dw in [-2, -1, 0, 1, 2]:
                nh = ch + dh
                nw = cw + dw
                if 0 <= nh < H and 0 <= nw < W:
                    if visited[nh][nw] == False and S[nh][nw] != "#":
                        dist[nh][nw] = dist[ch][cw]
                        visited[nh][nw] = True
                        q.append([nh, nw])
                        warp[nh][nw] = warp[ch][cw] + 1
print(warp[D[0]-1][D[1]-1])

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
ch,cw = lr()
ch-=1
cw-=1
dh, dw = lr()
dh-=1
dw-=1
s = [input() for i in range(h)]
visited = [[inf for j in range(w)] for i in range(h)]
revisited = [[False for j in range(w)] for i in range(h)]
visited[ch][cw] = 0
q = deque([[ch, cw]])
dir = [[0,1], [0,-1], [-1,0], [1,0]]
while q:
    y,x = q.popleft()
    c = visited[y][x]
    for dy,dx in dir:
        ny,nx = y+dy,x+dx
        if 0<=ny<h and 0<=nx<w:
            if s[ny][nx] == '.':
                if visited[ny][nx] > c:
                    visited[ny][nx] = c
                    q.append([ny,nx])
    if not q:
        dq = deque([[y, x]])
        while dq:
            y,x = dq.popleft()
            revisited[y][x] = True
            # ワープ処理
            ty, tx = y-2, x-2
            for i in range(5):
                for j in range(5):
                    ny, nx = ty + i, tx + j
                    if 0<=ny<h and 0<=nx<w:
                        if s[ny][nx]=='.':
                            if visited[ny][nx] > c+1:
                                visited[ny][nx] = c+1
                                q.append([ny,nx])
                            elif visited[ny][nx] == c and revisited[ny][nx] == False:
                                revisited[ny][nx] = True
                                dq.append([ny,nx])
if visited[dh][dw] != inf:
    print(visited[dh][dw])
else:
    print(-1)