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: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    h,w = map(int,ipt().split())
    ch,cw = map(int,ipt().split())
    dh,dw = map(int,ipt().split())
    board = [input()+"##" for i in range(h)]
    board.append("#"*(w+2))
    board.append("#"*(w+2))
    t = [[10**18]*w for i in range(h)]
    q = [(ch-1,cw-1)]
    nt = 0
    t[ch-1][cw-1] = 0

    while q:
        wall = set()
        while q:
            qx,qy = q.pop()
            for dx,dy in dir:
                nx = qx+dx
                ny = qy+dy
                if board[nx][ny] == ".":
                    if t[nx][ny] == 10**18:
                        t[nx][ny] = nt
                        q.append((nx,ny))
                else:
                    wall.add((qx,qy))
        nt += 1
        for wx,wy in wall:
            for xs in range(-2,3):
                nx = wx+xs
                for ys in range(-2,3):
                    ny = wy+ys
                    if board[nx][ny] == "." and t[nx][ny] == 10**18:
                        q.append((nx,ny))
                        t[nx][ny] = nt

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


    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

H,W = map(int,input().split())

sx,sy = map(int,input().split())
gx,gy = map(int,input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1

a = []
for i in range(H):

    tmp = list(input())
    a.append(tmp)

from collections import deque

q = deque([(sx,sy)])
d = [[float("inf")] * W for i in range(H)]
d[sx][sy] = 0

while len(q) > 0:

    nx,ny = q.popleft()
    if a[nx][ny] == "#":
        continue
    elif nx == gx and ny == gy:
        break

    if nx > 0 and d[nx-1][ny] > d[nx][ny] and a[nx-1][ny] != "#":
        d[nx-1][ny] = d[nx][ny]
        q.appendleft((nx-1,ny))

    if nx != H-1 and d[nx+1][ny] > d[nx][ny] and a[nx+1][ny] != "#":
        d[nx+1][ny] = d[nx][ny]
        q.appendleft((nx+1,ny))

    if ny > 0 and d[nx][ny-1] > d[nx][ny] and a[nx][ny-1] != "#":
        d[nx][ny-1] = d[nx][ny]
        q.appendleft((nx,ny-1))

    if ny != W-1 and d[nx][ny+1] > d[nx][ny] and a[nx][ny+1] != "#":
        d[nx][ny+1] = d[nx][ny]
        q.appendleft((nx,ny+1))

    for xx in range(-2,3):
        for yy in range(-2,3):

            nex = nx + xx
            ney = ny + yy
            if 0 <= nex < H and 0 <= ney < W and d[nex][ney] > d[nx][ny] + 1:
                d[nex][ney] = d[nx][ny] + 1
                q.append((nex,ney))

if d[gx][gy] == float("inf"):
    print (-1)
else:
    print (d[gx][gy])

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


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

    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())
    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1
    grid = []
    for _ in range(H):
        grid.append(input().rstrip('\n'))

    que = deque()
    que.append(sh * W + sw)
    seen = [[-1] * W for _ in range(H)]
    seen[sh][sw] = 0
    seen2 = [[0] * W for _ in range(H)]
    d = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    while que:
        hw = que.popleft()
        h, w = divmod(hw, W)
        if seen2[h][w]:
            continue
        seen2[h][w] = 1
        # toho
        for dh, dw in d:
            h_new, w_new = h+dh, w+dw
            if 0 <= h_new < H and 0 <= w_new < W:
                if grid[h_new][w_new] == ".":
                    if seen[h_new][w_new] == -1 or seen[h_new][w_new] > seen[h][w]:
                        que.appendleft(h_new * W + w_new)
                        seen[h_new][w_new] = seen[h][w]
        # warp
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                h_new, w_new = h + dh, w + dw
                if 0 <= h_new < H and 0 <= w_new < W:
                    if grid[h_new][w_new] == ".":
                        if seen[h_new][w_new] == -1:
                            que.append(h_new * W + w_new)
                            seen[h_new][w_new] = seen[h][w] + 1
    print(seen[gh][gw])
    #[print(*seen[h]) for h in range(H)]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sy -= 1
