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 d_wizard_in_maze():
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Start_row, Start_col = [int(i) - 1 for i in input().split()]
    Goal_row, Goal_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    neighbor = ((-1, 0), (1, 0), (0, -1), (0, 1))  # 上下左右
    warp = tuple((i, j) for i in range(-2, 3) for j in range(-2, 3)
                 if (i, j) not in neighbor)
    # dist[r][c]: スタートから (r, c) に到達するために必要なワープ回数の最小値
    dist = [[10000] * W for _ in range(H)]

    def can_move(row, col):
        return 0 <= row < H and 0 <= col < W and Grid[row][col] == '.'

    def next_query(row, col, time, _next, cost):
        for dr, dc in _next:
            nr, nc = row + dr, col + dc
            if can_move(nr, nc) and time < dist[nr][nc]:
                if cost == 0:
                    queue.append((nr, nc, time))
                else:
                    queue.appendleft((nr, nc, time + 1))

    queue = deque([(Start_row, Start_col, 0)])
    while queue:
        row, col, time = queue.pop()
        if time > dist[row][col]:
            continue  # キューに入れた時点では候補だったが、後に歩いて行けるとわかった

        dist[row][col] = time
        if row == Goal_row and col == Goal_col:
            break

        next_query(row, col, time, neighbor, 0)
        next_query(row, col, time, warp, 1)
    return -1 if dist[Goal_row][Goal_col] == 10000 else dist[Goal_row][Goal_col]

print(d_wizard_in_maze())

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    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 = tuple(['#'] * (w + 4))
    maze = {e: [] for e in range(h + 4)}
    maze[0] = dummy
    maze[1] = dummy
    for i in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze[i+2] = row
    maze[h+2] = dummy
    maze[h+3] = dummy
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'

    next_nodes = deque()
    next_nodes.append((0, ch, cw))
    res = []
    while next_nodes:
        (d, nextny, nextnx) = next_nodes.popleft()
        flag = False
        for j1 in range(4):
            ny = nextny + movey[j1]
            nx = nextnx + movex[j1]
            if maze[ny][nx] == 'g':
                res.append(d)
            elif maze[ny][nx] == '.':
                maze[ny][nx] = '+'
                if (d+1, ny, nx) in next_nodes:
                    next_nodes.remove((d+1, ny, nx))
                if (d, ny, nx) not in next_nodes:
                    next_nodes.appendleft((d, ny, nx))
            elif maze[ny][nx] == '#':
                flag = True
        if flag:
            for j1 in range(20):
                ny = nextny + warpy[j1]
                nx = nextnx + warpx[j1]
                nextg = maze[ny][nx]
                if maze[ny][nx] == 'g':
                    res.append(d+1)
                elif nextg == '.':
                    maze[ny][nx] = '+'
                    if (d+1, ny, nx) not in next_nodes and (d, ny, nx) not in next_nodes :
                        next_nodes.append((d+1, ny, nx))
    if res:
        print(min(res))
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    sh,sw = map(int, input().split())
    gh,gw = map(int, input().split())
    gh,gw = gh-1,gw-1
    field = [list(input()) for _ in range(H)]
    zeroq = []
    oneq = []
    zeroq.append((0, sh-1, sw-1))
    INF = 10 ** 30
    dist = [[INF] * W for _ in range(H)]
    dist[sh-1][sw-1] = 0
    while oneq or zeroq:
        if zeroq:
            cnt, h, w = zeroq.pop()
        else:
            cnt, h, w = oneq.pop()
        if dist[h][w] < cnt: continue
        if h == gh and w == gw: return cnt
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh = h+i
                nw = w+j
                if nh < 0 or nw < 0: continue
                if nh >= H or nw >= W: continue
                if field[nh][nw]  == "#": continue
                if (i, j) in ((1,0),(0,1),(-1,0),(0,-1)):
                    if dist[nh][nw] <= cnt: continue
                    dist[nh][nw] = cnt
                    zeroq.append((cnt, nh, nw))
                else:
                    if dist[nh][nw] <= cnt+1: continue
                    dist[nh][nw] = cnt+1
                    oneq.append((cnt+1, nh, nw))
    return -1

print(main())

Submission status: Wrong Answer

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

l = [input() for i in range(h)]

save = [[False]*w for i in range(h)]

