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:
#!/usr/bin/env python3

from collections import deque
import sys

INF = 10 ** 12


H, W = map(int, input().split())
s_i, s_j = map(lambda x: int(x) - 1, input().split())
t_i, t_j = map(lambda x: int(x) - 1, input().split())
field = [list(input()) for _ in range(H)]

# 1. bfs でワープなしで到達できるマスを探索
# 2. 1 で見つかったマスから一回ワープして到達できるマスを探索
# 3. 1, 2 を繰り返す


def bfs(que, warp_times):
    while que:
        i, j, times = que.popleft()
        # ワープ無しで到達できるマスの探索
        for di, dj in walk:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times:
                    warp_times[i_adj][j_adj] = times
                    que.appendleft((i_adj, j_adj, times))

        # ワープ有りで到達できるマスの探索
        for di, dj in warp:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and 0 <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times + 1:
                    warp_times[i_adj][j_adj] = times + 1
                    # ワープ無しで到達できるマスを探索しきった後に探索するため、単に append
                    que.append((i_adj, j_adj, times + 1))


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 (i, j) not in [(0, 0)] + walk]

warp_times = [[INF for j in range(W)] for i in range(H)]
que = deque()

warp_times[s_i][s_j] = 0
que.append((s_i, s_j, 0))

bfs(que, warp_times)

ans = warp_times[t_i][t_j] if warp_times[t_i][t_j] < INF else '-1'
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

from collections import deque
import sys

INF = 10 ** 12


H, W = map(int, input().split())
s_i, s_j = map(lambda x: int(x) - 1, input().split())
t_i, t_j = map(lambda x: int(x) - 1, input().split())
field = [list(input()) for _ in range(H)]

# 1. bfs でワープなしで到達できるマスを探索
# 2. 1 で見つかったマスから一回ワープして到達できるマスを探索
# 3. 1, 2 を繰り返す


def bfs(que, warp_times):
    while que:
        i, j, times = que.popleft()
        # ワープ無しで到達できるマスの探索
        for di, dj in walk:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times:
                    warp_times[i_adj][j_adj] = times
                    que.appendleft((i_adj, j_adj, times))

        # ワープ有りで到達できるマスの探索
        for di, dj in warp:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times + 1:
                    warp_times[i_adj][j_adj] = times + 1
                    # ワープ無しで到達できるマスを探索しきった後に探索するため、単に append
                    que.append((i_adj, j_adj, times + 1))


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 (i, j) not in [(0, 0)] + walk]

warp_times = [[INF for j in range(W)] for i in range(H)]
que = deque()

warp_times[s_i][s_j] = 0
que.append((s_i, s_j, 0))

bfs(que, warp_times)

ans = warp_times[t_i][t_j] if warp_times[t_i][t_j] < INF else '-1'
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
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 = [input() for i in range(H)]
INF = 10 ** 9
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
h = CH
w = CW
Distance = np.ones((H,W)) * INF
Distance[h,w] = 0
q = deque([])
q.append([h,w])
while q:
  h,w = q.popleft()
  if [h,w] == [DH,DW]:
    break
  for i,j in walk:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h,w] < Distance[hwalk,wwalk]:
      Distance[hwalk,wwalk] = Distance[h,w]
      q.appendleft([hwalk,wwalk])
  for i,j in warp:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h,w] + 1 < Distance[hwalk,wwalk]:
      Distance[hwalk,wwalk] = Distance[h,w] + 1
      q.append([hwalk,wwalk])
print(Distance)
print(int(Distance[DH,DW]) if Distance[DH,DW] != INF else -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())

S=[list(input()) for _ in range(H)]
MAX_COST = 99999
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-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

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

dq = deque([])
dq.append((Ch, Cw, 0))
search[Ch][Cw] = 0

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]
dq1 = deque([])

