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:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = deque([(Dh, Dw)])
    while True:
        bq = deque()
        while q:
            h, w = q.pop()
            # print('({}, {}) = {}'.format(h, w, ans))
            if h == Ch and w == Cw:
                print(ans)
                return True
            M[h][w] = '#'
            for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= h+dh < H and 0 <= w+dw < W:
                    if M[h+dh][w+dw] == '.':
                        q.append((h+dh, w+dw))
                    else:
                        bq.append((h+dh, w+dw))

        while bq:
            h, w = bq.pop()
            for dh in range(-1, 2):
                for dw in range(-1, 2):
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '.':
                            q.append((h+dh, w+dw))
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    H,W = LMIIS()
    Ch,Cw = LMIIS()
    Ch -= 1
    Cw -= 1
    Dh,Dw = LMIIS()
    Dh -= 1
    Dw -= 1
    S = []
    for i in range(H):
        S.append(input())
    
    num_warp = []
    for i in range(H):
        num_warp.append([-1]*W)
    num_warp[Ch][Cw] = 0
    
    targets_walk = deque([(Ch,Cw)])
    targets_warp = deque([(Ch,Cw)])

    def check_and_move(y,x,n):
        if 0 <= y < H and 0 <= x < W and num_warp[y][x] == -1 and S[y][x] == '.':
            num_warp[y][x] = n
            return True
        return False




    # BFS


    #　歩いて行ける範囲を全部いく
    while targets_walk:
        y,x = targets_walk.popleft()
        num_currrent_warp = num_warp[y][x]
        for y2,x2 in [(y-1,x),(y,x+1),(y+1,x),(y,x-1)]:
            if check_and_move(y2,x2,num_currrent_warp):
                    # 歩きの探索対象に追加
                    targets_walk.append((y2,x2))
                    # ワープの探索対象に追加
                    targets_warp.append((y2,x2))


    # 一回ワープ -> 歩いて行ける範囲を全部潰す
    while targets_warp:
            y,x = targets_warp.popleft()
            num_currrent_warp = num_warp[y][x]
            for y2,x2 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-2,x+2),
                    (y,x-2),(y,x+2),
                    (y+1,x-2),(y+1,x-1),(y+1,x+1),(y+1,x+2),
                    (y+2,x-2),(y+2,x-1),(y+2,x),(y+2,x+1),(y+2,x+2)
                ]:
                if check_and_move(y2,x2,num_currrent_warp+1):
                    targets_walk = deque([(y2,x2)])
                    while targets_walk:
                        y3,x3 = targets_walk.popleft()
                        for y4,x4 in [(y3-1,x3),(y3,x3+1),(y3+1,x3),(y3,x3-1)]:
                            if check_and_move(y4,x4,num_currrent_warp+1):
                                targets_walk.append((y4,x4))
                                targets_warp.append((y4,x4))



    ans = num_warp[Dh][Dw]
    print(-1 if ans == INF else ans)


    
main()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
c1, c2 = map(int,input().split())
d1, d2 = map(int,input().split())
data = []
for i in range(h):data.append(input())
ans = []
for i in range(h):ans.append([1e9]*w)

warp = [-2, -1, 0, 1, 2]
ans[c1-1][c2-1] = 0
for i in range(h):
    for j in range(w):


        for t1 in warp:
            for t2 in warp:
                if(i+t1 < 0 or j+t2 < 0 or i+t1 >= h or j+t2 >= w):continue
                if(data[t1+i][t2+j] == "#"):continue
                if(abs(t1)+abs(t2) <= 1 ):
                    ans[t1+i][t2+j] = min(ans[t1+i][t2+j], ans[i][j])
                else:
                    ans[t1+i][t2+j] = min(ans[t1+i][t2+j], ans[i][j]+1)

