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())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
ch-=1
cw-=1
dh-=1
dw-=1

maze=[list(input()) for i in range(h)]
distance=[[10**10 for j in range(w)] for i in range(h)]
visited=[[False]*w for i in range(h)]

distance[ch][cw]=0


Q=deque()
Q.append((ch,cw))


while Q:
  p=Q.popleft()
  visited[p[0]][p[1]]=True

  if p[0]==dh and p[1]==dw:
    break
  
  dx=[1,1,-1,-1]
  dy=[-1,1,-1,1]
  dddx=[2,2,2,2,2,1,1,1,1,1,0,0,0,0,-1,-1,-1,-1,-1,-2,-2,-2,-2,-2]
  dddy=[2,1,0,-1,-2,2,1,0,-1,-2,2,1,-1,-2,2,1,0,-1,-2,2,1,0,-1,-2]

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

    if 0<=nx<h and 0<=ny<w and visited[nx][ny]==False and maze[nx][ny]!='#':
      Q.appendleft((nx,ny))
      distance[nx][ny]=min(distance[p[0]][p[1]],distance[nx][ny])

  
  for j in range(24):
    nnnx=p[0]+dddx[j]
    nnny=p[1]+dddy[j]

    if 0<=nnnx<h and 0<=nnny<w and visited[nnnx][nnny]==False and maze[nnnx][nnny]!='#':
      Q.append((nnnx,nnny))
      distance[nnnx][nnny]=min(distance[nnnx][nnny],distance[p[0]][p[1]]+1)


if distance[dh][dw]==10**10:
  print(-1)
  exit()


print(distance[dh][dw])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    def warp(cury2, curx2):
        curg2 = maze[cury2][curx2]
        nexts2 = []
        for j1 in range(20):
            nexty2 = cury2 + warpy[j1]
            nextx2 = curx2 + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                sys.exit()
            elif nextg2 == '#':
                pass
            elif nextg2 == '.':
                maze[nexty2][nextx2] = curg2 + 1
                nexts2.append((nexty2, nextx2))
        return nexts2

    def dfs1(cury, curx):
        flag = False
        curg = maze[cury][curx]
        for i1 in range(4):
            nexty = cury + movey[i1]
            nextx = curx + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                dfs1(nexty, nextx)
            elif nextg == '#':
                flag = True
        if flag:
            nexts = warp(cury, curx)
            if nexts:
                for ne in nexts:
                    dfs1(ne[0], ne[1])

    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
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'
    dfs1(ch, cw)
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
S=[list(input()) for _ in range(H)]
d={(CH-1,CW-1):0}
q=[(CH-1,CW-1,0)]
def tryAppend(h,w,c):
    if 0<=h<H:
        if 0<=w<W:
            if S[h][w]=='.':
                p=(h,w)
                if p in d:
                    d[p]=min(d[p],c)
                else:
                    d[p]=c
                    q.append((h,w,c))
                    return True
    return False
while q:
    (h,w,c)=q.pop(0)
    # walk
    hit=False
    hit|=tryAppend(h-1,w,c)
    hit|=tryAppend(h,w-1,c)
    hit|=tryAppend(h+1,w,c)
    hit|=tryAppend(h,w+1,c)
    if hit:
        continue
    # warp
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                tryAppend(h+i,w+j,c+1)
p = (DH-1,DW-1)
if p in d:
    print(d[p])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
S=[list(input()) for _ in range(H)]
d={(CH-1,CW-1):0}
q=[(CH-1,CW-1,0)]
def tryAppend(h,w,c):
    if 0<=h<H:
        if 0<=w<W:
            if S[h][w]=='.':
                p=(h,w)
                if p in d:
                    d[p]=min(d[p],c)
                else:
                    d[p]=c
                    q.append((h,w,c))
                    return True
    return False
while q:
    (h, w, c) = q.pop(0)
    # walk
    tryAppend(h-1,w,c)
    tryAppend(h,w-1,c)
    tryAppend(h+1,w,c)
    tryAppend(h,w+1,c)
    # warp
    for i in range(-2, 3):
        for j in range(-2, 3):
            tryAppend(h+i,w+j,c+1)
p = (DH-1,DW-1)
if p in d:
    print(d[p])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
S=[list(input()) for _ in range(H)]
d={(CH-1,CW-1):0}
q=[(CH-1,CW-1,0)]
def tryAppend(h,w,c):
    if 0 <= h < H:
        if 0 <= w < W:
            if S[h][w] == '.':
                p = (h,w)
                if p in d:
                    d[p] = min(d[p], c)
                else:
                    d[p] = c
                    q.append((h,w,c))
                    return True
    return False