while dq:
    r, c, cur_cost = dq.popleft()
    dq1.append((r, c, cur_cost))

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.append((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    if not dq:
        while dq1:
            r, c, cur_cost = dq1.popleft()

            for x in range(-2, 3):
                r_new = r + x
                if r_new < 0 or r_new >= H:
                    continue

                for y in range(-2, 3):
                    c_new = c + y

                    if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                        continue

                    dq1.append((r_new, c_new, cur_cost + 1))
                    search[r_new][c_new] = cur_cost + 1


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

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

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

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]

  while len(deq):
    y,x = deq.popleft()
    for dy,dx in move_a:
      ny,nx = y+dy,x+dx
      if 0<=ny<H and 0<=nx<W and S[ny][nx] and dist[ny][nx]>dist[y][x]:
        dist[ny][nx] = dist[y][x]
        deq.appendleft((ny,nx))
    for dy,dx in move_b:
      ny,nx = y+dy,x+dx
      if not (0<=ny<H and 0<=nx<W):
        continue
      if not S[ny][nx]:
        continue
      if dist[ny][nx] <= dist[y][x]+1:
        continue
      flag = False
      for ddy,ddx in move_a:
        nny,nnx = ny+ddy,nx+ddx
        if 0<=nny<H and 0<=nnx<W and S[nny][nnx] and dist[nny][nnx]==dist[y][x]:
          flag = True
          break
      if flag:
        break
      dist[ny][nx] = dist[y][x] + 1
      deq.append((ny,nx))
    
  ans = dist[D_h][D_w]
  print(ans if ans!=INF else -1)


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

solve(H,W,C_h,C_w,D_h,D_w,S)

Submission status: Wrong Answer

Solution code:
from pprint import pprint
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 _ in range(h)]

from collections import deque

dist=[[-1]*w for _ in range(h)]
q=deque()
p=set()
q.append((ch,cw))
dist[ch][cw]=0
visited=set()
cur=0 #ワープ回数
while q:
    # print("now cur:",cur)
    # print(q)
    while q:
        x,y=q.popleft()
        dist[x][y]=cur
        for i in range(-1,2):
            for j in range(-1,2):
                if abs(i)+abs(j)==1:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if dist[xx][yy]==-1:
                            if maze[xx][yy]==".":
                                dist[xx][yy]=cur
                                q.append((xx,yy))
                                visited.add((xx,yy))
                        if dist[xx][yy]>cur:
                            dist[xx][yy]=cur
                            q.append((xx,yy))
                                
        for i in range(-2,3):
            for j in range(-2,3):
                if abs(i)+abs(j)>=2:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if dist[xx][yy]==-1:
                            if maze[xx][yy]==".":
                                p.add((xx,yy))
                                
    
    if len(q)==0:
        for pp in p:
            if pp in visited:
                continue
            q.append(pp)
        visited=set()
        p=set()
        cur+=1
# pprint(dist)
print(dist[dh][dw])

Submission status: Wrong Answer

Solution code:
from pprint import pprint
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 _ in range(h)]

from collections import deque

dist=[[-1]*w for _ in range(h)]
q=deque()
p=set()
q.append((ch,cw))
dist[ch][cw]=0
visited=set()
cur=0 #ワープ回数
while q:
    # print("now cur:",cur)
    # print(q)
    while q:
        x,y=q.popleft()
        dist[x][y]=cur
        for i in range(-1,2):
            for j in range(-1,2):
                if abs(i)+abs(j)==1:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if dist[xx][yy]==-1:
                            if maze[xx][yy]==".":
                                dist[xx][yy]=cur
                                q.append((xx,yy))
                                visited.add((xx,yy))
                        if dist[xx][yy]>cur:
                            dist[xx][yy]=cur
                            q.append((xx,yy))
                                
        for i in range(-2,3):
            for j in range(-2,3):
                if abs(i)+abs(j)>=2:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if dist[xx][yy]==-1:
                            if maze[xx][yy]==".":
                                p.add((xx,yy))
                                
    
    if len(q)==0:
        for pp in p:
            if pp in visited:
                continue
            q.append(pp)
        p=set()
        cur+=1