sx -= 1
gy -= 1
gx -= 1
a = [list(input())[: -1] for _ in range(H)]
Q = dq([sy * W + sx])
inf = H * W + 1
dp = [inf] * (H * W)
dp[sy * W + sx] = 0
d = [-1, 0, 1, 0]
while len(Q):
  t = Q.popleft()
  y = t // W
  x = t % W
  for k in range(4):
    u = y + d[k]
    v = x + d[-1 - k]
    if u in range(H) and (v in range(W)):
      if a[u][v] == "#": continue
      if dp[u * W + v] > dp[t]:
        dp[u * W + v] = dp[t]
        Q.appendleft(u * W + v)

  for i in range(5):
    for j in range(5):
      u = y + i - 2
      v = x + j - 2
      if u in range(H) and (v in range(W)):
        if a[u][v] == "#": continue
        if dp[u * W + v] > dp[t] + 1:
          dp[u * W + v] = dp[t] + 1
          Q.append(u * W + v)
if dp[gy * W + gx] != inf: print(dp[gy * W + gx])
else: print(-1)

Submission status: Accepted

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

import heapq
inf = 10 ** 7
d = [[inf]*w for _ in range(h)]
 
def bfs():
    que = [(0, ch, cw)]
    d[ch][cw] = 0
    heapq.heapify(que)
    
    while len(que) > 0:
        dist, qx, qy = heapq.heappop(que)
        if dist > d[qx][qy]:
            continue
        if qx == dh and qy == dw:
            return d[dh][dw]
        for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            px, py = qx+dx, qy+dy
            if 0 <= px < h and 0 <= py < w and s[px][py]=='.' and d[px][py] > d[qx][qy]:
                d[px][py] = d[qx][qy]
                heapq.heappush(que, (d[px][py], px, py))
        
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                px, py = qx+dx, qy+dy
                if 0 <= px < h and 0 <= py < w and s[px][py]=='.' and d[px][py] > d[qx][qy] + 1:
                    d[px][py] = d[qx][qy] + 1
                    heapq.heappush(que, (d[px][py], px, py))
    
    return -1

ans = bfs()
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

INF = 10 ** 9

H, W = map(int, input().split())
si, sj = map(int, input().split())
gi, gj = map(int, input().split())

si += 1
sj += 1
gi += 1
gj += 1

sentinel = [-1] * (W + 4)
MAP = [sentinel, sentinel]
for _ in range(H):
    MAP.append([-1, -1] + [-1 if c == '#' else INF for c in input()] + [-1, -1])
MAP.append(sentinel)
MAP.append(sentinel)

#detected = [[False] * (W+4) for _ in range(H+4)]
#arrived = [[False] * (W+4) for _ in range(H+4)]
MAP[si][sj] = 0
q = deque([(si, sj)])
while q:
    i, j = q.popleft()
    if i == gi and j == gj:
        break
    for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        if MAP[i+di][j+dj] > MAP[i][j]:
            MAP[i+di][j+dj] = MAP[i][j]
            q.appendleft((i+di, j+dj))

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if MAP[i+di][j+dj] > MAP[i][j] + 1:
                MAP[i+di][j+dj] = MAP[i][j] + 1
                q.append((i+di, j+dj))

# print(*MAP, sep = '\n')

ans = MAP[gi][gj]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
INF = 10 ** 10
dxdy = ((0, 1), (0, -1), (1, 0), (-1, 0))
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = ['#' * (w + 2)] + ['#' + input() + '#' for _ in range(h)] + ['#' * (w + 2)]
d = [[INF] * (w + 1) for _ in range(h + 1)]
d[ch][cw] = 0
q = deque([(ch, cw)])
while q:
    y, x = q.pop()
    for dx, dy in dxdy:
        if s[y + dy][x + dx] == '.' and d[y + dy][x + dx] > d[y][x]:
            d[y + dy][x + dx] = d[y][x]
            q.append((y + dy, x + dx))
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == j == 0:
                continue
            elif 1 <= y + i <= h and 1 <= x + j <= w and s[y + i][x + j] == '.' and d[y + i][x + j] > d[y][x] + 1:
                d[y + i][x + j] = d[y][x] + 1
                q.appendleft((y + i, x + j))