while q:
    (h, w, c) = q.pop(0)
    print(h,w,c)
    # walk
    tryAppend(h-1,w,c)
    tryAppend(h,w-1,c)
    tryAppend(h+1,w,c)
    tryAppend(h,w+1,c)
    # warp
    for i in range(-2, 3):
        for j in range(-2, 3):
            tryAppend(h+i,w+j,c+1)
p = (DH-1,DW-1)
if p in d:
    print(d[p])
else:
    print(-1)

Submission status: Wrong Answer

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

field = {}

for y in range(1, H + 1):
    l = list(input())
    field[y] = {}
    for x in range(1, W + 1):
        field[y][x] = l[x - 1]

x = [1, 0, -1, 0]
y = [0, -1, 0, 1]

wx = [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, -2, -2, -2, -2, -2, -1, - 1, - 1, - 1, - 1]
wy = [2, 1, 0, -1, -2, 2, 1, 0, -1, -2, 2, 1, 0, -1, -2, 2, 1, 0, -1, -2, 2, 1, 0, -1, -2]

searchedArea = set()
canMove = set()
canWarp = []
moved = set()
moved.add((Ch, Cw))
ans = [0]


# 探索
# add canM
# if not (canM  - moved) : return canM
# for (x, y) in canM:

def searchCanM(x, y, xs, ys, length):
    if 0 < y <= H and 0 < x <= W and field[y][x] == '#':
        return

    moved.add((x, y))

    for i in range(0, length):
        xx = xs[i]
        yy = ys[i]
        if moved.__contains__((xx, yy)):
            continue
        canMove.add((xx, yy))
        searchCanM(xx, yy, xs, ys, length)

    return moved


searchCanM(Ch, Cw, x, y, 4)
tmp = 0
# while moved.__len__() != canMove.__len__():
#     ll = list(canMove)
#     for c in ll:
#         moved.add(c)
#         cy, cx = c
#         searchCanM(cy, cx, x, y, 4)

if canMove.__contains__((Dh, Dw)):
    ans.append(tmp)