# pprint(dist)
print(dist[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**9
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
s = [input() for _ in range(H)]

def walk(h, w):
    q = deque([[h, w]])
    coord = []
    while q:
        y, x = q.popleft()
        for i, j in [(0,1), (0,-1), (1,0),(-1,0)]:
            if (y+i<0 or y+i>H-1) or (x+j<0 or x+j>W-1):
                continue
            if s[y+i][x+j] == '#':
                continue
            if m[y+i][x+j] != INF:
                continue
            q.append([y+i, x+j])
            m[y+i][x+j] = m[h][w]
            coord.append([y+i, x+j])
    return coord


def warp(h, w):
    coord = []
    v = m[h][w]
    h_s = max(0, h-2)
    h_e = min(H-1, h+2)
    w_s = max(0, w-2)
    w_e = min(W-1, w+2)
    for h1 in range(h_s, h_e+1):
        for w1 in range(w_s, w_e+1):
            if h==h1 and w==w1:
                continue
            if m[h1][w1] == INF and s[h1][w1] != '#':
                m[h1][w1] = v + 1
                coord.append([h1, w1])
    return coord

    
m = [[INF] * W for _ in range(H)]
m[ch][cw] = 0
queue = [[ch, cw]]
while True:
    coord = []
    co = []
    for y, x in queue:
        coord += walk(y, x)
    coord += queue
    for h, w in coord:
        co = warp(h, w)
    if len(co) == 0:
        break
    queue = co.copy()

print(m[dh][dw])

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
 
H, W = map(lambda x: int(x)+4, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
 
grid = '#' * W * 2
for _ in range(H-4):
  grid += '##' + input() + '##'
grid += '#' * W * 2
 
magic_list = []
for i in range(5):
  for j in range(5):
    if (i, j) in [(2, 2), (1, 2), (2, 1), (2, 3), (3, 2)]:
      continue
    else:
      magic_list.append(i-2 + W*(j-2))
 
move_list = [-1, 1, W, -W]
 
def bfs(start):
  INF = 10 ** 4
  dist = [INF] * (H*W)
  dist[start] = 0
  qw = deque([start])
  qm = deque([])
  while qw or qm:
    while qw:
      v = qw.popleft()
      dv = dist[v]
      magic_flag = True
      for move in move_list:
        w = v + move
        if grid[w] == '#':
          if magic_flag:
            qm.append(v)
            magic_flag = False
          continue
        dw = dv
        if dw >= dist[w]:
          continue
        dist[w] = dw
        qw.append(w)
    while qm:
      v = qm.popleft()
      dv = dist[v]
      for magic in magic_list:
        w = v + magic
        if grid[w] == '#':
          continue
        dw = dv + 1
        if dw >= dist[w]:
          continue
        dist[w] = dw
        qw.append(w)
  return dist
 
ans = bfs( (Ch+1)*W + Cw+1 )[(Dh+1)*W + Dw+1]
 
if ans == 10**4:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = map(int, input().split())
c = tuple(map(int, input().split()))
d = tuple(map(int, input().split()))
m = ['#' for _ in range(h+2)]
m[0] += '#'*w
m[h+1] += '#'*w
que = deque()
que.append(c)
warp = [[10**5 for _ in range(w+1)] for _ in range(h+1)]
for i in range(1,h+1):  m[i] += input()+'#'
up = lambda x,y: 1 if 0<x-1 and m[x-1][y]=='.' else 0
down = lambda x,y: 1 if x+1<=h and m[x+1][y]=='.' else 0
right = lambda x,y: 1 if y+1<=w and m[x][y+1]=='.' else 0
left = lambda x,y: 1 if 0<y-1 and m[x][y-1]=='.' else 0

def jump(x,y,cost):
  deq = deque()
  for i in range(x-2,x+3):
    if i<=0 or h<i:  continue
    for j in range(y-2,y+3):
      if j<=0 or w<j:  continue
      if m[i][j] == '.' and warp[i][j]>cost+1:
        warp[i][j] = cost+1
        deq.append((i,j))
  return deq
  
warp[c[0]][c[1]] = 0
while que:
  q = que.popleft()
  row = q[0]
  col = q[1]
  cost = warp[row][col]
  if up(row,col) and warp[row-1][col]>cost:
    que.appendleft((row-1,col))
    warp[row-1][col] = cost
  if down(row,col) and warp[row+1][col]>cost:
    que.appendleft((row+1,col))
    warp[row+1][col] = cost
  if right(row,col) and warp[row][col+1]>cost:
    que.appendleft((row,col+1))
    warp[row][col+1] = cost
  if left(row,col) and warp[row][col-1]>cost:
    que.appendleft((row,col-1))
    warp[row][col-1] = cost
  que.extend(jump(row,col,cost))

if warp[d[0]][d[1]] != 10**5:  print(warp[d[0]][d[1]])
else:  print(-1)

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(input()) for i in range(h)]
visited=[[-1 for i in range(w)] for i in range(h)]
queue=[]

queue.append([ch-1,cw-1])
visited[ch-1][cw-1]=0

dy_dx=[[1,0],[0,1],[-1,0],[0,-1]]
warp=[]
for i in range(-2,3):
	for j in range(-2,3):
		if i!=0 or j!=0:
			warp.append([i,j])

while len(queue)>0:
	now=queue.pop(0)
	for i in range(4):
		y=now[0]+dy_dx[i][0]
		x=now[1]+dy_dx[i][1]
		if 0<=y<h and 0<=x<w:
			if s[y][x]!="#" and visited[y][x] == -1:
				visited[y][x]=0
				queue.append([y,x])

cost=0
while True:
	cost+=1
	if cost==10:
		print(visited[dh-1][dw-1])
		sys.exit()
	for i in range(h):
		for j in range(w):
			if visited[i][j]==cost-1:
				for r in warp:
					y=i+r[0]
					x=j+r[1]
					if 0<=y<h and 0<=x<w:
						if s[y][x]!="#" and visited[y][x] == -1:
							visited[y][x]=cost
							queue.append([y,x])

	if len(queue)==0:
		print(visited[dh-1][dw-1])
		sys.exit()
	while len(queue)>0:
		now=queue.pop(0)
		for i in range(4):
			y=now[0]+dy_dx[i][0]
			x=now[1]+dy_dx[i][1]
			if 0<=y<h and 0<=x<w:
				if s[y][x]!="#" and visited[y][x] == -1:
					visited[y][x]=1
					queue.append([y,x])

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(input()) for i in range(h)]
visited=[[-1 for i in range(w)] for i in range(h)]
queue=[]

queue.append([ch-1,cw-1])
visited[ch-1][cw-1]=0

dy_dx=[[1,0],[0,1],[-1,0],[0,-1]]
warp=[]
for i in range(-2,3):
	for j in range(-2,3):
		if i!=0 or j!=0:
			warp.append([i,j])

while len(queue)>0:
	now=queue.pop(0)
	for i in range(4):
		y=now[0]+dy_dx[i][0]
		x=now[1]+dy_dx[i][1]
		if 0<=y<h and 0<=x<w:
			if s[y][x]!="#" and visited[y][x] == -1:
				visited[y][x]=0
				queue.append([y,x])

cost=0
while True:
	cost+=1
	if cost==100:
		print(visited[dh-1][dw-1])
		sys.exit()
	for i in range(h):
		for j in range(w):
			if visited[i][j]==cost-1:
				for r in warp:
					y=i+r[0]
					x=j+r[1]
					if 0<=y<h and 0<=x<w:
						if s[y][x]!="#" and visited[y][x] == -1:
							visited[y][x]=cost
							queue.append([y,x])

	if len(queue)==0:
		print(visited[dh-1][dw-1])
		sys.exit()
	while len(queue)>0:
		now=queue.pop(0)
		for i in range(4):
			y=now[0]+dy_dx[i][0]
			x=now[1]+dy_dx[i][1]
			if 0<=y<h and 0<=x<w:
				if s[y][x]!="#" and visited[y][x] == -1:
					visited[y][x]=1
					queue.append([y,x])

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(input()) for i in range(h)]
visited=[[-1 for i in range(w)] for i in range(h)]
queue=[]