queue = [[ch,cw,0]]
ans = -1
while(queue):
    now_h,now_w,now_c = queue.pop(0)
    if(now_h==dh and now_w==dw):
        ans = now_c
        break

    for i in range(-2,3):
        for j in range(-2,3):
            if(i==0 and j==0):
                continue
            nex_h,nex_w = now_h+i,now_w+j

            if(nex_h<0 or nex_h>=h or nex_w<0 or nex_w>=w):
                continue
            
            if(save[nex_h][nex_w]):
                continue
            save[nex_h][nex_w]=True
            if(l[nex_h][nex_w]=="#"):
                continue
            
            mul = abs(i*j)
            if(mul==1):
                queue.append([nex_h,nex_w,now_c])
            else:
                queue.append([nex_h,nex_w,now_c+1])

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())
map_list = []
for i in range(H):
    str_input = input()
    map_list.append(list(str_input))

walk = [[1,0], [-1,0], [0,1], [0,-1]] #　下　上　右　左
warp = [[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]]

dist = [[10000 for _ in range(W)] for i in range(H)] #10^3より大きい値

d = deque()
d.append([sy-1, sx-1])
dist[sy-1][sx-1] = 0

#BFS実行部分
while d:
    y,x = d.popleft()
    for dy,dx in walk:
        new_x = x + dx
        new_y = y + dy
        if 0 <= new_y < H and 0 <= new_x < W and map_list[new_y][new_x] == '.' and dist[new_y][new_x] > dist[y][x]:
            dist[new_y][new_x] = dist[y][x]
            d.appendleft([new_y, new_x]) #コスト低い方を優先して取り出すために先頭に追加
    for dy, dx in warp:
        new_x = x + dx
        new_y = y + dy
        if 0 <= new_y < H and 0 <= new_x < W and map_list[new_y][new_x] == '.' and dist[new_y][new_x] > dist[y][x] + 1:
            dist[new_y][new_x] = dist[y][x] + 1
            d.append([new_y, new_x]) #コストが高いので優先順位低い　最高尾に追加

#print(dist)
ans = dist[gy-1][gx-1]
if ans == 10000:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from copy import deepcopy
def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    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 = tuple(['#'] * (w + 4))
    maze = {e: [] for e in range(h + 4)}
    maze[0] = dummy
    maze[1] = dummy
    for i in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze[i+2] = row
    maze[h+2] = dummy
    maze[h+3] = dummy
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'

    next_nodes = deque()
    next_nodes.append((ch, cw))
    next2_nodes = deque()
    cnt = 0
    while next_nodes:
        while next_nodes:
            (nextny, nextnx) = next_nodes.popleft()
            flag = False
            curg = maze[nextny][nextnx]
            for j1 in range(4):
                ny = nextny + movey[j1]
                nx = nextnx + movex[j1]
                if maze[ny][nx] == 'g':
                    print(curg)
                    sys.exit()
                elif maze[ny][nx] == '.':
                    maze[ny][nx] = curg
                    if (ny, nx) in next_nodes:
                        next_nodes.remove((ny, nx))
                    next2_nodes.appendleft((ny, nx))
                elif maze[ny][nx] == '#':
                    flag = True
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.appendleft((ny, nx))
            if flag:
                for j1 in range(20):
                    ny = nextny + warpy[j1]
                    nx = nextnx + warpx[j1]
                    nextg = maze[ny][nx]
                    if nextg == 'g':
                        print(curg + 1)
                        sys.exit()
                    elif nextg == '.':
                        next2_nodes.append((ny, nx))
                        maze[ny][nx] = curg + 1
                    elif nextg == '#':
                        pass
                    elif nextg > curg + 1:
                        maze[ny][nx] = curg + 1
                        next2_nodes.append((ny, nx))
        next_nodes = deepcopy(next2_nodes)
        next2_nodes = deque()
    

    print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    try:
        for dh,dw in D:
            to_h, to_w=fro_h+dh, fro_w+dw
            if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
                if kyori < d[(to_h, to_w)]:
                    d[(to_h, to_w)]=kyori
                    q.appendleft((kyori, to_h, to_w))
    except:
        pass
    try:
        #ワープ
        for dh,dw in WARP:
            to_h, to_w=fro_h+dh, fro_w+dw
            if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
                if kyori+1 < d[(to_h, to_w)]:
                    d[(to_h, to_w)]=kyori+1
                    q.append((kyori+1, to_h, to_w))
    except:
        pass

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        childy = py + dy
        childx = px + dx
        if 0 <= childx < w and 0 <= childy < h:
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    if meiro[gy][gx] != inf:
        break

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            warpx = px + dx
            warpy = py + dy
            if 0<=warpx<w and 0<=warpy<h:
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
S = [list(input()) for _ in range(H)]
INF = 10**3
cnt = [[INF]*W for _ in range(H)]
walk = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def jump(x, y, i):
  if i == 0:
    return [(x-2, y+2),(x-1, y+2),(x, y+2),(x+1, y+2),(x+2, y+2),(x-1, y+1),(x+1, y+1)]
  elif i == 1:
    return [(x+2, y+2),(x+2, y+1),(x+2, y),(x+2, y-1),(x+2, y-2),(x+1, y+1),(x+1, y-1)]
  elif i == 2:
    return [(x-2, y-2),(x-1, y-2),(x, y-2),(x+1, y-2),(x+2, y-2),(x-1, y-1),(x+1, y-1)]
  elif i == 3:
    return [(x-2, y+2),(x-2, y+1),(x-2, y),(x-2, y-1),(x-2, y-2),(x-1, y+1),(x-1, y-1)]
  