# canMove.clear()
print(canMove)
print(min(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np



dx=[0,1,-1,0]
dy=[1,0,0,-1]
d2=[-2,-1,0,1,2]
que=[]
q2=[]
def warp(x):
  ch,cw=x
  dis=seen[ch][cw]
  for i in d2:
    for j in d2:
      nh=ch+i
      nw=cw+j
      if nh<0 or nh>=h or nw<0 or nw>=w:
        continue
      if field[nh][nw]=="#" or seen[nh][nw]!=0:
        continue
      seen[nh][nw]=int(dis+1)
      que.append((nh,nw))
      q2.append((nh,nw))
def bfs(x):
  ch,cw=x
  dis=seen[ch][cw]
  for i in range(0,4):
    nh=ch+dx[i]
    nw=cw+dy[i]
    if nh<0 or nh>=h or nw<0 or nw>=w:
      continue
    if field[nh][nw]=="#" or seen[nh][nw]<=dis:
      if field[nh][nw]=="#":
        seen[nh][nw]=-1
      continue
    seen[nh][nw]=int(dis)
    que.append((nh,nw))
    q2.append((nh,nw))
def grinp(h):
  ret=[]
  for i in range(h):
    ret.append(list(input()))
  return ret
def mapcnt():
  ret=0
  for i in seen:
    for j in i:
      if j==0:
        ret+=1
  return ret


h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
field=grinp(h)
seen=np.zeros((h,w))
seen[sh-1][sw-1]=1
que.append((sh-1,sw-1))
q2.append((sh-1,sw-1))
lm=np.array([[-1]])
endf=False
while mapcnt()!=0:
  while len(que)!=0:
    bfs(que.pop(0))
  while len(q2)!=0:
    warp(q2.pop(0))
  if len(que)==0:
    break
ans=int(seen[gh-1][gw-1])-1
  
print(ans)
#print(seen)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, C, D, S):
    q = deque()
    q.append((0, C))
    memo = {}
    T = 10**6
    while q:
        c, (x, y) = q.popleft()
        if (x*T + y) in memo:
            continue
        memo[x*T + y] = c

        for nx in range(x-2, x+3):
            for ny in range(y-2, y+3):
                if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                    if abs(nx-x) + abs(ny-y) == 1:
                        q.appendleft((c, (nx, ny)))
                    else:
                        q.append((c+1, (nx, ny)))

    return -1 if (D[0]*T + D[1]) not in memo else memo[D[0]*T + D[1]]


def main():
    H, W = read_int_n()
    C = read_int_n()
    D = read_int_n()
    S = [read_str() for _ in range(H)]
    print(slv(H, W, C, D, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

"""
l = [list(input().strip()) for i in range(h)]
ans = [[-1]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            ans[i][j] = -2
ch -= 1
cw -= 1
dh -= 1
dw -= 1
"""

base = ["#" * (w + 4)]
base.append("#" * (w + 4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w + 4))
base.append("#" * (w + 4))
ans = [[-1] * (w + 4) for _ in range(h + 4)]
for i in range(h + 4):
    for j in range(w + 4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch += 1
cw += 1
dh += 1
dw += 1

ans[ch][cw] = 0
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]
        ]
q1 = deque([[ch, cw]])
q2 = deque([])

while q1:
    x1, y1 = q1.popleft()
    q2.append([x1, y1])
    for i, j in move1:
        nx, ny = x1 + i, y1 + j
        if nx < 0 or h <= nx or ny < 0 or w <= ny:
            continue
        if ans[nx][ny] == -1:
            ans[nx][ny] = ans[x1][y1]
            q1.append([nx, ny])
    if len(q1) == 0:
        while q2:
            x2, y2 = q2.popleft()
            for i, j in move2:
                mx, my = x2 + i, y2 + j
                if mx < 0 or h <= mx or my < 0 or w <= my:
                    continue
                if ans[mx][my] == -1:
                    ans[mx][my] = ans[x2][y2] + 1
                    q1.append([mx, my])
print(ans[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
INF=float("inf")

H,W=map(int,readline().split())
Ch,Cw=map(lambda x: int(x) - 1, readline().split())
Dh,Dw=map(lambda x: int(x) - 1, readline().split())
maze=list(map(str,read().rstrip().decode().split()))

path=[[INF]*W for _ in range(H)]
walk=[(1,0),(0,-1),(-1,0),(0,1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if not (i, j) in [(0, 0)] + walk]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s)) 
    for dx, dy in warp: 
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1)) 
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'

Submission status: Wrong Answer

Solution code:
import sys, math
import io, os
data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
#def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


h,w=mdata()
ch,cw=mdata()
dh,dw=mdata()
ch,cw,dh,dw=ch-1,cw-1,dh-1,dw-1
S=[data() for i in range(h)]
steps=[(0,1),(1,0),(-1,0),(0,-1)]
dist=[[INF]*w for i in range(h)]
dist[ch][cw]=0

queue = deque()
queue.append((ch, cw))
while queue:
    u, v = queue.popleft()
    d=dist[u][v]
    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= u + i < h and 0 <= v + j < w and S[u + i][v + j] == '.':
                if (i,j) in steps:
                    if d < dist[u+i][v+j]:
                        dist[u+i][v+j] = d
                        queue.appendleft((u+i,v+j))
                else:
                    if 1 + d < dist[u + i][v + j]:
                        dist[u + i][v + j] = 1 + d
                        queue.append((u + i, v + j))


if dist[dh][dw]!=INF:
    out(dist[dh][dw])
else:
    out(-1)

Submission status: Wrong Answer

Solution code:
# D - Wizard in Maze
import sys
from collections import deque
from typing import List, Tuple


class WarpableMaze:
    __slots__ = ["height", "width", "road", "wall", "grid"]

    def __init__(
        self,
        height: int,
        width: int,
        grid: List[str],
        road: str = ".",
        wall: str = "#",
    ) -> None:
        # Values of start and goal must be 0-origin.
        self.height = height + 4
        self.width = width + 4
        self.road = road
        self.wall = wall
        self.grid = self._flatten_grid(grid)

    def _flatten_grid(self, grid: List[str]) -> str:
        flat_grid = self.wall * self.width * 2
        for row in grid:
            flat_grid += self.wall * 2 + row + self.wall * 2
        flat_grid += self.wall * self.width * 2
        return flat_grid

    def _flatten_dxy(self, x: int, y: int) -> int:
        return self.width * x + y

    def _flatten_coordinate(self, h: int, w: int) -> int:
        return self._flatten_dxy(h + 2, w + 2)

    def bfs(self, start_2d: Tuple[int, int], goal_2d: Tuple[int, int]) -> int:
        start = self._flatten_coordinate(*start_2d)
        goal = self._flatten_coordinate(*goal_2d)

        w = self.width
        flatten = lambda *dxy: tuple(self._flatten_dxy(_dx, _dy) for _dx, _dy in dxy)
        move_to_warp = {
            -w: flatten((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-1, -1)),
            w: flatten((1, 1), (2, -1), (2, 0), (2, 1), (2, 2)),
            -1: flatten((-1, -2), (0, -2), (1, -2), (1, -1), (2, -2)),
            1: flatten((-1, 1), (-2, 2), (-1, 2), (2, 0), (1, 2)),
        }

        unsearched = 1 << 30
        dist = [unsearched] * (self.height * self.width)
        dist[start] = 0
        queue = deque([start])
        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == goal:
                break

            for move, warp in move_to_warp.items():
                nx = x + move
                if self.grid[nx] == self.road:
                    if dist[nx] > cur_dist:
                        dist[nx] = cur_dist
                        queue.appendleft(nx)
                    continue

                for dx in warp:
                    nx = x + dx
                    if self.grid[nx] == self.wall:
                        continue
                    if dist[nx] > cur_dist + 1:
                        dist[nx] = cur_dist + 1
                        queue.append(nx)

        return dist[goal] if dist[goal] != unsearched else -1

    def debug(self):
        print("<DEBUG>", file=sys.stderr)
        for row in zip(*[iter(self.grid)] * self.width):
            print(*row, file=sys.stderr)


def main():
    H, W, CH, CW, DH, DW, *S = open(0).read().split()
    maze = WarpableMaze(int(H), int(W), S)
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    print(maze.bfs(start, goal))
    # maze.debug()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# D - Wizard in Maze
import sys
from collections import deque
from typing import List, Tuple


class WarpableMaze:
    __slots__ = ["height", "width", "road", "wall", "grid"]

    def __init__(
        self,
        height: int,
        width: int,
        grid: List[str],
        road: str = ".",
        wall: str = "#",
    ) -> None:
        # Values of start and goal must be 0-origin.
        self.height = height + 4
        self.width = width + 4
        self.road = road
        self.wall = wall
        self.grid = self._flatten_grid(grid)

    def _flatten_grid(self, grid: List[str]) -> str:
        flat_grid = self.wall * self.width * 2
        for row in grid:
            flat_grid += self.wall * 2 + row + self.wall * 2
        flat_grid += self.wall * self.width * 2
        return flat_grid

    def _flatten_dxy(self, x: int, y: int) -> int:
        return self.width * x + y

    def _flatten_coordinate(self, h: int, w: int) -> int:
        return self._flatten_dxy(h + 2, w + 2)

    def bfs(self, start_2d: Tuple[int, int], goal_2d: Tuple[int, int]) -> int:
        start = self._flatten_coordinate(*start_2d)
        goal = self._flatten_coordinate(*goal_2d)

        w = self.width
        flatten = lambda *dxy: tuple(self._flatten_dxy(_dx, _dy) for _dx, _dy in dxy)
        move_to_warp = {
            -w: flatten((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-1, -1)),
            w: flatten((1, 1), (2, -1), (2, 0), (2, 1), (2, 2)),
            -1: flatten((-1, -2), (-2, 0), (1, -2), (1, -1), (2, -1)),
            1: flatten((-1, 1), (-2, 2), (-1, 2), (2, 0), (1, 2)),
        }

        unsearched = 1 << 30
        dist = [unsearched] * (self.height * self.width)
        dist[start] = 0
        queue = deque([start])
        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == goal:
                break

            for move, warp in move_to_warp.items():
                nx = x + move
                if self.grid[nx] == self.road:
                    if dist[nx] > cur_dist:
                        dist[nx] = cur_dist
                        queue.appendleft(nx)
                    continue

                for dx in warp:
                    nx = x + dx
                    if self.grid[nx] == self.wall:
                        continue
                    if dist[nx] > cur_dist + 1:
                        dist[nx] = cur_dist + 1
                        queue.append(nx)

        return dist[goal] if dist[goal] != unsearched else -1

    def debug(self):
        print("<DEBUG>", file=sys.stderr)
        for row in zip(*[iter(self.grid)] * self.width):
            print(*row, file=sys.stderr)


def main():
    H, W, CH, CW, DH, DW, *S = open(0).read().split()
    maze = WarpableMaze(int(H), int(W), S)
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    print(maze.bfs(start, goal))
    # maze.debug()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import product

INF = 10**18

H, W = map(int, input().split())
C = list(map(int, input().split()))
D = list(map(int, input().split()))
S = [input() for _ in range(H)]

s_pos = sx, sy = C[1]-1, C[0]-1
g_pos = gx, gy = D[1]-1, D[0]-1

dist = [[INF for _ in range(W)] for _ in range(H)]
dist[sy][sx] = 0

is_queue_added = [[False for _ in range(W)] for _ in range(H)]
is_queue_added[sy][sx] = True

q = deque([s_pos])
while q:
    t_pos = tx, ty = q.popleft()
    t_dist = dist[ty][tx]

    for dx, dy in product(range(-2, 3), repeat=2):
        if dx == dy == 0:
            continue
        pos = x, y = tx+dx, ty+dy
        if not (0 <= x < W and 0 <= y < H):
            continue
        if S[y][x] == "#":
            continue
        cost = (abs(dx)+abs(dy) > 1)
        if dist[y][x] <= t_dist + cost:
            continue
        dist[y][x] = t_dist + cost
        if is_queue_added[y][x]:
            continue
        is_queue_added[y][x] = True
        if cost == 0:
            q.appendleft(pos)
        else:
            q.append(pos)

r = dist[gy][gx]
if r == INF:
    print(-1)
else:
    print(r)

Submission status: Wrong Answer

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

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
S = [list(input()) for _ in range(H)]

move1 = ((1,0),(-1,0),(0,-1),(0,1))
move2 = []
for i in range(-2,3):
    for j in range(-2,3):
        if (i,j) not in move1:
            move2.append((i,j))

queue = deque()
queue.append((Cw, Ch))
search_queue = deque()
search_queue.append((Cw, Ch))
blockmat = [[-1]*W for _ in range(H)]
blockmat[Ch][Cw] = 0

while queue or search_queue:
    while queue:
        x,y = queue.popleft()
        block = blockmat[y][x]
        
        if x == Dw and y == Dh:
            queue.clear()
            search_queue.clear()
            break
                
        for dx,dy in move1:
            X = x + dx; Y = y + dy
            if X >= 0 and X < W and Y >= 0 and Y < H:
                if blockmat[Y][X] == -1 and S[Y][X] == '.':
                    blockmat[Y][X] = block
                    queue.append((X,Y))
                    search_queue.append((X,Y))

    while search_queue:
        x,y = search_queue.popleft()
        block = blockmat[y][x]

        for dx,dy in move2:
            X = x + dx; Y = y + dy
            if X >= 0 and X < W and Y >= 0 and Y < H:
                if blockmat[Y][X] == block:
                    continue
                if blockmat[Y][X] == -1 and S[Y][X] == '.':
                    blockmat[Y][X] = block + 1
                    queue.append((X,Y))
print(blockmat[Dh][Dw])

Submission status: Wrong Answer

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

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
S = [list(input()) for _ in range(H)]

move1 = ((1,0),(-1,0),(0,-1),(0,1))
move2 = []
for i in range(-2,3):
    for j in range(-2,3):
        if (i,j) not in move1:
            move2.append((i,j))

queue = deque()
queue.append((Cw, Ch))
search_queue = deque()
search_queue.append((Cw, Ch))
blockmat = [[-1]*W for _ in range(H)]
blockmat[Ch][Cw] = 0

while queue or search_queue:
    while queue:
        x,y = queue.popleft()
        block = blockmat[y][x]
        
        if x == Dw and y == Dh:
            queue.clear()
            search_queue.clear()
            break
                
        for dx,dy in move1:
            X = x + dx; Y = y + dy
            if X >= 0 and X < W and Y >= 0 and Y < H:
                if blockmat[Y][X] == -1 and S[Y][X] == '.':
                    blockmat[Y][X] = block
                    queue.append((X,Y))
                    search_queue.append((X,Y))

    while search_queue:
        x,y = search_queue.popleft()
        block = blockmat[y][x]
        
        if x == Dw and y == Dh:
            queue.clear()
            search_queue.clear()
            break
                
        for dx,dy in move2:
            X = x + dx; Y = y + dy
            if X >= 0 and X < W and Y >= 0 and Y < H:
                if blockmat[Y][X] == block:
                    continue
                if blockmat[Y][X] == -1 and S[Y][X] == '.':
                    blockmat[Y][X] = block + 1
                    queue.append((X,Y))
print(blockmat[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

dd = [(1,0),(0,1),(-1,0),(0,-1)]
h,w = inpl()
cy,cx = inpl()
gy,gx = inpl()
cy,cx,gy,gx = cy-1,cx-1,gy-1,gx-1
s = [input() for _ in range(h)]
res = [[INF] * w for _ in range(h)]
seen = [[False] * w for _ in range(h)]
q = deque([])
q.append((cy,cx))
res[cy][cx] = 0
def waap(i,j):
    for dy in range(-2,3):
        for dx in range(-2,3):
            ny = dy + i
            nx = dx + j
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == '.':
                res[ny][nx] = min(res[ny][nx], res[i][j] + 1)
                if not seen[ny][nx]:
                    q.append((ny,nx))
waap(cy,cx)
while q:
    oy,ox = q.popleft()
    seen[oy][ox] = True
    for dy,dx in dd:
        ny = dy + oy
        nx = dx + ox
        # print(ny,nx)
        if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == '.' and not seen[ny][nx]:
            res[ny][nx] = min(res[ny][nx], res[oy][ox])
            waap(ny,nx)
            # seen[ny][nx] = True
            # print(ny,nx)
            q.append([ny,nx])
# print(res)
print(res[gy][gx] if res[gy][gx] != INF else -1)

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
Ch, Cw = list(map(lambda x:int(x)+1, input().split()))
Dh, Dw = list(map(lambda x:int(x)+1, input().split()))
S = []

S.append(list('#'*(W+4)))
S.append(list('#'*(W+4)))
for i in range(H):
    S.append(list('#'*2+input()+'#'*2))
S.append(list('#'*(W+4)))
S.append(list('#'*(W+4)))

from collections import deque

q1 = deque()
q2 = deque()
inf = 10**10


#cost
T = []
for w in S:
    T_W = [-1 if s=='#' else inf for s in w]
    T.append(T_W)

# print(T)
move1 = [(1,0),(0,1),(-1,0),(0,-1)]
move2 = [(i-2,j-2) for i in range(5) for j in range(5)]
move2.remove((0,0))
for t in move1:
    move2.remove(t)
d = 0
h, w = Ch, Cw
T[Ch][Cw] = d
q1.append((h,w))
q2.append((h,w))

ans = -1

while len(q2)>0 or len(q1)>0:
    while len(q1)>0:
        v = q1.popleft()
        for t in [(1,0),(0,1),(-1,0),(0,-1)]:
            h, w = v[0]+t[0], v[1]+t[1]
            if T[h][w] > d:
                if (h,w) == (Dh,Dw):
                    ans = -1
                T[h][w] = d
                q1.append((h,w))
                q2.append((h,w))
    d += 1
    while len(q2)>0:
        v = q2.popleft()
        for t in move2:
            h, w = v[0]+t[0], v[1]+t[1]
            if T[h][w] > d:
                if (h,w) == (Dh,Dw):
                    ans = -1
                T[h][w] = d
                q1.append((h,w))
    q2.extend(q1)

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
Ch, Cw = list(map(lambda x:int(x)+1, input().split()))
Dh, Dw = list(map(lambda x:int(x)+1, input().split()))
S = []

S.append(list('#'*(W+4)))
S.append(list('#'*(W+4)))
for i in range(H):
    S.append(list('#'*2+input()+'#'*2))
S.append(list('#'*(W+4)))
S.append(list('#'*(W+4)))

from collections import deque

q1 = deque()
q2 = deque()
inf = 10**10


#cost
T = []
for w in S:
    T_W = [-1 if s=='#' else inf for s in w]
    T.append(T_W)

# print(T)
move1 = [(1,0),(0,1),(-1,0),(0,-1)]
move2 = [(i-2,j-2) for i in range(5) for j in range(5)]
move2.remove((0,0))
for t in move1:
    move2.remove(t)
d = 0
h, w = Ch, Cw
T[Ch][Cw] = d
q1.append((h,w))
q2.append((h,w))


while len(q2)>0 or len(q1)>0:
    while len(q1)>0:
        v = q1.popleft()
        for t in [(1,0),(0,1),(-1,0),(0,-1)]:
            h, w = v[0]+t[0], v[1]+t[1]
            if T[h][w] > d:
                if (h,w) == (Dh,Dw):
                    print(d)
                T[h][w] = d
                q1.append((h,w))
                q2.append((h,w))
    d += 1
    while len(q2)>0:
        v = q2.popleft()
        for t in move2:
            h, w = v[0]+t[0], v[1]+t[1]
            if T[h][w] > d:
                if (h,w) == (Dh,Dw):
                    print(d)
                T[h][w] = d
                q1.append((h,w))
    q2.extend(q1)
else:
    print(-1)