for i in range(h):
    for j in range(w):

        for t1 in warp:
            for t2 in warp:
                if(h-i-1+t1 < 0 or w-j-1+t2 < 0 or h-i-1+t1 >= h or w-j-1+t2 >= w):continue
                if(data[t1+h-i-1][t2+w-j-1] == "#"):continue
                if(abs(t1)+abs(t2) <= 1 ):
                    ans[t1+h-i-1][t2+w-j-1] = min(ans[t1+h-i-1][t2+w-j-1], ans[h-i-1][w-j-1])
                else:
                    ans[t1+h-i-1][t2+w-j-1] = min(ans[t1+h-i-1][t2+w-j-1], ans[h-i-1][w-j-1]+1)
if(ans[d1-1][d2-1] == 1e9):print(-1)
else:print(ans[d1-1][d2-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

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

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S
    

    stack = deque([(Ch,Cw,0)])
    seen = set()
    ans = INF
    X = [[INF]*W for _ in range(H)]
    while stack:
        h,w,magic = stack.popleft()

        # print(h,w,magic)
        X[h][w] = min(X[h][w],magic)
        if (h,w) in seen: continue

        seen.add((h,w))
        found_wall = False
        for dh,dw in [(-1,0),(1,0),(0,1),(0,-1)]:
            new_h,new_w = h+dh,w+dw
            if not (0<=new_h<H and 0<=new_w<W): continue
            if G[new_h][new_w] == "#": 
                found_wall = True
                continue
                
            stack.append((new_h,new_w,magic))

        if found_wall:
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    if new_h == 0 and new_w == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    
                    stack.append((new_h,new_w,magic+1))


    if X[Dh][Dw] == INF:
        print(-1)
    else:
        print(X[Dh][Dw])
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def wapu(now):
    pass

def dfs(x,y,ans,u,goal,h,w,c):
    global l
    if not(0 <= x < h) or not(0 <= y < w) or c[x][y] == "#" or c[x][y] == "o": # 壁に当たったり、探索範囲外になった場合はreturn
        ans = -1
        return
    if c[x][y] == "G":
        l.append(ans)
        return
    c[x][y] = "o"
    dfs(x+1,y,ans,u,goal,h,w,c)
    dfs(x-1,y,ans,u,goal,h,w,c)
    dfs(x,y+1,ans,u,goal,h,w,c)
    dfs(x,y-1,ans,u,goal,h,w,c)
    if 0 <= x+2 < h and c[x+1][y] == "#" and (c[x+2][y] == "." or c[x+2][y] == "G"):
        ans += 1
        dfs(x+2,y,ans,u,goal,h,w,c)
    if 0 <= x-2 < h and c[x-1][y] == "#" and (c[x-2][y] == "." or c[x-2][y] == "G"):
        ans += 1
        dfs(x-2,y,ans,u,goal,h,w,c)
    if 0 <= y+2 < w and c[x][y+1] == "#" and (c[x][y+2] == "." or c[x][y+2] == "G"):
        ans += 1
        dfs(x,y+2,ans,u,goal,h,w,c)
    if 0 <= y-2 < w and c[x][y-1] == "#" and (c[x][y-2] == "." or c[x][y-2] == "G"):
        ans += 1
        dfs(x,y-2,ans,u,goal,h,w,c)
    if 0 <= x+1 < h and 0 <= y+2 < w and (c[x+1][y+2]=="." or c[x+1][y+2]=="G"):
        ans += 1
        dfs(x+1,y+2,ans,u,goal,h,w,c)
    if 0 <= y+1 < w and 0 <= x+2 < h and (c[x+2][y+1]=="." or c[x+2][y+1]=="G"):
        ans += 1
        dfs(x+2,y+1,ans,u,goal,h,w,c)
    if 0 <= x+2 < h and 0 <= y+2 < w and (c[x+2][y+2]=="." or c[x+2][y+2]=="G"):
        ans += 1
        dfs(x+2,y+2,ans,u,goal,h,w,c)
    if 0 <= y-1 < w and 0 <= x+2 < h and (c[x+2][y-1]=="." or c[x+2][y-1]=="G"):
        ans += 1
        dfs(x+2,y-1,ans,u,goal,h,w,c)
    if 0 <= x+1 < h and 0 <= y-2 < w and (c[x+1][y-2]=="." or c[x+1][y-2]=="G"):
        ans += 1
        dfs(x+1,y-2,ans,u,goal,h,w,c)
    if 0 <= x+2 < h and 0 <= y-2 < w and (c[x+2][y-2]=="." or c[x+2][y-2]=="G"):
        ans += 1
        dfs(x+2,y-2,ans,u,goal,h,w,c)
    if 0 <= x-1 < h and 0 <= y+2 < w and (c[x-1][y+2]=="." or c[x-1][y+2]=="G"):
        ans += 1
        dfs(x-1,y+2,ans,u,goal,h,w,c)
    if 0 <= y+1 < w and 0 <= x-2 < h and (c[x-2][y+1]=="." or c[x-2][y+1]=="G"):
        ans += 1
        dfs(x-2,y+1,ans,u,goal,h,w,c)
    if 0 <= x-2 < h and 0 <= y+2 < w and (c[x-2][y+2]=="." or c[x-2][y+2]=="G"):
        ans += 1
        dfs(x-2,y+2,ans,u,goal,h,w,c)
    if 0 <= x-1 < h and 0 <= y-2 < w and (c[x-1][y-2]=="." or c[x-1][y-2]=="G"):
        ans += 1
        dfs(x-1,y-2,ans,u,goal,h,w,c)
    if 0 <= y-1 < w and 0 <= x-2 < h and (c[x-2][y-1]=="." or c[x-2][y-1]=="G"):
        ans += 1
        dfs(x-2,y-1,ans,u,goal,h,w,c)
    if 0 <= x-2 < h and 0 <= y-2 < w and (c[x-2][y-2]=="." or c[x-2][y-2]=="G"):
        ans += 1
        dfs(x-2,y-2,ans,u,goal,h,w,c)




l = []

def solve():
    global l
    #n = int(stdin.readline().rstrip())
    h,w = map(int, stdin.readline().rstrip().split())
    mahou = list(map(int, stdin.readline().rstrip().split()))
    goal = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    c = [list(input()) for i in range(h)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    ans = 0
    u = 999999
    c[goal[0]-1][goal[1]-1] = "G"
    dfs(mahou[0]-1,mahou[1]-1,ans,u,goal,h,w,c)
    if len(l) == 0:
        print(-1)
    else:
        print(min(l))





if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
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

start = (Ch, Cw)

S = ['#'*(W+4)]
S.append('#'*(W+4))
for k in range(H):
  S.append('##' + input() + '##')
S.append('#'*(W+4))
S.append('#'*(W+4))

counter = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      counter[k][j] = 10**7

counter[Ch][Cw] = 0

#print(counter)
#print(S)

now = [start]
for item in now:
  x = item[0]
  y = item[1]
  if counter[x+1][y] == 10**7:
    counter[x+1][y] = 0
    now.append((x+1, y))
  if counter[x][y+1] == 10**7:
    counter[x][y+1] = 0
    now.append((x, y+1))
  if counter[x-1][y] == 10**7:
    counter[x-1][y] = 0
    now.append((x-1, y))
  if counter[x][y-1] == 10**7:
    counter[x][y-1] = 0
    now.append((x, y-1))

#print(counter)
if counter[Dh][Dw] == 0:
  print(0)
  exit()
ans = 0
while counter[Dh][Dw] == 10**7:
  if len(now) == 0:
    print(-1)
    exit() 
  nextlist = []
  ans += 1
  for item in now:
    x = item[0]
    y = item[1]
    if counter[x+2][y+2] > ans:
      counter[x+2][y+2] = ans
      nextlist.append((x+2, y+2))
    if counter[x+2][y+1] > ans:
      counter[x+2][y+1] = ans
      nextlist.append((x+2, y+1))
    if counter[x+2][y] > ans:
      counter[x+2][y] = ans
      nextlist.append((x+2, y))
    if counter[x+2][y-1] > ans:
      counter[x+2][y-1] = ans
      nextlist.append((x+2, y-1))
    if counter[x+2][y-2] > ans:
      counter[x+2][y-2] = ans
      nextlist.append((x+2, y-2))
    if counter[x+1][y+2] > ans:
      counter[x+1][y+2] = ans
      nextlist.append((x+1, y+2))
    if counter[x+1][y-2] > ans:
      counter[x+1][y-2] = ans
      nextlist.append((x+1, y-2))
    if counter[x][y+2] > ans:
      counter[x][y+2] = ans
      nextlist.append((x, y+2))
    if counter[x][y-2] > ans:
      counter[x][y-2] = ans
      nextlist.append((x, y-2))
    if counter[x-2][y+2] > ans:
      counter[x-2][y+2] = ans
      nextlist.append((x-2, y+2))
    if counter[x-2][y+1] > ans:
      counter[x-2][y+1] = ans
      nextlist.append((x-2, y+1))
    if counter[x-2][y] > ans:
      counter[x-2][y] = ans
      nextlist.append((x-2, y))
    if counter[x-2][y-1] > ans:
      counter[x-2][y-1] = ans
      nextlist.append((x-2, y-1))
    if counter[x-2][y-2] > ans:
      counter[x-2][y-2] = ans
      nextlist.append((x-2, y-2))
    if counter[x-1][y+2] > ans:
      counter[x-1][y+2] = ans
      nextlist.append((x-1, y+2))
    if counter[x-1][y-2] > ans:
      counter[x-1][y-2] = ans
      nextlist.append((x-1, y-2))
  
  
  for item in nextlist:
    x = item[0]
    y = item[1]
    if counter[x+1][y] > ans:
      counter[x+1][y] = ans
      nextlist.append((x+1, y))
    if counter[x][y+1] > ans:
      counter[x][y+1] = ans
      nextlist.append((x, y+1))
    if counter[x-1][y] > ans:
      counter[x-1][y] = ans
      nextlist.append((x-1, y))
    if counter[x][y-1] > ans:
      counter[x][y-1] = ans
      nextlist.append((x, y-1))
  now = nextlist
  if ans > 10**7:
    print(-1)
    exit()
print(ans)

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())
field = [["#"] * (w + 4)] + \
        [["#"] * (w + 4)] + \
        [list("##" + input() + "##") for i in range(h)] + \
        [["#"] * (w + 4)] + \
        [["#"] * (w + 4)]
sy += 1
sx += 1
gy += 1
gx += 1          
          
dxy1 = [(0,1), (0,-1), (1,0), (-1,0)]
dxy2 = [(1,1), (1,-1), (-1,1), (-1,-1), \
        (-2,-2), (-1,-2), (0,-2), (1,-2), (2,-2), \
        (-2,-1), (2,-1), (-2,0), (2,0), (-2,1), (2,1), \
        (-2,2), (-1,2), (0,2), (1,2), (2,2)]


goal = False
INF = 10**4
cnt = [[INF]*(w+4) for i in range(h+4)]

q = deque()
q.append([sy, sx])
cnt[sy][sx] = 0

while goal == False and q:
    y, x = q.pop()
    now = cnt[y][x]
    flg = False
    for dy, dx in dxy1:
        ny, nx = y + dy, x + dx
        if ny == gy and nx == gx:
            cnt[ny][nx] = now
            goal = True
            flg = True
            break
        if field[ny][nx] == '#':
            continue
        if field[ny][nx] == '.' and cnt[ny][nx] > now:
            q.append([ny, nx])
            cnt[ny][nx] = now
            flg = True
    if goal:
        break
    for dy, dx in dxy2:
        ny, nx = y + dy, x + dx
        if field[ny][nx] == '#':
            continue
        if field[ny][nx] == '.' and cnt[ny][nx] > now + 1:
            q.appendleft([ny, nx])
            cnt[ny][nx] = now + 1
print(cnt[gy][gx]) if cnt[gy][gx] < INF else print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
  d = [[float('inf')]*w for i in range(h)]
  
  dx = [1, 0, -1, 0]
  dy = [0, 1, 0, -1]
  ex = [2, 1, 0, -1, -2, 2, -2, 2, -2, 2, -2, 2, 1, 0, -1, -2, 1, 1, -1, -1]
  ey = [2, 2, 2, 2, 2, 1, 1, 0, 0, -1, -1, -2, -2, -2, -2, -2, 1, -1, 1, -1]
  
  que = deque([])
  que.append((ch, cw))
  d[ch][cw] = 0
  
  while que:
    p = que.popleft()
    if p[0]==dh and p[1]==dw:
      break
    for i in range(4):
      nx = p[0] + dx[i]
      ny = p[1] + dy[i]
      if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and d[nx][ny]==float('inf'):
        que.append((nx, ny))
        d[nx][ny] = min(d[nx][ny], d[p[0]][p[1]])
      elif 0<=nx<h and 0<=ny<w and maze[nx][ny]=='#'and d[nx][ny]==float('inf'):
        for j in range(19):
          nx = p[0] + ex[j]
          ny = p[1] + ey[j]
          if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and d[nx][ny]==float('inf'):
            que.append((nx, ny)) 
            d[nx][ny] = min(d[nx][ny], d[p[0]][p[1]]+1)
            
              
  return d[dh][dw]
        
  
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)]