next_pos = [(c_h-1, c_w-1)]
warp = 0
jump_pos = []

while True:
  while next_pos:
    x, y = next_pos.pop(0)
    cnt[x][y] = warp
    for i in range(4):
      a, b = walk[i]
      walk_x, walk_y = x+a, y+b
      if walk_x < 0 or walk_x >= H or walk_y < 0 or walk_y >= W:
        continue
      elif S[walk_x][walk_y] == '#':
        jump_pos += jump(x, y, i)
      else:
        if cnt[walk_x][walk_y] <= warp:
          continue
        else:
          cnt[walk_x][walk_y] = warp
          next_pos.append((walk_x, walk_y))
  for x, y in set(jump_pos):
    if x < 0 or x >= H or y < 0 or y >= W:
        continue
    elif S[x][y] == '#':
      continue
    elif cnt[x][y] <= warp:
      continue
    else:
      next_pos.append((x, y))
  if next_pos == []:
    break
  else:
    warp += 1
    jump_pos = []
    
# print(cnt)
if cnt[d_h-1][d_w-1] == INF:
  print(-1)
else:
  print(cnt[d_h-1][d_w-1])

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc176/submissions/16164430?lang=ja
import heapq

h, w = map(int, input().split())
sh, sw = map(lambda x: int(x) - 1, input().split())
gh, gw = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]

inf = 10 ** 10
D = [[inf] * w for i in range(h)]

D[sh][sw] = 0
Q = [(0, (sh, sw))]
heapq.heapify(Q)
while Q:
  _, (curr_h, curr_w) = heapq.heappop(Q)
  print(curr_h, curr_w)
  for di in range(-2, 3):
    for dj in range(-2, 3):
      next_h, next_w = curr_h + di, curr_w + dj
      if 0 <= next_h < h and 0 <= next_w < w and S[next_h][next_w] == ".":
        nex = int(abs(di) + abs(dj) != 1)
        if D[next_h][next_w] > D[curr_h][curr_w] + nex:
          D[next_h][next_w] = D[curr_h][curr_w] + nex
          heapq.heappush(Q, (D[next_h][next_w], (next_h, next_w)))
if D[gh][gw] >= inf:
  print(-1)
else:
  print(D[gh][gw])

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #bfs
    for dy, dx in move1:
        childy = py + dy
        childx = px + dx
        if 0 <= childx < w and 0 <= childy < h:
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            warpx = px + dx
            warpy = py + dy
            if 0<=warpx<w and 0<=warpy<h:
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])

ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque
from copy import deepcopy
def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    
    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'

    next_nodes = deque()
    next_nodes.append((ch, cw))
    next2_nodes = deque()
    #cnt = 0
    while next_nodes:
        while next_nodes:
            nextn = next_nodes.popleft()
            nextny = nextn[0]
            nextnx = nextn[1]
            curg = maze[nextny][nextnx]
            flag = False
            for j1 in range(4):
                ny = nextny + movey[j1]
                nx = nextnx + movex[j1]
                if maze[ny][nx] == '.':
                    maze[ny][nx] = curg
                    next2_nodes.appendleft((ny, nx))
                elif maze[ny][nx] == '#':
                    flag = True
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.appendleft((ny, nx))
            if flag:
                for j1 in range(20):
                    ny = nextny + warpy[j1]
                    nx = nextnx + warpx[j1]
                    nextg = maze[ny][nx]
                    if nextg == '.':
                        next2_nodes.append((ny, nx))
                        maze[ny][nx] = curg + 1
                    elif nextg == '#':
                        pass
                    #elif nextg > curg + 1:
                    #    maze[ny][nx] = curg + 1
                    #    next2_nodes.append((ny, nx))
        next_nodes = deque(set(next2_nodes))
        next2_nodes = deque()
    g = maze[dh][dw]
    if g == '.':
        print(-1)
    else:
        print(g)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

