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:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################
# Verified by
# https://atcoder.jp/contests/arc033/submissions/me
# https://atcoder.jp/contests/abc174/tasks/abc174_f
#
# speed up TIPS: delete update of el. non-use of getitem, setitem.
#
# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value
# Bit.l_bound(w)  : get bound of index where x1+x2+...+xi<w

class Bit: # 1-indexed
    def __init__(self,n,init=None):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        self.el=[0]*(2**self.m+1)
        if init!=None:
            for i in range(len(init)):
                self.add(i,init[i])
                self.el[i]=init[i]

    def __str__(self):
        a=[self.sum(i+1)-self.sum(i) for i in range(self.size)]
        return str(a)
        
    def add(self,i,x):
        if not 0<i<=self.size:return NotImplemented
        self.el[i]+=x
        while i<=self.size:
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        if not 0<=i<=self.size:return NotImplemented
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def __getitem__(self,key):
        return self.el[key]
        return self.sum(key+1)-self.sum(key)

    def __setitem__(self,key,value):
        self.add(key,value-self.sum(key+1)+self.sum(key))

    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<=self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k>>=1
        return x+1
        
    def u_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<=self.size and self.arr[x+k]<=w:
                w-=self.arr[x+k]
                x+=k
            k>>=1
        return x+1
        
class Bit0(Bit): # 0-indexed
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)
    def u_bound(self,w):
        return max(super().u_bound(w)-1,0)

class Multiset(Bit0):
    def __init__(self,max_v):
        super().__init__(max_v)
    def insert(self,x):
        super().add(x,1)
    def find(self,x):
        return super().l_bound(super().sum(x))
    def __str__(self):
        return str(self.arr)

def compress(L):
    dc={v:i for i,v in enumerate(sorted(set(L)))}
    return [dc[i] for i in L]


show_flg=False
show_flg=True

ans=0

h,w=LI()
sh,sw=LI()
gh,gw=LI()

w+=2
m=[1]*w
for i in range(h):
    s=input()
    m+=[1]+[i=='#'for i in s]+[1]
m+=[1]*w
h+=2
n=h*w
v=[-1]*w*h

dc=dict()
cn=0
def bfs(x):
    global cn
    q=[x]
    v[x]=x
    dc[x]=cn
    cn+=1
    while q:
        c=q.pop()
        for nx in [c+1,c-1,c+w,c-w]:
            if 0<=nx<n and m[nx]!=1 and v[nx]==-1:
                q+=nx,
                v[nx]=x
    return        
            
for i in range(n):
    if m[i]!=1 and v[i]==-1:
        bfs(i)

g=[set()for i in range(cn)]
nbw=[-2*w+1,-2*w+2,-w+1,-w+2,2,2*w+1,2*w+2,w+1,w+2,+2*w,-2*w,-2*w-1,-2*w-2,-w-1,-w-2,-2,2*w-1,2*w-2,w-1,w-2]
nb=[1,-1,w,-w]
d=[-1]*n
q=list().append(sh*w+sw)
while q:
    i=q.pop()
    if m[i]==1:
        continue
    for di in nb:
        nx=i+di
        if 0<=nx<n and m[nx]!=1 and d[nx]!=-1:
            d[nx]=d[i]
            q.appendleft(i)

q=deque([dc[v[sh*w+sw]]])
dist=[-1]*cn
dist[dc[v[sh*w+sw]]]=0
while q:
    c=q.pop()
    for nx in g[c]:
        if dist[nx]==-1:
            q.appendleft(nx)
            dist[nx]=dist[c]+1

print(dist[dc[v[gh*w+gw]]])

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())
maze = [[] for i in range(H)]
for i in range(H):
  st = input()
  for j in range(W):
    maze[i].append(st[j])
walk_queue = [[Ch-1, Cw-1]]
magic_queue = [[Ch-1, Cw-1]]
all_queue = [[Ch-1, Cw-1]]