if bfs()==float('inf'):
  print(-1)
else:
  print(bfs())

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys
    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
    S = [input() for _ in range(H)]
    d = [[0]*W for _ in range(H)]

    que = deque([[cw, ch]])
    count = 0
    while que:
        while que:
            x, y = que.popleft()
            if x == dw and y == dh:
                print(count)
                sys.exit()
                
            d[y][x] = -1
            for i in range(-2, 3):
                for j in range(-2, 3):
                    nnx, nny = x+i, y+j
                    if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                        d[nny][nnx] = 1
        
            for dx, dy in [1, 0], [0, 1], [-1, 0], [0, -1]:
                nx, ny = x+dx, y+dy
                if 0<=nx<W and 0<=ny<H and S[ny][nx]!='#' and d[ny][nx]!=-1:
                    if nx == dw and ny == dh:
                        print(count)
                        sys.exit()
                
                    d[ny][nx] = -1
                    for i in range(-2, 3):
                        for j in range(-2, 3):
                            nnx, nny = nx+i, ny+j
                            if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                                d[nny][nnx] = 1
                    que.append([nx, ny])
                    
        count += 1
    print(-1)
main()

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, c0, c1, d0, d1, arr):
    c0 = c0 - 1
    c1 = c1 - 1
    d0 = d0 - 1
    d1 = d1 - 1

    status = []
    for i in range(H):
        tmp = []
        for j in range(W):
            tmp.append(-1)
        status.append(tmp)

    q = deque()

    q.append((c0, c1, 0))

    while len(q) > 0:
        hIndex, wIndex, index = q.popleft()

        if hIndex == d0 and wIndex == d1:
            break


        for _hIndex in range(hIndex - 2, hIndex + 3):
            for _wIndex in range(wIndex - 2, wIndex + 3):
                if (_hIndex == hIndex) and (_wIndex == wIndex):
                    continue
                if ( _hIndex == c0) and (_wIndex == c1):
                    continue
                if (_hIndex >= 0 and _hIndex < h) and (_wIndex >= 0 and _wIndex < w):
                    if arr[_hIndex][_wIndex] == '.':
                        if status[_hIndex][_wIndex] == 0:
                            continue
                        if (_hIndex == hIndex) and (_wIndex == (wIndex - 1)):
                            tmpIndex = index
                        elif (_hIndex == hIndex) and (_wIndex == (wIndex + 1)):
                            tmpIndex = index
                        elif (_wIndex == wIndex) and (_hIndex == (hIndex - 1)):
                            tmpIndex = index
                        elif (_wIndex == wIndex) and (_hIndex == (hIndex + 1)):
                            tmpIndex = index
                        else:
                            tmpIndex = index + 1

                        if status[_hIndex][_wIndex] == -1:
                            status[_hIndex][_wIndex] = tmpIndex
                            q.append((_hIndex, _wIndex, tmpIndex))
                        else:
                            if status[_hIndex][_wIndex] > tmpIndex:
                                status[_hIndex][_wIndex] = tmpIndex
                                q.append((_hIndex, _wIndex, tmpIndex))

    if status[d0][d1] >= 0:
        print(status[d0][d1])
    else:
        print(-1)