H, W = MI()
Ch, Cw = MI()
Dh, Dw = MI()
S_ = []
for i in range(H):
    s = S()
    S_.append(s)

# i行目j列目のマスに(i - 1) * W + j　- 1の数字を割り振る
star = (Ch - 1) * W + Cw - 1
goal = (Dh - 1) * W + Dw - 1
g = [[] for _ in range(H * W)]
for i in range(H * W):
    h, w = divmod(i, W)
    if S_[h][w] == '#':
        continue
    else:
        if w != 0 and S_[h][w - 1] == '.':
            g[i].append(i - 1)
        if w != W - 1 and S_[h][w + 1] == '.':
            g[i].append(i + 1)
        if h != 0 and S_[h - 1][w] == '.':
            g[i].append(i - W)
        if h != (H - 1) and S_[h + 1][w] == '.':
            g[i].append(i + W)


from collections import deque

def bfs(u, n):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    dif_list = [u]
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = 0
                queue.append(i)
                dif_list.append(i)
    return dif_list

def warp(A, B):
    dif_A = []
    dif_A_total = [0] * (H * W)
    bfs_list = []
    for a in A:
        h, w = divmod(a, W)
        left = min(w, 2)
        right = min(W - 1 - w, 2)

        for i in range(-left, right + 1):
            for j in range(-2, 3):
                a_ = a + i + (j * W)
                h_, w_ = divmod(a_, W)
                if 0 <= a_ <= H * W - 1 and B[a_] == 0 and dif_A_total[a_] == 0 and S_[h_][w_] == '.':
                    dif_A_total[a_] = 1
                    B[a_] = 1
                    dif_A.append(a_)
    for b in dif_A:
        if b not in bfs_list:
            for c in bfs(b, H * W):
                if c not in dif_A:
                    bfs_list.append(c)
                    dif_A.append(c)
    return dif_A

dif_0 = bfs(star, H * W)
dif_total = [0] * (H * W)
for _ in dif_0:
    dif_total[_] = 1
ans = 0
if dif_total[goal] != 0:
    print(0)
    exit()
else:
    while dif_0 != []:
        dif_0 = warp(dif_0, dif_total)
        ans += 1
        if dif_total[goal] != 0:
            print(ans)
            exit()
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque
from copy import deepcopy
def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    warpy1 = (-2, -2, -1, -1, 0, 1, 1, 2, 2)
    warpx1 = ( 1,  2,  1,  2, 2, 1, 2, 1, 2)
    warpy2 = (-2, -2, -2, -2, -2, -1, -1, -1, -1)
    warpx2 = (-2, -1,  0,  1,  2, -2, -1,  1, 2)
    warpy3 = (-2, -2, -1, -1,  0,  1,  1,  2, 2)
    warpx3 = (-2, -1, -2, -1, -2, -2, -1, -2, -1)
    warpy4 = ( 1,  2,  1,  2,  2,  1,  1, 1, 2)
    warpx4 = (-2, -2, -1, -1,  0,  1,  2, 2, 2)
    warps = []
    warps.append((warpy1, warpx1))
    warps.append((warpy2, warpx2))
    warps.append((warpy3, warpx3))
    warps.append((warpy4, warpx4))
    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'

    next_nodes = deque()
    next_nodes.append((ch, cw))
    next2_nodes = deque()
    #cnt = 0
    while next_nodes:
        while next_nodes:
            nextn = next_nodes.popleft()
            nextny = nextn[0]
            nextnx = nextn[1]
            curg = maze[nextny][nextnx]
            flag = False
            for j1 in range(4):
                ny = nextny + movey[j1]
                nx = nextnx + movex[j1]
                if maze[ny][nx] == '.':
                    maze[ny][nx] = curg
                    next2_nodes.append((ny, nx))
                elif maze[ny][nx] == '#':
                    warpnext_y = warps[j1][0]
                    warpnext_x = warps[j1][1]
                    for k1 in range(9):
                        ny = nextny + warpnext_y[k1]
                        nx = nextnx + warpnext_x[k1]
                        nextg = maze[ny][nx]
                        if nextg == '.':
                            next2_nodes.append((ny, nx))
                            maze[ny][nx] = curg + 1
                        elif nextg == '#':
                            pass
                        #elif nextg > curg + 1:
                        #    maze[ny][nx] = curg + 1
                        #    next2_nodes.append((ny, nx))
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.append((ny, nx))

        next_nodes = deepcopy(next2_nodes)
        next2_nodes = deque()
    g = maze[dh][dw]

    if g == '.':
        print(-1)
    else:
        print(g)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque
from copy import deepcopy
def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    warpy1 = (-2, -2, -1, -1, 0, 1, 1, 2, 2)
    warpx1 = ( 1,  2,  1,  2, 2, 1, 2, 1, 2)
    warpy2 = (-2, -2, -2, -2, -2, -1, -1, -1, -1)
    warpx2 = (-2, -1,  0,  1,  2, -2, -1,  1, 2)
    warpy3 = (-2, -2, -1, -1,  0,  1,  1,  2, 2)
    warpx3 = (-2, -1, -2, -1, -2, -2, -1, -2, -1)
    warpy4 = ( 1,  2,  1,  2,  2,  1,  1, 1, 2)
    warpx4 = (-2, -2, -1, -1,  0,  1,  2, 2, 2)
    warps = []
    warps.append((warpy1, warpx1))
    warps.append((warpy2, warpx2))
    warps.append((warpy3, warpx3))
    warps.append((warpy4, warpx4))
    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)

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=[]
for h in range(H):
    s=list(input())
    L.append(s)

def isOK(h,w):
    if 0<=h<H and 0<=w<W:
        if L[h][w]!="#":
            return True
        
    return False


DX=[1,0,-1,0]
DY=[0,1,0,-1]

que=deque([])
count=0
que.append((ch-1,cw-1, 0))
cost=[[-1]*W for _ in range(H)]
cost[ch-1][cw-1]=0
lis=[(ch-1,cw-1)]
while que:
    while que:
        t=que.popleft()
        x,y,now=t
        if x==dh-1 and y==dw-1:
            print(now)
            exit()
        for i in range(4):
            dx,dy=DX[i],DY[i]
            nx=x+dx
            ny=y+dy
            if isOK(nx,ny):
                if cost[nx][ny]==-1:
                    cost[nx][ny]=now
                    que.append((nx,ny,now))
                    lis.append((nx,ny))
    for t in lis:
        x,y=t
        for dx in range(-2,3):
            for dy in range(-2,3):
                if dx==0 and dy==0:
                    continue
                nx=x+dx
                ny=y+dy
                if isOK(nx,ny):
                    if cost[nx][ny]==-1:
                        cost[nx][ny]=count+1
                        que.append((nx,ny,count+1))
    count+=1
    lis=[]

print(cost[dh-1][dw-1])

#print(cost)

Submission status: Wrong Answer

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

    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'

    next_nodes = deque()
    next_nodes.append((ch, cw))
    next2_nodes = deque()
    #cnt = 0
    while next_nodes:
        while next_nodes:
            nextn = next_nodes.popleft()
            nextny = nextn[0]
            nextnx = nextn[1]
            curg = maze[nextny][nextnx]
            flag = False
            for j1 in range(4):
                ny = nextny + movey[j1]
                nx = nextnx + movex[j1]
                if maze[ny][nx] == '.':
                    maze[ny][nx] = curg
                    next2_nodes.append((ny, nx))
                elif maze[ny][nx] == '#':
                    flag = True
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.append((ny, nx))
            if flag:
                for j1 in range(20):
                    ny = nextny + warpy[j1]
                    nx = nextnx + warpx[j1]
                    nextg = maze[ny][nx]
                    if nextg == '.':
                        next2_nodes.append((ny, nx))
                        maze[ny][nx] = curg + 1
                    elif nextg == '#':
                        pass
                    elif nextg > curg + 1:
                        maze[ny][nx] = curg + 1
                        #next2_nodes.append((ny, nx))
        next_nodes = deepcopy(next2_nodes)
        next2_nodes = deque()
    g = maze[dh][dw]
    if g == '.':
        print(-1)
    else:
        print(g)

if __name__ == '__main__':
    main()