queue.append([ch-1,cw-1])
visited[ch-1][cw-1]=0

dy_dx=[[1,0],[0,1],[-1,0],[0,-1]]
warp=[]
for i in range(-2,3):
	for j in range(-2,3):
		if i!=0 or j!=0:
			warp.append([i,j])

while len(queue)>0:
	now=queue.pop(0)
	for i in range(4):
		y=now[0]+dy_dx[i][0]
		x=now[1]+dy_dx[i][1]
		if 0<=y<h and 0<=x<w:
			if s[y][x]!="#" and visited[y][x] == -1:
				visited[y][x]=0
				queue.append([y,x])

cost=0
while True:
	cost+=1
	if cost==5:
		print(visited[dh-1][dw-1])
		sys.exit()
	for i in range(h):
		for j in range(w):
			if visited[i][j]==cost-1:
				for r in warp:
					y=i+r[0]
					x=j+r[1]
					if 0<=y<h and 0<=x<w:
						if s[y][x]!="#" and visited[y][x] == -1:
							visited[y][x]=cost
							queue.append([y,x])

	if len(queue)==0:
		print(visited[dh-1][dw-1])
		sys.exit()
	while len(queue)>0:
		now=queue.pop(0)
		for i in range(4):
			y=now[0]+dy_dx[i][0]
			x=now[1]+dy_dx[i][1]
			if 0<=y<h and 0<=x<w:
				if s[y][x]!="#" and visited[y][x] == -1:
					visited[y][x]=1
					queue.append([y,x])

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = map(int, input().split())
c = tuple(map(int, input().split()))
d = tuple(map(int, input().split()))
m = ['#' for _ in range(h+2)]
m[0] += '#'*w
m[h+1] += '#'*w
que = deque()
que.append(c)
warp = [[10**3 for _ in range(w+1)] for _ in range(h+1)]
for i in range(1,h+1):  m[i] += input()+'#'
up = lambda x,y: 1 if 0<x-1 and m[x-1][y]=='.' else 0
down = lambda x,y: 1 if x+1<=h and m[x+1][y]=='.' else 0
right = lambda x,y: 1 if y+1<=w and m[x][y+1]=='.' else 0
left = lambda x,y: 1 if 0<y-1 and m[x][y-1]=='.' else 0

