Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**9)

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())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch-1, cw-1)])
S = [[float("inf")]*w for _ in range(h)]
S[ch][cw] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = ((1,0),(0,1),(-1,0),(0,-1))
    ans = S[y][x]

    if (y, x) == (dh, dw):
            S[y][x] = ans
            break

    for j, i in dx_dy:
        if 0 <= x+i < w and 0 <= y+j < h:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = ans
                queue.appendleft((y+j, x+i))

    ans += 1
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > ans and G[y+j][x+i] == ".":
                        S[y+j][x+i] = ans
                        queue.append((y+j, x+i))


if S[dh][dw] == float("inf"):
    print(-1)
else:
    print(S[dh][dw])

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    warp_up = [
        (-2, -2),
        (-1, -2),
        (0, -2),
        (1, -2),
        (2, -2),
        (-2, -1),
        (-1, -1),
        (1, -1),
        (2, -1),
    ]
    warp_do = [
        (2, 2),
        (1, 2),
        (0, 2),
        (-1, 2),
        (-2, 2),
        (2, 1),
        (1, 1),
        (-1, 1),
        (-2, 1),
    ]
    warp_ri = [
        (2, -2),
        (2, -1),
        (2, 0),
        (2, 1),
        (2, 2),
        (1, -2),
        (1, -1),
        (1, 1),
        (1, 2),
    ]
    warp_le = [
        (-2, 2),
        (-2, 1),
        (-2, 0),
        (-2, -1),
        (-2, -2),
        (-1, 2),
        (-1, 1),
        (-1, -1),
        (-1, -2),
    ]

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(30000):
        for _ in range(40000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_xy = c[y][x]
                        if c_xy == "#":
                            next = [next_x, next_y]
                            if next == [1, 0]:
                                warp = warp_ri.copy()
                            elif next == [0, 1]:
                                warp = warp_do.copy()
                            elif next == [-1, 0]:
                                warp = warp_le.copy()
                            elif next == [0, -1]:
                                warp = warp_up.copy()
                            for next_x, next_y in warp:
                                x, y = now_x + next_x, now_y + next_y
                                if 0 <= x < w and 0 <= y < h:
                                    if c[y][x] not in "#=!":
                                        c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                        d2.append([x, y])
                        elif c_xy != "=":
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
flag = True
ans = 0
s = set()

while True:
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in [(1,0),(-1,0),(0,1),(0,-1),(0,0)]:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        temp = (Th + i, Tw + i)
        if (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          # print(_p)
          if not(i == 0 and j == 0):
            flag = True
  if (Dh,Dw) in d:
    print(ans)
    exit()
  else:
    s |= set(d)
    temps = set(d)
    d = deque()
    for Th,Tw in temps:
      for i in [-2,-1,0,1,2]:
        for j in [-2,-1,0,1,2]:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          temp = (Th + i, Tw + i)
          if (not (_p) in s) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 1

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    warp_up = [
        (-2, -2),
        (-1, -2),
        (0, -2),
        (1, -2),
        (2, -2),
        (-2, -1),
        (-1, -1),
        (1, -1),
        (2, -1),
    ]
    warp_do = [
        (2, 2),
        (1, 2),
        (0, 2),
        (-1, 2),
        (-2, 2),
        (2, 1),
        (1, 1),
        (-1, 1),
        (-2, 1),
    ]
    warp_ri = [
        (2, -2),
        (2, -1),
        (2, 0),
        (2, 1),
        (2, 2),
        (1, -2),
        (1, -1),
        (1, 1),
        (1, 2),
    ]
    warp_le = [
        (-2, 2),
        (-2, 1),
        (-2, 0),
        (-2, -1),
        (-2, -2),
        (-1, 2),
        (-1, 1),
        (-1, -1),
        (-1, -2),
    ]

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(30000):
        for _ in range(30000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_xy = c[y][x]
                        if c_xy == "#":
                            next = [next_x, next_y]
                            if next == [1, 0]:
                                warp = warp_ri.copy()
                            elif next == [0, 1]:
                                warp = warp_do.copy()
                            elif next == [-1, 0]:
                                warp = warp_le.copy()
                            elif next == [0, -1]:
                                warp = warp_up.copy()
                            for next_x, next_y in warp:
                                x, y = now_x + next_x, now_y + next_y
                                if 0 <= x < w and 0 <= y < h:
                                    if c[y][x] not in "#=!":
                                        c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                        d2.append([x, y])
                        elif c_xy != "=":
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    warp_up = [
        (-2, -2),
        (-1, -2),
        (0, -2),
        (1, -2),
        (2, -2),
        (-2, -1),
        (-1, -1),
        (1, -1),
        (2, -1),
    ]
    warp_do = [
        (2, 2),
        (1, 2),
        (0, 2),
        (-1, 2),
        (-2, 2),
        (2, 1),
        (1, 1),
        (-1, 1),
        (-2, 1),
    ]
    warp_ri = [
        (2, -2),
        (2, -1),
        (2, 0),
        (2, 1),
        (2, 2),
        (1, -2),
        (1, -1),
        (1, 1),
        (1, 2),
    ]
    warp_le = [
        (-2, 2),
        (-2, 1),
        (-2, 0),
        (-2, -1),
        (-2, -2),
        (-1, 2),
        (-1, 1),
        (-1, -1),
        (-1, -2),
    ]

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(10000):
        for _ in range(10000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_xy = c[y][x]
                        if c_xy == "#":
                            next = [next_x, next_y]
                            if next == [1, 0]:
                                warp = warp_ri.copy()
                            elif next == [0, 1]:
                                warp = warp_do.copy()
                            elif next == [-1, 0]:
                                warp = warp_le.copy()
                            elif next == [0, -1]:
                                warp = warp_up.copy()
                            for next_x, next_y in warp:
                                x, y = now_x + next_x, now_y + next_y
                                if 0 <= x < w and 0 <= y < h:
                                    if c[y][x] not in "#=!":
                                        c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                        d2.append([x, y])
                        elif c_xy != "=":
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
flag = True
ans = 0
s = set()

while True:
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in [(1,0),(-1,0),(0,1),(0,-1),(0,0)]:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        temp = (Th + i, Tw + i)
        if (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          # print(_p)
          if not(i == 0 and j == 0):
            flag = True
  if (Dh,Dw) in d:
    print(ans)
    exit()
  else:
    s |= set(d)
    d = deque()
    for Th,Tw in s:
      for i in [-2,-1,0,1,2]:
        for j in [-2,-1,0,1,2]:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          temp = (Th + i, Tw + i)
          if (not (_p) in s) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 1

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**9)

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

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch-1, cw-1)])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0


while queue:
    y, x = queue.popleft()
    dx_dy = [(1,0),(0,1),(-1,0),(0,-1)]
    ans = S[y][x]
    for j, i in dx_dy:
        if 0 <= x+i < w and 0 <= y+j < h:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = ans
                queue.appendleft((y+j, x+i))

    ans += 1
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > ans and G[y+j][x+i] == ".":
                        S[y+j][x+i] = ans
                        queue.append((y+j, x+i))


if S[dh-1][dw-1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

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
rows,cols = h,w

OK = "."
NG = "#"

ss = np.array([[c=="#" for c in input()] for _ in range(h)])

def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    # dx = [0,1,0,-1]
    # dy = [1,0,-1,0]
#     dx = []
#     dy = []
#     vvs = []
#     for i in range(-2,3):
#         for j in range(-2,3):
#             if not (i==j==0):
#                 dx.append(i)
#                 dy.append(j)
#                 if abs(i)+abs(j)>1:
#                     vvs.append(1)
#                 else:
#                     vvs.append(0)
    while q:
#         print(seen)
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        # print(pnum,divmod(pu,w))
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
#         for xx,yy,vv in zip(dx,dy,vvs):
    #         x = ux+xx
    #         y = uy+yy
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
from heapq import *

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(wall, Sx, Sy, Tx, Ty):
    INF = 1 << 30
    H, W = wall.shape
    S = Sx * W + Sy
    T = Tx * W + Ty
    dist = np.full(H * W, INF, np.int64)
    q = [(0,S)]
    while q:
        dv, v = heappop(q)
        if dv > dist[v]:
            continue
        vx, vy = divmod(v, W)
        # そのままあるく
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            wx, wy = vx + dx, vy + dy
            if not (0 <= wx < H):
                continue
            if not (0 <= wy < W):
                continue
            if wall[wx, wy]:
                continue
            w = wx * W + wy
            if dist[w] <= dv:
                continue
            dist[w] = dv
            heappush(q, (dv, w))
        # ワープする
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                wx, wy = vx + dx, vy + dy
                if not (0 <= wx < H):
                    continue
                if not (0 <= wy < W):
                    continue
                if wall[wx, wy]:
                    continue
                w = wx * W + wy
                if dist[w] <= dv + 1:
                    continue
                dist[w] = dv + 1
                heappush(q, (dv+1, w))
    ans = dist[T]
    if ans == INF:
        ans = -1
    return ans

H, W = map(int, readline().split())
Sx, Sy = map(lambda x: int(x) - 1, readline().split())
Tx, Ty = map(lambda x: int(x) - 1, readline().split())
wall = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'#'

# print(main(wall, Sx, Sy, Tx, Ty))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

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
rows,cols = h,w

OK = "."
NG = "#"

ss = np.array([[c=="#" for c in input()] for _ in range(h)])
@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    # dx = [0,1,0,-1]
    # dy = [1,0,-1,0]
#     dx = []
#     dy = []
#     vvs = []
#     for i in range(-2,3):
#         for j in range(-2,3):
#             if not (i==j==0):
#                 dx.append(i)
#                 dy.append(j)
#                 if abs(i)+abs(j)>1:
#                     vvs.append(1)
#                 else:
#                     vvs.append(0)
    while q:
#         print(seen)
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        # print(pnum,divmod(pu,w))
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
#         for xx,yy,vv in zip(dx,dy,vvs):
    #         x = ux+xx
    #         y = uy+yy
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val

Submission status: Wrong Answer

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

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
q=collections.deque()
q.append((sy,sx,0))
count=0
while len(q)!=0:
  y,x,score=q.popleft()
  scores[y][x]=score
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>score:
      q.append((y+dy,x+dx,score))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>score+1:
        q.append((y+dy,x+dx,score+1))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy))