walk_move = [[-1, 0], [0, -1], [1, 0], [0, 1]]
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

ans = 0
while True:
  for x1,y1 in walk_queue:
    for i,j in walk_move:
      if 0 <= x1+i <= H-1 and  0 <= y1+j <= W-1 and maze[x1+i][y1+j] == ".":
        if not [x1+i, y1+j] in all_queue:
          walk_queue.append([x1+i, y1+j])
          all_queue.append([x1+i, y1+j])
          magic_queue.append([x1+i, y1+j])

  walk_queue.clear()
  for x2,y2 in magic_queue:
    for k,l in magic_move:
      if 0 <= x2+k <= H-1 and  0 <= y2+l <= W-1 and maze[x2+k][y2+l] == ".":
        if not [x2+k, y2+l] in all_queue:
          walk_queue.append([x2+k, x2+l])
          all_queue.append([x2+k, x2+l])
          
  if not len(walk_queue):
    if [Dh-1, Dw-1] in all_queue:
      break
    else:
      ans = "-1"
      break
  else:
    ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
cy, cx = map(lambda x: int(x) - 1, input().split())
dy, dx = map(lambda x: int(x) - 1, input().split())
table = [list(input()) for _ in range(h)]
if cy == dy and cx == dx:
    print(0)
    exit()
if table[cy][cx] == "#" or table[dy][dx] == "#":
    print(-1)
    exit()
stack = [[cy, cx]]
table[cy][cx] = 0
step = [0, 1, 0, -1, 0]
step2 = [[-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], [-1, -1], [-1, 1], [1, -1], [1, 1]]
while len(stack) > 0:
    cur = stack.pop()
    if cur[0] == dy and cur[1] == dx:
        break
    for [i, j] in step2:
        ny, nx = cur[0] + i, cur[1] + j
        if 0 <= ny < h and 0 <= nx < w and table[ny][nx] != "#":
            if table[ny][nx] == ".":
                table[ny][nx] = table[cur[0]][cur[1]] + 1
                stack.append([ny, nx])
            elif table[ny][nx] > table[cur[0]][cur[1]] + 1:
                table[ny][nx] = table[cur[0]][cur[1]] + 1
                stack.append([ny, nx])

    cur2 = cur
    for i in range(4):
        ny, nx = cur2[0] + step[i], cur2[1] + step[i + 1]
        if 0 <= ny < h and 0 <= nx < w and table[ny][nx] != "#":
            if table[ny][nx] == ".":
                table[ny][nx] = table[cur2[0]][cur2[1]]
                stack.append([ny, nx])
            elif table[ny][nx] > table[cur2[0]][cur2[1]]:
                table[ny][nx] = table[cur2[0]][cur2[1]]
                stack.append([ny, nx])
print(-1 if table[dy][dx] == "." else table[dy][dx])

Submission status: Wrong Answer

Solution code:
import sys

h, w= map(int, input().split(' '))
start = list(map(int, input().split(' ')))
for i in range(2):
  start[i] -= 1
goal = list(map(int, input().split(' ')))
for i in range(2):
  goal[i] -= 1

grid = []
for _ in range(h):
  grid.append(list(input()))
   
q = []
    
def dfs(grid, i, j, d, h, w):
  if i == goal[0] and j == goal[1]:
    print(d)
    sys.exit()
  if 0 <= i < h and 0 <= j < w and grid[i][j] == '.':
    grid[i][j] = '#'
    q.append([i, j, d])
    dfs(grid, i-1, j, d, h, w)
    dfs(grid, i+1, j, d, h, w)
    dfs(grid, i, j-1, d, h, w)
    dfs(grid, i, j+1, d, h, w)
    return
  
dfs(grid, start[0], start[1], 0, h, w)

x_directions = [-2, -1, 0, 1, 2]
y_directions = [-2, -1, 0, 1, 2]