def jump(x,y,cost):
  deq = deque()
  for i in range(x-2,x+3):
    if i<=0 or h<i:  continue
    for j in range(y-2,y+3):
      if j<=0 or w<j:  continue
      if m[i][j] == '.' and warp[i][j]>cost+1:
        warp[i][j] = cost+1
        if (i,j) not in que:
          deq.append((i,j))
  return deq
  
warp[c[0]][c[1]] = 0
while que:
  q = que.popleft()
  row,col = q[0],q[1]
  cost = warp[row][col]
  if up(row,col) and warp[row-1][col]>cost:
    if (row-1,col) in que: que.remove((row-1,col))
    que.appendleft((row-1,col))
    warp[row-1][col] = cost
  if down(row,col) and warp[row+1][col]>cost:
    if (row+1,col) in que: que.remove((row+1,col))
    que.appendleft((row+1,col))
    warp[row+1][col] = cost
  if right(row,col) and warp[row][col+1]>cost:
    if (row,col+1) in que: que.remove((row,col+1))
    que.appendleft((row,col+1))
    warp[row][col+1] = cost
  if left(row,col) and warp[row][col-1]>cost:
    if (row,col-1) in que: que.remove((row,col-1))
    que.appendleft((row,col-1))
    warp[row][col-1] = cost
  que.extend(jump(row,col,cost))

if warp[d[0]][d[1]] != 10**3: print(warp[d[0]][d[1]])
else: print(-1)

Submission status: Wrong Answer

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

s = [list(input()) for _ in range(H)]