calculate(H, W, C0, C1, D0, D1, ARR)

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] = 0
ans = -2
while True:
    # つながっているエリアを探索
    while q:
        i, j, wc = q.popleft()
        # Dがあったら終了
        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] != wc:
                    visited[ni][nj] = wc
                    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 or visited[ni][nj] > wc+1)):
                visited[ni][nj] = wc+1
                q.append([ni, nj, wc+1])
                wall.append([ni, nj, wc+1])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    # import sys
    # input = sys.stdin.readline
    dh = [-1,0,1,0]
    dw = [0,-1,0,1]
    dh2 = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
    dw2 = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
    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)]
    # print(S)
    # ans = 0
    d = deque()
    d.append([Ch,Cw])
    warp = 0
    warp_moto = [(Ch,Cw)]
    move = [[-1 for i in range(W)] for j in range(H)]
    move[Ch][Cw] = 0
    while True:
        while len(d)>0:
            p_h,p_w = d.popleft()
            # print(p_h)
            for i in range(4):
                # print(dh[i])
                # print(dw[i])
                n_h,n_w = p_h+dh[i], p_w+dw[i]
                if(n_h<H and n_h>=0 and n_w<W and n_w>=0):
                    if(S[n_h][n_w]=='.' and move[n_h][n_w] == -1):
                        move[n_h][n_w] = warp
                        d.append([n_h,n_w])
                        warp_moto.append((n_h,n_w))
        # print(move)
        # ゴール
        if move[Dh][Dw] != -1:
            print(move[Dh][Dw])
            return
        # ゴールできていないならワープ
        else:
            # print(warp_moto)
            can_warp = False
            warp += 1
            for p in warp_moto:
                for i in range(24):
                    n_h,n_w = p[0]+dh2[i], p[1]+dw2[i]
                    # print((n_h,n_w))
                    if(n_h<H and n_h>=0 and n_w<W and n_w>=0):
                        if S[n_h][n_w]=='.' and move[n_h][n_w] == -1:
                            move[n_h][n_w] = warp
                            can_warp = True
                            d.append([n_h,n_w])
            warp_moto = []
            # ワープできなかったら終了
            if not can_warp:
                print(-1)
                return
 