while q:
  i, j, d = q.pop(0)
  if i == goal[0] and j == goal[1]:
    print(d)
    sys.exit()
  for x in x_directions:
    for y in y_directions:
      if 0 <= x + i < h and 0 <= y + j < w and grid[x + i][y + j] == '.':
        grid[x + i][y + j] = '#'
        q.append([x + i, y + j, d + 1])
        dfs(grid, x+i, y+j, d+1, h, w)
        
print(-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, Cw, Dh, Dw = Ch - 1, Cw - 1, Dh - 1, Dw - 1
maze = [list(input()) for i in range(H)]
#print(maze)
  
ans = [[-1] * W for i in range(H)]  
ans[Ch][Cw] = 0
q = deque([[0, Ch, Cw]])  
one = [[0, 1], [0, -1], [1, 0], [-1, 0]]
two = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [2, 0], [-1, 2], [-1, -1], [-1, 1], [-1, 2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]] 
while q:
  cnt, h, w = q.popleft()
  if ans[h][w] < cnt:
    continue
  for i, j in one:
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "#"):
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt:
          ans[h + i][w + j] = cnt
          q.appendleft([cnt, h + i, w + j])
  for i, j in two:  
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "#"):
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt + 1:
          ans[h + i][w + j] = cnt + 1
          q.appendleft([cnt + 1, h + i, w + j])
              
print(ans[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from collections import deque

inf = float("inf")


def BFS():
    color = [["white" for _ in range(w)] for _ in range(h)]
    D = [[inf for _ in range(w)] for _ in range(h)]
    queue = deque([])

    x, y = C
    x -= 1
    y -= 1
    queue.append([x, y])
    D[x][y] = 0

    for i in range(h):
        for j in range(w):
            if S[i][j] == "#":
                color[i][j] = "black"

    while len(queue) > 0:
        x, y = queue.popleft()
        for i in range(max(0, x - 2), min(h, x + 3)):
            for j in range(max(0, y - 2), min(w, y + 3)):
                X, Y = i, j
                if 0 <= X < h and 0 <= Y < w:
                    if color[X][Y] != "black":
                        D[X][Y] = min(D[X][Y], D[x][y] + 1)
                        if color[X][Y] == "white":
                            queue.append([X, Y])
                        color[X][Y] = "gray"
        for i, j in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            X, Y = x + i, y + j
            if 0 <= X < h and 0 <= Y < w:
                if color[X][Y] != "black":
                    D[X][Y] = min(D[X][Y], D[x][y])
                    if color[X][Y] == "white":
                        queue.append([X, Y])
                    color[X][Y] = "gray"

        color[x][y] = "black"

    return D[G[0] - 1][G[1] - 1]


h, w = map(int, input().split())
C = list(map(int, input().split()))
G = list(map(int, input().split()))
S = [list(input()) for _ in range(h)]

D = BFS()
print(D if D != inf else -1)

Submission status: Wrong Answer

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

h,w = map(int, input().split())
sy,sx = map(int, input().split())
gy,gx = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from heapq import heappush, heappop,heappushpop,heapify
from collections import defaultdict
link = defaultdict(list)
chg=10**4

for y in range(h):
    for x in range(w):
        if l[y][x]=="#":
            continue
        frm = y*chg+x
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0 <= nx < w and 0 <= ny < h and l[ny][nx]==".":
                to=ny*chg+nx
                link[frm].append([to,0])

        for dx in [-2,-1,0,1,2]:
            for dy in [-2,-1,0,1,2]:
                if abs(dx)+abs(dy)<=1:
                    continue
                nx=x+dx
                ny=y+dy
                if 0 <= nx < w and 0 <= ny < h and l[ny][nx]==".":
                    to=ny*chg+nx
                    link[frm].append([to,1])
def dks(g,start):
    visited = set()
    hq = []
    heappush(hq, (0,start))

    cost = defaultdict(lambda: float("inf"))
    while hq:
        shortest, i = heappop(hq)
        if i in visited:
            continue
        visited.add(i)
        cost[i] = shortest
        for j, t in g[i]:
            if j in visited:
                continue
            if j==goal:
                return shortest+t
            heappush(hq, (shortest + t, j))
    return -1

start = (sy-1)*chg+sx-1
goal = (gy-1)*chg+gx-1
ret=dks(link, start)
print(ret)

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, Cw, Dh, Dw = Ch - 1, Cw - 1, Dh - 1, Dw - 1
maze = [0] * H
for i in range(H):
  maze[i] = str(input())
  
ans = [[-1] * W for i in range(H)]  
ans[Ch][Cw] = 0
q = deque([[0, Ch, Cw]])  
one = [[0, 1], [0, -1], [1, 0], [-1, 0]]
two = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [2, 0], [-1, 2], [-1, -1], [-1, 1], [-1, 2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]] 
while q:
  cnt, h, w = q.popleft()
  if ans[h][w] < cnt:
    continue
  for i, j in one:
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "#"):
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt:
          ans[h + i][w + j] = cnt
          q.appendleft([cnt, h + i, w + j])
  for i, j in two:  
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "#"):
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt + 1:
          ans[h + i][w + j] = cnt + 1
          q.appendleft([cnt + 1, h + i, w + j])
              