ans = d[dh][dw]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input().rstrip() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
dq = deque([(0, Ch, Cw)])
while dq:
    d, i, j = dq.popleft()
    if (i, j) == (Dh, Dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
            dq.appendleft((d, ni, nj))
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.' and not visited[ni][nj]:
                dq.append((d + 1, ni, nj))
print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

h, w = na()
ch, cw = na()
dh, dw = na()

b = []
for i in range(h):
    b.append(ns())

q = deque()
q.append((ch-1, cw-1))
ds = [9999999999] * (h*w)
ds[(ch-1)*w+cw-1] = 0

di = ((1, 0), (0, 1), (-1, 0), (0, -1))
while q:
    r, c = q.popleft()
    for k in di:
        nr, nc = r + k[0], c + k[1]
        if 0 <= nr < h and 0 <= nc < w and b[nr][nc] == "." and ds[nr*w+nc] > ds[r*w+c]:
            ds[nr*w+nc] = ds[r*w+c]
            q.appendleft((nr, nc))
    for nr in range(r-2, r+3):
        for nc in range(c-2, c+3):
            if 0 <= nr < h and 0 <= nc < w and b[nr][nc] == "." and ds[nr * w + nc] > ds[r * w + c] + 1:
                ds[nr * w + nc] = ds[r * w + c] + 1
                q.append((nr, nc))

if ds[(dh-1)*w+dw-1] > 9999999:
    print(-1)
else:
    print(ds[(dh-1)*w+dw-1])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w = LI()
    cy,cx = LI()
    gy,gx = LI()
    s = [input() for _ in range(h)]
    cy -= 1
    cx -= 1
    gy -= 1
    gx -= 1
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    bfs = [[float("inf")]*w for i in range(h)]
    bfs[cy][cx] = 0
    q = deque([(cy,cx)])
    while q:
        y,x = q.popleft()
        b = bfs[y][x]
        if (y,x) == (gy,gx):
            print(b)
            return
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != "#" and b < bfs[ny][nx]:
                bfs[ny][nx] = b
                q.appendleft((ny,nx))
        nb = b+1
        for dy in range(-2,3):
            for dx in range(-2,3):
                ny,nx = y+dy,x+dx
                if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != "#" and nb < bfs[ny][nx]:
                    bfs[ny][nx] = nb
                    q.append((ny,nx))
    print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
from collections import deque

h , w = map(int, input().split())
start_y, start_x = map(int, input().split())
end_y, end_x = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
cost = [[float('inf') for i in range(w)] for j in range(h)]

def bfs():
    que = deque()
    que.append((start_x-1, start_y-1,0))
    que_contents = set()
    while que:
        x, y, c = que.popleft()
        if not ((0 <= y < h) and (0 <= x < w)) :
            continue
        if grid[y][x] == '#':
            continue
        if cost[y][x] <= c:
            continue
        cost[y][x] = c
        for n_x, n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
            que.appendleft((n_x, n_y, c))
        for i in range(-2,3):
            for j in range(-2,3):
                que.append((x+i,y+j,c+1))

bfs()
if cost[end_y-1][end_x] == float('inf'):
    print(-1)
    exit()
print(cost[end_y-1][end_x-1])

Submission status: Runtime Error

Solution code:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
G[sy][sx] = '#'
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    d = D[y][x]
    for dy, dx in product(range(-2, 3), repeat=2):
        if dx+dy==0:
            G[y][x] = '#'
        ny, nx = y+dy, x+dx
        elif any((ny<0, h<=ny, nx<0, w<=nx)):
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1 and D[ny][nx] > d:
            G[ny][nx] = '#'
            D[ny][nx] = d
            Q.append((ny, nx))
        elif D[ny][nx] > d+1:
            D[ny][nx] = d+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Submission status: Runtime Error

Solution code:
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = []
for _ in range(h):
    G.append(list(input()))
D = [[10**6]*w for i in range(h)]
D[sy][sx] = 0
Q = deque()
Q.append((sy, sx))

while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx+dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dx)+abs(dy)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] > D[y][x]+1:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Submission status: Runtime Error