if __name__ == '__main__':
    main()

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)]
visited[ch][cw] = 0
q = deque([[ch, cw]])
dq = 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])
                    dq.append([ny,nx])
    if len(q) == 0:
        # ワープ処理
        while dq:
            ry,rx = dq.popleft()
            ty,tx = ry-2, rx-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])
if visited[dh][dw] != inf:
    print(visited[dh][dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
"""
dp[i][j] => マスi,jに到達するのに必要なワープ回数。
近隣5*5のマスから
"""


def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

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

    que = deque([(Ch,Cw,0)])
    adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
    while que:
        h,w,worp = que.popleft()
        if h==Dh and w==Dw:
            print(worp)
            exit()
        if maze[h][w] == "#" or (maze[h][w]!="." and maze[h][w] <= worp):
            continue
        else:
            maze[h][w] = worp
            for a,b in adjecents:
                nxh,nxw = h+a,w+b
                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw]>worp):
                    que.append((nxh,nxw,worp))
                elif 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]=="#":
                    for i in range(-2,3,1):
                        for j in range(-2,3,1):
                            nxh,nxw = h+i,w+j
                            if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw] > worp+1):
                                que.append((nxh,nxw,worp+1))
    
    if maze[Dh][Dw] == "#" or maze[Dh][Dw] == ".":
        print(-1)
    else:
        print(maze[Dh][Dw])
main()