print(ans[Dh][Dw])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and dx==1) or (dy==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])

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, Cw, Dh, Dw = Ch - 1, Cw - 1, Dh - 1, Dw - 1
maze = [0] * H
for i in range(H):
  maze[i] = str(input())
  
ans = [[-1] * W for i in range(H)]  
ans[Ch][Cw] = 0
q = deque([[0, Ch, Cw]])  
one = [[0, 1], [0, -1], [1, 0], [-1, 0]]
two = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [2, 0], [-1, 2], [-1, -1], [-1, 1], [-1, 2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]] 
while q:
  cnt, h, w = q.popleft()
  if ans[h][w] < cnt:
    continue
  for i, j in one:
    if (0 <= h + i < H) and (0 <= w + j < W):
      if maze[h + i][w + j] == ".":
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt:
          ans[h + i][w + j] = cnt
          q.appendleft([cnt, h + i, w + j])
  for i, j in two:  
    if (0 <= h + i < H) and (0 <= w + j < W):
      if maze[h + i][w + j] == ".":
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt + 1:
          ans[h + i][w + j] = cnt + 1
          q.appendleft([cnt + 1, h + i, w + j])
              
print(ans[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh, dw = map(int, input().split())
    dh -= 1
    dw -= 1
    maze = [input() for i in range(h)]
    visited = [[-1]*w for j in range(h)]
    
    def maze_solver(maze, visited, sy, sx, gy, gx):
        mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        q = deque([[sy, sx]])
        visited[sy][sx] = 0 
        _yx = list()
        _yx.append([sy, sx])
        while q:
            y, x = q.popleft()
            if y == gy and x == gx:
                ans = visited[y][x]
                _yx = list(map(list, set(map(tuple, _yx))))
                return ans, visited, _yx
            for i, j in mv:
                if (0 <= y + i < h) and (0 <= x + j < w):  
                    ny = y+i
                    nx = x+j
                    if visited[ny][nx] != -1:
                        continue
                    if maze[ny][nx] == '.':
                        visited[ny][nx] = visited[y][x] + 1 
                        q.append([ny, nx])
                        _yx.append([ny, nx])
                else:
                    continue
        _yx = list(map(list, set(map(tuple, _yx))))
        return -1, visited, _yx

    def telepo(maze, visited, _yx, h, w):
        n_yx = list()
        for y, x in _yx:
            for ny in range(-2, 3):
                for nx in range(-2, 3):
                    if 0 <= y+ny < h and \
                        0 <= x+nx < w and \
                        visited[y+ny][x+nx] == -1 and \
                        maze[y+ny][x+nx] != '#': 
                        n_yx.append([y+ny, x+nx])
        n_yx_s = list(map(list, set(map(tuple, n_yx))))
        return n_yx_s
    
    telepo_cnt = 0
    ans, _visited, _yx = maze_solver(maze, visited, ch, cw, dh, dw)
    if ans != -1:
        print(telepo_cnt)
        exit()
    else:
        n_yx_s = [[]]
        while len(n_yx_s) > 0:
            n_yx_s = telepo(maze, _visited, _yx, h, w)
            telepo_cnt += 1
            for ny, nx in n_yx_s:
                ans, _visted, _yx= maze_solver(maze, _visited, ny, nx, dh, dw)
                if ans != -1:
                    print(telepo_cnt)
                    exit()
    print(-1)
                        
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", "start", "goal", "road", "wall", "grid"]

    def __init__(
        self,
        height: int,
        width: int,
        start: Tuple[int, int],
        goal: Tuple[int, 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.start = self._flatten_coordinate(*start)
        self.goal = self._flatten_coordinate(*goal)
        self.road = road
        self.wall = wall
        self.grid = self._flatten_grid(grid)

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

    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 bfs(self) -> int:
        w = self.width
        move = (-w, w, -1, 1)
        warp = [-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -2 * w + 2]
        warp.extend([-w - 2, -w - 1, -w + 1, -w + 2, -2, 2])
        warp.extend([w - 2, w - 1, w + 1, w + 2])
        warp.extend([2 * w - 2, 2 * w - 1, 2 * w, 2 * w + 1, 2 * w + 2])

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

            for dx in move:
                nx = x + dx
                if self.grid[nx] == self.wall:
                    continue
                if dist[nx] == unsearched or dist[nx] > cur_dist:
                    dist[nx] = cur_dist
                    queue.appendleft(nx)

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

        return dist[self.goal]

    def debug(self):
        print(f"<DEBUG>\nstart={self.start}, goal={self.goal}", 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()
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    maze = WarpableMaze(int(H), int(W), start, goal, S)
    # maze.debug()
    print(maze.bfs())


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", "start", "goal", "road", "wall", "grid"]

    def __init__(
        self,
        height: int,
        width: int,
        start: Tuple[int, int],
        goal: Tuple[int, 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.start = self._flatten_coordinate(*start)
        self.goal = self._flatten_coordinate(*goal)
        self.road = road
        self.wall = wall
        self.grid = self._flatten_grid(grid)

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

    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 bfs(self) -> int:
        w = self.width
        move = (-w, w, -1, 1)
        warp = [-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -2 * w + 2]
        warp.extend([-w - 2, -w - 1, -w + 1, -w + 2, -2, 2])
        warp.extend([w - 2, w - 1, w + 1, w + 2])
        warp.extend([2 * w - 2, 2 * w - 1, 2 * w, 2 * w + 1, 2 * w + 2])

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

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

            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[self.goal]

    def debug(self):
        print(f"<DEBUG>\nstart={self.start}, goal={self.goal}", 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()
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    maze = WarpableMaze(int(H), int(W), start, goal, S)
    # maze.debug()
    print(maze.bfs())


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())
path = [[-1]*w for i in range(h)]
maze = []
for _ in range(h):
  s = input()
  maze.append(s)

walk = [(0,1),(1,0),(-1,0),(0,-1)]
warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
Q = deque()
path[ch-1][cw-1]=0
Q.append((ch-1,cw-1,0))
while Q:
  hi,wi,c = Q.popleft()
  for i,j in walk:
    nh = i + hi
    nw = j + wi
    if 0<=nh<h and 0<=nw<w and maze[nh][nw]=='.' and path[nh][nw]==-1:
      path[nh][nw] = c
      Q.append((nh,nw,c))
  for i,j in warp:
    nh = i + hi
    nw = j + wi
    if 0<=nh<h and 0<=nw<w and maze[nh][nw]=='.' and path[nh][nw]==-1:
      path[nh][nw] = c+1
      Q.append((nh,nw,c+1))
print(path[dh-1][dw-1])