Solution code:
from collections import deque
def main():
  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 = [["#"]*(w+4) for _ in range(2)]+[["#"]*2+list(input())+["#"]*2 for _ in range(h)]+[["#"]*(w+4) for _ in range(2)]
  m1 = ((-1,0),(0,-1),(0,1),(1,0))
  m2 = [(i,j) for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]
  a = deque([(ch,cw)])
  b = deque()
  i = 0
  while a:
    while a:
      ah,aw = a.popleft()
      if s[bh][bw]!=".":
        continue
      b.append((ah,aw))
      s[ah][aw] = i
      for bh,bw in m1:
        bh,bw = ah+bh,aw+bw
        if s[bh][bw]==".":
          a.append((bh,bw))
    while b:
      ah,aw = b.popleft()
      for bh,bw in m2:
        bh,bw = ah+bh,aw+bw
        if s[bh][bw]==".":
          a.append((bh,bw))
    i += 1
  ans = s[dh][dw]
  print(ans if ans != "." else -1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')
C, R = it()
start_r, start_c = it()
start_c, start_r = start_c - 1, start_r - 1
end_r, end_c = it()
end_c, end_r = end_c - 1, end_r - 1
grid = [input().strip() for _ in range(R)]
dist = [[INF] * C for _ in range(R)]
dist[start_r][start_c] = 0
queue = deque()
queue.append((0, start_r, start_c))
while queue:
  d, r, c = queue.popleft()
  if d > dist[r][c]: continue
  for r0, c0 in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
    if 0 <= r0 < R and 0 <= c0 < C and grid[r0][c0] == '.' and dist[r0][c0] > d:
        dist[r0][c0] = d
        queue.append((d, r0, c0))
  for r0 in range(r - 2, r + 3):
    for c0 in range(c - 2, c + 3):
      if 0 <= r0 < R and 0 <= c0 < C and grid[r0][c0] == '.' and dist[r0][c0] > d + 1:
        dist[r0][c0] = d + 1
        queue.append((d + 1, r0, c0))
if dist[end_r][end_c] == INF:
  print(-1)
else:
  print(dist[end_r][end_c])

Submission status: Runtime Error

Solution code:
from collections import deque
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')
C, R = it()
start_c, start_r = it()
start_c, start_r = start_c - 1, start_r - 1
end_c, end_r = it()
end_c, end_r = end_c - 1, end_r - 1
grid = [input().strip() for _ in range(R)]
dist = [[INF] * C for _ in range(R)]
queue = deque()
queue.append((0, start_r, start_c))
dist[start_r][start_c] = 0
while queue:
  d, r, c = queue.popleft()
  if d > dist[r][c]: continue
  for r0 in range(r - 2, r + 3):
    for c0 in range(c - 2, c + 3):
      if 0 <= r0 < R and 0 <= c0 < C and grid[r0][c0] == '.' and dist[r0][c0] > d + 1:
        dist[r0][c0] = d + 1
        queue.append((d + 1, r0, c0))
if dist[end_r][end_c] == INF:
  print(-1)
else:
  print(dist[end_r][end_c])

Submission status: Runtime Error

Solution code:
from collections import deque
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')
C, R = it()
start_c, start_r = it()
end_c, end_r = it()
grid = [input().strip() for _ in range(R)]
dist = [[INF] * C for _ in range(R)]
queue = deque()
queue.append((0, start_c, start_r))
dist[start_r][start_c] = 0
while queue:
  d, r, c = queue.popleft()
  if d > dist[r][c]: continue
  for r0 in range(r - 2, r + 3):
    for c0 in range(c - 2, c + 3):
      if 0 <= r0 < R and 0 <= c0 < C and grid[r0][c0] == '.' and dist[r0][c0] > d + 1:
        dist[r0][c0] = d + 1
        queue.append((d + 1, r0, c0))
if dist[end_r][end_c] == INF:
  print(-1)
else:
  print(dist[end_r][end_c])

Submission status: Runtime Error

Solution code:
from collections import deque

H,W = map(int,input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
# 지도
board = [input() for _ in range(H)]
# 방문 체크
visited = [[False] * W for _ in range(H)]
# bfs를 위한 큐 
dq = deque([[0,C[0],C[1]]])
visited[H][W] = True

while dq:
  cnt, h, w = dq.popleft()
  # 도착점에 도착하면 종료
  if [h,w] == D:
    print(cnt)
    exit()
  if visited[h][w]:
    continue
  # 상,하,좌,우 1칸씩 이동
  for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
    new_h = h + move_h
    new_w = w + move_w
    # 걸어서 갈 수 있는 경우 앞에서부터 큐에 넣음
    if 0 <= new_h <= H-1 and 0<= new_w <= W-1 and board[new_h][new_w] == '.' and (not visited[new_h][new_w]):
      visited[new_h][new_w] = True
      dq.appendleft([cnt,new_h,new_w])
  # 인접한 5x5 탐색
  for move_h in range(-2,3):
    for move_w in range(-2,3):
      if [move_h, move_w] == [0,0]:
        continue
      new_h = h + move_h
      new_w = w + move_w 
      # 마법을 사용한 경우 뒤에서부터 큐에 넣음
      if 0 <= new_h <= H-1 and 0<= new_w <= W-1 and board[new_h][new_w] == '.' and (not visited[new_h][new_w]):
        visited[new_h][new_w] = True
        dq.append([cnt+1,new_h,new_w])
print(-1)

Submission status: Runtime Error

Solution code:
import copy
import sys
from collections import deque

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw= map(int,input().split())
board = [[0 for col in range(W)] for row in range(H)]
for i in range(0,H):
  s = input()
  for j in range(0,len(s)):
    board[i][j] = s[j]

visited = [[False for col in range(W)] for row in range(H)]
# bfs를 위한 큐 
dq = deque([[0,Ch,Cw]])

while dq:
  cnt, h, w = dq.popleft()
  print(cnt,h,w)
  if [h,w] == [Dh-1,Dw-1]:
    print(cnt)
    exit()
  if visited[h][w]:
    continue
  visited[h][w] = True
  for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
    new_h = h + move_h
    new_w = w + move_w
    if 0 <= new_h <= H-1 and 0<= new_w <= W-1 and board[new_h][new_w] == '.' and (not visited[new_h][new_w]):
      dq.appendleft([cnt,new_h,new_w])
  for move_h in range(-2,3):
    for move_w in range(-2,3):
      if [move_h, move_w] == [0,0]:
        continue
      new_h = h + move_h
      new_w = w + move_w 
      if 0 <= new_h <= H-1 and 0<= new_w <= W-1 and board[new_h][new_w] == '.' and (not visited[new_h][new_w]):
        dq.append([cnt+1,new_h,new_w])
print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw= map(int,input().split())
board = [[0 for col in range(W)] for row in range(H)]
for i in range(0,H):
  s = input()
  for j in range(0,len(s)):
    board[i][j] = s[j]

visited = [[False for col in range(W)] for row in range(H)]
# bfs를 위한 큐 
dq = deque([[0,Ch,Cw]])

while dq:
  cnt, h, w = dq.popleft()
  # print(cnt,h,w)
  if [h,w] == [Dh-1,Dw-1]:
    print(cnt)
    exit()
  if visited[h][w]:
    continue
  visited[h][w] = True
  for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
    new_h = h + move_h
    new_w = w + move_w
    if 0 <= new_h <= H-1 and 0<= new_w <= W-1 and board[new_h][new_w] == '.' and (not visited[new_h][new_w]):
      dq.appendleft([cnt,new_h,new_w])
  for move_h in range(-2,3):
    for move_w in range(-2,3):
      if [move_h, move_w] == [0,0]:
        continue
      new_h = h + move_h
      new_w = w + move_w 
      if 0 <= new_h <= H-1 and 0<= new_w <= W-1 and board[new_h][new_w] == '.' and (not visited[new_h][new_w]):
        dq.append([cnt+1,new_h,new_w])
print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw= map(int,input().split())
board = [[0 for col in range(W)] for row in range(H)]
for i in range(0,H):
  s = input()
  for j in range(0,len(s)):
    board[i][j] = s[j]

visited = [[False for col in range(W)] for row in range(H)]
# bfs를 위한 큐 
dq = deque([[0,Ch,Cw]])

while dq:
  cnt, h, w = dq.popleft()
  if h == Dh and w == Dw:
    print(cnt)
    exit()
  if visited[h][w]:
    continue
  visited[h][w] = True
  for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
    new_h = h + move_h
    new_w = w + move_w
    if 0 <= new_h <= H-1 and 0<= new_w <= W-1 and board[new_h][new_w] == '.' and (not visited[new_h][new_w]):
      dq.appendleft([cnt,new_h,new_w])
  for move_h in range(-2,3):
    for move_w in range(-2,3):
      if [move_h, move_w] == [0,0]:
        continue
      new_h = h + move_h
      new_w = w + move_w 
      if 0 <= new_h <= H-1 and 0<= new_w <= W-1 and board[new_h][new_w] == '.' and (not visited[new_i][new_j]):
        dq.append([cnt+1,new_h,new_w])
print(-1)

Submission status: Runtime Error

Solution code:
#dp[][]は何回のジャンプが必要かを示す

from collections import deque
h,w = list(map(int,input().split()))
sy,sx = list(map(int,input().split()))
gy,gx = list(map(int,input().split()))


sy -= 1
sx -= 1
gy -= 1
gx -= 1


grid = [input() for _ in range(h)]
dp = [[-1 for _ in range(w)] for _ in range(h)]

dp[sy][sx] = 0

#print(dp)
pos_que = deque()
pos_que.append((sx,sy))
#print(pos_que)
ps = deque()
ps.append((sx,sy))

def area_move(pos_que):
    while pos_que:
        px,py = pos_que.popleft()
        d = dp[py][px]
        ps.append((px,py))
        for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
            px_new = px + dx
            py_new = py + dy
            if py_new < 0 or h <= py_new or px_new < 0 or w <= px_new or dp[py_new][px_new] != -1 or grid[py_new][px_new] == '#':
                continue
            else:
                dp[py_new][px_new] = d
                pos_que.append((px_new,py_new))
                ps.append((px_new,py_new))
    return False




def magic_jump(n,ps):
    while ps:
        if True:
            i,j = ps.popleft()
            #print(i,j)
            if dp[j][i] == n:
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i+dx
                    new_h = j + dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_wor grid[new_h][new_w] == '#' or dp[new_h][new_w] >-1:
                        continue
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i-dx
                    new_h = j-dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w or grid[new_h][new_w] == '#' or dp[new_h][new_w] >-1:
                        continue
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                        
                        
                
def main(dp_old):
    for i in range(10000000):
        area_move(pos_que)
        if dp[gy][gx] != -1:
            return dp[gy][gx]
        magic_jump(i,ps)
        if not pos_que:
            return -1
    return -1

print(main([]))

Submission status: Runtime Error

Solution code:
#dp[][]は何回のジャンプが必要かを示す

from collections import deque
h,w = list(map(int,input().split()))
sy,sx = list(map(int,input().split()))
gy,gx = list(map(int,input().split()))


sy -= 1
sx -= 1
gy -= 1
gx -= 1


grid = [input() for _ in range(h)]
dp = [[-1 for _ in range(w)] for _ in range(h)]

dp[sy][sx] = 0

#print(dp)
pos_que = deque()
pos_que.append((sx,sy))
#print(pos_que)
ps = deque()
ps.append((sx,sy))

def area_move(pos_que):
    while pos_que:
        px,py = pos_que.popleft()
        d = dp[py][px]
        ps.append((px,py))
        for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
            px_new = px + dx
            py_new = py + dy
            if py_new < 0 or h <= py_new or px_new < 0 or w <= px_new or dp[py_new][px_new] != -1 or grid[py_new][px_new] == '#':
                continue
            else
                dp[py_new][px_new] = d
                pos_que.append((px_new,py_new))
                ps.append((px_new,py_new))
    return False




def magic_jump(n,ps):
    while ps:
        if True:
            i,j = ps.popleft()
            #print(i,j)
            if dp[j][i] == n:
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i+dx
                    new_h = j + dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_wor grid[new_h][new_w] == '#' or dp[new_h][new_w] >-1:
                        continue
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i-dx
                    new_h = j-dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w or grid[new_h][new_w] == '#' or dp[new_h][new_w] >-1:
                        continue
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                        
                        
                
def main(dp_old):
    for i in range(10000000):
        area_move(pos_que)
        if dp[gy][gx] != -1:
            return dp[gy][gx]
        magic_jump(i,ps)
        if not pos_que:
            return -1
    return -1

print(main([]))