from heapq import heappop, heappush
q = []
heappush(q, (0, ch-1, cw-1))
e = {(ch-1, cw-1): 0}

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while q:
    t, hh, ww = heappop(q)
    print(t, hh, ww)
    if hh == (eh - 1) and ww == (ew - 1):
        print(t)
        exit(0)

    for dh, dw in d:
        h, w = hh+dh, ww+dw
        if h < 0 or h > H-1 or w < 0 or w > W-1:
            continue
        if s[h][w] == '#':
            continue
        if (h, w) in e and e[(h, w)] <= t:
            continue
        e[(h, w)] = t
        heappush(q, (t, h, w))
    for dh in range(-2,3):
        for dw in range(-2,3):
            h, w = hh + dh, ww + dw
            if h < 0 or h > H - 1 or w < 0 or w > W - 1:
                continue
            if s[h][w] == '#':
                continue
            if (h, w) in e and e[(h, w)] <= t+1:
                continue
            e[(h, w)] = t+1
            heappush(q, (t+1, h, w))

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = map(int, input().split())
c = tuple(map(int, input().split()))
d = tuple(map(int, input().split()))
m = ['#' for _ in range(h+2)]
m[0] += '#'*w
m[h+1] += '#'*w
que = deque()
que.append(c)
warp = [[10**3 for _ in range(w+1)] for _ in range(h+1)]
for i in range(1,h+1):  m[i] += input()+'#'
up = lambda x,y: 1 if 0<x-1 and m[x-1][y]=='.' else 0
down = lambda x,y: 1 if x+1<=h and m[x+1][y]=='.' else 0
right = lambda x,y: 1 if y+1<=w and m[x][y+1]=='.' else 0
left = lambda x,y: 1 if 0<y-1 and m[x][y-1]=='.' else 0

def jump(x,y,cost):
  deq = deque()
  for i in range(x-2,x+3):
    if i<=0 or h<i:  continue
    for j in range(y-2,y+3):
      if j<=0 or w<j:  continue
      if m[i][j] == '.' and warp[i][j]>cost+1:
        warp[i][j] = cost+1
        deq.append((i,j))
  return deq
  
warp[c[0]][c[1]] = 0
while que:
  q = que.popleft()
  row = q[0]
  col = q[1]
  cost = warp[row][col]
  if up(row,col) and warp[row-1][col]>cost:
    que.appendleft((row-1,col))
    warp[row-1][col] = cost
  if down(row,col) and warp[row+1][col]>cost:
    que.appendleft((row+1,col))
    warp[row+1][col] = cost
  if right(row,col) and warp[row][col+1]>cost:
    que.appendleft((row,col+1))
    warp[row][col+1] = cost
  if left(row,col) and warp[row][col-1]>cost:
    que.appendleft((row,col-1))
    warp[row][col-1] = cost
  que.extend(jump(row,col,cost))

if warp[d[0]][d[1]] != 10**3:  print(warp[d[0]][d[1]])
else:  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split(" "))
sy,sx = map(int,input().split(" "))
gy,gx = map(int,input().split(" "))
sx-=1
sy-=1
gx-=1
gy-=1

field = [ list(input()) for i in range(H) ]
dx = ( 1, 0,-1, 0 )
dy = ( 0, 1, 0,-1 )
wx = ( 2, 2, 2, 1, 1, 0,-1,-1,-2,-2,-2,-2,-1,-2,-1, 0, 1, 1, 2, 2 )
wy = ( 0, 1, 2, 1, 2, 2, 2, 1, 2, 1, 0,-1,-1,-2,-2,-2,-2,-1,-2,-1 )

q = deque()
q.append( (sx,sy) )

q_warp = deque()

dist_ = [ [ -1 for i in range(W) ] for i in range(H)  ]
dist_warp = [ [ -1 for i in range(W) ] for i in range(H)  ]
dist_[sy][sx] = 0
dist_warp[sy][sx] = 0
warp_num = 0