visited = {}
visited[(cx, cy)] = 0
ans = float("inf")
while q:
    x, y = q.popleft()
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if (nx, ny) not in visited:
                visited[(nx, ny)] = visited[(x, y)]
                if nx == gx and ny == gy:
                    continue
                q.appendleft((nx, ny))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                # print("warp append")
                if (nx, ny) not in visited:
                    visited[(nx, ny)] = visited[(x, y)] + 1
                    if nx == gx and ny == gy:
                        continue
                    q.append((nx, ny))
# print(visited)
if (gx, gy) in visited:
    print(visited[(gx, gy)])
else:
    print(-1)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [input() for _ in range(h)]

dx, dy = [1, 0, -1, 0, 1, -1, -1, 1], [0, 1, 0, -1, 1, 1, -1, -1]
que = deque([(cw-1, ch-1)])
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
while que:
    x, y = que.popleft()
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if i <= 3 and s[ny][nx] == '.' and d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.appendleft((nx, ny))
            if s[ny][nx] == '#' and s[y][x] == '.' and d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append((nx, ny))

if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

def inc(y, x):
	return 0 <= y < H and 0 <= x < W

H, W = map(int, input().split())
Sy, Sx = map(int, input().split())
Gy, Gx = map(int, input().split())
"""
a = [[] for i in range(h)]
for i in range(h):
    a[i] = input()
"""
a = [input() for i in range(H)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

#同じ大きさの行列を作って最短路をメモする発想がなかった
visit = [[1e8 for i in range(W)] for j in range(H)]
visit[Sy-1][Sx-1]=0 #sy-1, sx-1に注意
deq = deque([(Sy-1, Sx-1)])

while deq:
    h, w = deq.pop()
    for dh, dw in zip(DH, DW):
        x = w+dw; y=h+dh
        if inc(y, x)==False or a[y][x]=='#':
            continue
        if visit[y][x] > visit[h][w]:
            print('wow___h,w:', h,w)
            visit[y][x] = visit[h][w]
            deq.append((y,x))
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if inc(h+dh, w+dw)==False or a[h+dh][w+dw]=='#':
                continue
            if visit[h+dh][w+dw] > visit[h][w]+1: 
                visit[h+dh][w+dw] = visit[h][w]+1
                deq.appendleft((h+dh, w+dw))
if visit[Gy-1][Gx-1] == 1e8:
    print(-1)
else:
    print(visit[Gy-1][Gx-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())

grid = []
for i in range(H):
    grid.append(input().rstrip())

d = deque()
d.append((Ch-1, Cw-1, 0))

memo = [[False] * W for _ in range(H)]
memo[Ch-1][Cw-1] = True

searched = [[False] * W for _ in range(H)]

ans = -1

while d:
    h, w, c = d.popleft()

    if searched[h][w]:
        continue

    searched[h][w] = True

    if h == Dh-1 and w == Dw-1:
        ans = c
        break

    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if 0 <= h+i < H and 0 <= w+j < W:
            if grid[h+i][w+j] == '.':
                if not memo[h+i][w+j] and not searched[h+i][w+j]:
                    memo[h+i][w+j] = True
                    d.appendleft((h+i, w+j, c))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= h+i < H and 0 <= w+j < W:
                if grid[h+i][w+j] == '.':
                    if not memo[h+i][w+j] and not searched[h+i][w+j]:
                        memo[h+i][w+j] = True
                        d.append((h+i, w+j, c+1))

print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [input() for _ in range(h)]

dx, dy = [1, 0, -1, 0, 1, -1, -1, 1], [0, 1, 0, -1, 1, 1, -1, -1]
que = deque([(cw-1, ch-1)])
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
while que:
    x, y = que.popleft()
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if i <= 3 and s[ny][nx] == '.' and d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.append((nx, ny))
            if s[ny][nx] == '#' and s[y][x] == '.' and d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append((nx, ny))
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
ch, cw = [int(i)-1 for i in input().split()]
dh, dw = [int(i)-1 for i in input().split()]
S = [list(input()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]

move = []
for i in range(5):
    for j in range(5):
        if i == 3 and j == 3:
            continue
        move.append((i-2, j-2))
q = deque()
q.append((0, ch, cw))
while q:
    c, h, w = q.popleft()
    if dist[h][w] >= 0:
        continue
    dist[h][w] = c
    for hh, ww in move:
        if 0 <= h+hh < H and 0 <= w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] < 0:
            if (hh, ww) in ((0,1), (1,0), (-1,0), (0,-1)):
                q.appendleft((c, h+hh, w+ww)) # 徒歩は前に追加
            else:
                q.append((c+1, h+hh, w+ww)) # ワープは後ろに追加

print(dist[dh][dw])

Submission status: Wrong Answer

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

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
G = []
for i in range(H):
    G += [[[0,1][x=='#']for x in input()]]

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]


dy2 = []
dx2 = []
for y in range(-2,3):
    for x in range(-2,3):
        if abs(y)+abs(x) > 1:
            dy2 += [y]
            dx2 += [x]
dl = len(dx2)

q = [(CH-1, CW-1)]
a = [(CH-1, CW-1)]
f = True
c = 0
ans = -1
while f:
    f = False
    while q:
        for y, x in q:
            t = []
            G[y][x] = 2
            for d in range(4):
                px = x + dx[d]
                py = y + dy[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0:
                    G[py][px] = 2
                    t += [(py, px)]
                    a += [(py, px)]
        q = t
    b = []
    for y, x in a:
        for d in range(dl):
            px = x + dx2[d]
            py = y + dy2[d]
            if 0<=px<W and 0<=py<H and G[py][px] == 0:
                b += [(py, px)]
                q += [(py, px)]
    
    if G[DH-1][DW-1] == 2:
        ans = c
        break
    c += 1
    a = []
    if b : f = True
    
print(ans)

Submission status: Wrong Answer

Solution code:
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 = [list(input()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]

move = []
for i in range(5):
    for j in range(5):
        if i == 3 and j == 3:
            continue
        move.append((i-2, j-2))
q = deque()
q.append((0, ch, cw))
while q:
    c, h, w = q.popleft()
    if dist[h][w] >= 0:
        continue
    dist[h][w] = c
    for hh, ww in move:
        if 0 <= h+hh < H and 0 <= w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] < 0:
            if (hh, ww) in ((0,1), (1,0), (-1,0), (0,-1)):
                q.appendleft((c, h+hh, w+ww)) # 徒歩は前に追加
            else:
                q.append((c+1, h+hh, w+ww)) # ワープは後ろに追加

print(dist[dh][dw])