while True:
    while len(q) != 0:
        # 親ループ位置座標設定
        x,y = q.popleft()

        for direction in range(4):
            # 子ループ（徒歩）位置座標設定
            next_x = x + dx[direction]
            next_y = y + dy[direction]

            if W <= next_x or H <= next_y or next_x < 0 or next_y < 0:
                continue
            if field[next_y][next_x] == '#':
                continue
            if dist_[next_y][next_x] != -1 :
                continue
            
            # 徒歩で行ける場所は同じワープ回数
            dist_warp[next_y][next_x] = warp_num
            
            dist_[next_y][next_x] = dist_[y][x] + 1
            q.append( ( next_x,next_y ) )

        for warp_direction in range(20):
            # 子ループ（ワープ）の位置座標設定
            warp_x = x + wx[warp_direction]
            warp_y = y + wy[warp_direction]

            # 対象位置が領域外は無視
            if W <= warp_x or H <= warp_y or warp_x < 0 or warp_y < 0:
                continue
            # 対象位置が壁は無視
            if field[warp_y][warp_x] == '#':
                continue
            # 対象位置のステップ数（徒歩）が既に印字されているなら無視
            if dist_[warp_y][warp_x] != -1 :
                continue
            # 対象位置のステップ数（ワープ）が既に印字されているなら無視
            if dist_warp[warp_y][warp_x] != -1:
                continue
            
            dist_warp[warp_y][warp_x] = dist_warp[y][x] + 1
            q_warp.append( ( warp_x,warp_y ) )

    if len(q_warp) <= 0:
        break
    else:
        # ワープする前準備
        warp_num += 1
        # ワープ後の位置座標を新しい親ループ位置座標として設定
        x,y = q_warp.popleft()
        if dist_[y][x] == -1:
            dist_[y][x] = 0
        q.append( (x,y) )


print(dist_warp[gy][gx])

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split(" "))
sy,sx = map(int,input().split(" "))
gy,gx = map(int,input().split(" "))
sx-=1
sy-=1

field = [ list(input()) for i in range(H) ]
dx = ( 1, 0,-1, 0 )
dy = ( 0, 1, 0,-1 )
wx = ( 2, 2, 2, 1, 1, 0,-1,-1,-2,-2,-2,-2,-1,-2,-1, 0, 1, 1, 2, 2 )
wy = ( 0, 1, 2, 1, 2, 2, 2, 1, 2, 1, 0,-1,-1,-2,-2,-2,-2,-1,-2,-1 )

q = deque()
q.append( (sx,sy) )

q_warp = deque()

dist_ = [ [ -1 for i in range(W) ] for i in range(H)  ]
dist_warp = [ [ -1 for i in range(W) ] for i in range(H)  ]
dist_[sy][sx] = 0
dist_warp[sy][sx] = 0
warp_num = 0

while True:
    while len(q) != 0:
        # 親フォーカス位置
        x,y = q.popleft()

        for direction in range(4):
            # 子フォーカス（徒歩）対象位置
            next_x = x + dx[direction]
            next_y = y + dy[direction]

            if W <= next_x or H <= next_y or next_x < 0 or next_y < 0:
                continue
            if field[next_y][next_x] == '#':
                dist_[next_y][next_x] = '#'
                continue
            if dist_[next_y][next_x] != -1 or dist_[next_y][next_x] == '#':
                continue
            
            # 徒歩で行ける場所は同じワープ回数
            dist_warp[next_y][next_x] = warp_num
            
            dist_[next_y][next_x] = dist_[y][x] + 1
            q.append( ( next_x,next_y ) )

        for warp_direction in range(20):
            # 子フォーカス（ワープ）の対象位置決定
            warp_x = x + wx[warp_direction]
            warp_y = y + wy[warp_direction]

            # 対象位置が領域外は無視
            if W <= warp_x or H <= warp_y or warp_x < 0 or warp_y < 0:
                continue
            # 対象位置が壁は無視
            if field[warp_y][warp_x] == '#':
                continue
            # 対象位置のステップ数（徒歩）が既に印字されているなら無視
            if dist_[warp_y][warp_x] != -1 or dist_[warp_y][warp_x] == '#':
                continue
            # 対象位置のステップ数（ワープ）が既に印字されているなら無視
            if dist_warp[warp_y][warp_x] != -1:
                continue
            
            dist_warp[warp_y][warp_x] = dist_warp[y][x] + 1
            q_warp.append( ( warp_x,warp_y ) )

    

    if len(q_warp) <= 0:
        break
    else:
        # ワープする前準備
        warp_num += 1
        # 新しい親フォーカス位置
        x,y = q_warp.popleft()
        if dist_[y][x] == -1:
            dist_[y][x] = 0
        q.append( (x,y) )


print(dist_warp[gy-1][gx-1])