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 itertools import product
from collections import deque
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x, space=1):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
        self.space = space
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join(''.join(f'{{: >{self.space}}}'.format(x) for x in row) for row in self.grid) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def bfs_01(grid, root):
    dequeue = deque([root])
    x, y = root
    dist = Grid(grid.grid, function=lambda x:-9 if x=='#' else -1, space=3)
    dist[y, x] = 0
    while dequeue:
        x, y = dequeue.pop()
        if grid[y, x] == '!':
            continue
        elif grid[y, x] == 'g':
            return dist[y, x]
        grid[y, x] = '!'
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'g.?':
                if grid[ny, nx] == 'g':
                    return dist[y, x]
                dist[ny, nx] = dist[y, x]
                grid[ny, nx] = '!'
                dequeue.append((nx, ny))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'g.':
                dist[ny, nx] = dist[y, x] + 1
                grid[y, x] = '?'
                dequeue.appendleft((nx, ny))
    return -1

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
grid = Grid([input() for s in range(h)], space=3)
grid[sy, sx] = 's'
grid[gy, gx] = 'g'

print(bfs_01(grid, (sx, sy)))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import collections

input = stdin.readline

Y, X = map(int, input().split())
sy, sx = map(int, input().split())
sy -= 1
sx -= 1
ey, ex = map(int, input().split())
ey -= 1
ex -= 1
grid = [[c for c in inp] for inp in stdin.read().splitlines()]
dis = [[1000] * X for _ in range(Y)]

Q = collections.deque()
Q.append((sy, sx,))
dis[sy][sx] = 0
while Q:
    cy, cx = Q.popleft()
    for ny, nx in [(cy + 1, cx), (cy - 1, cx), (cy, cx + 1), (cy, cx - 1)]:
        if 0 <= ny < Y and 0 <= nx < X and grid[ny][nx] == '.' and dis[ny][nx] > dis[cy][cx]:
            Q.appendleft((ny,nx))
            dis[ny][nx] = dis[cy][cx]
    for dy in range(-2,3):
        for dx in range(-2,3):
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < Y and 0 <= nx < X and grid[ny][nx] == '.' and dis[ny][nx] > dis[cy][cx] + 1:
                Q.append((ny,nx))
                dis[ny][nx] = dis[cy][cx] + 1

print(dis[ey][ex] if dis[ey][ex] != 1000 else -1)

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 = [["#"]*(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()
def check(arg):
  y,x = arg
  if y<0 or x<0 or h<=y or w<=x:
    return False
  elif s[y][x] == ".":
    return True
  else:
    return False
  
for i in range(10**4):
  while a:
    ah,aw = a.popleft()
    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))
  if not a:
    break
ans = s[dh][dw]
print(ans if ans != "." else -1)

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 = [["#"]*(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 = set([(ch,cw)])
b = set()
def check(arg):
  y,x = arg
  if y<0 or x<0 or h<=y or w<=x:
    return False
  elif s[y][x] == ".":
    return True
  else:
    return False
  
for i in range(10**4):
  while a:
    ah,aw = a.pop()
    b.add((ah,aw))
    s[ah][aw] = i
    for bh,bw in m1:
      bh,bw = ah+bh,aw+bw
      if s[bh][bw]==".":
        a.add((bh,bw))
  while b:
    ah,aw = b.pop()
    for bh,bw in m2:
      bh,bw = ah+bh,aw+bw
      if s[bh][bw]==".":
        a.add((bh,bw))
  if not a:
    break
ans = s[dh][dw]
print(ans if ans != "." else -1)

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

a = set([(ch,cw)])
b = set()

def check(arg):
  y,x = arg
  if y<0 or x<0 or h<=y or w<=x:
    return False
  if s[y][x] == ".":
    return True
  return False
  
for i in range(10**4):
  while(len(a)>0):
    ah,aw = a.pop()
    s[ah][aw] = i
    for bh,bw in((-1,0),(0,-1),(0,1),(1,0)):
      e = (ah+bh,aw+bw)
      if check(e):
        if e in b:
          b.remove(e)
        a.add(e)
    for bh,bw 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)):
      e = (ah+bh,aw+bw)
      if check(e):
        if e in a:
          continue
        else:
          b.add(e)
  if len(b) == 0:
    break
  a = set(b)
  b = set()
ans = s[dh][dw]
print(ans if ans != "." else -1)

Submission status: Wrong Answer

Solution code:
from _collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    s[i+1]=x
s[0]=s[-1]=["#"]*(w+2)


dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy]])
data2=deque([[cx,cy]])
while len(data)>0 or len(data2)>0:
    while len(data)>0:
        xy=data.popleft()
        x,y=xy[0],xy[1]

        if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
            dep[x-1][y]=dep[x][y]
            data.append([x-1,y])
            data2.append([x-1,y])
        if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
            dep[x+1][y] = dep[x][y]
            data.append([x + 1,y])
            data2.append([x + 1,y])
        if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
            dep[x][y-1] = dep[x][y]
            data.append([x,y-1])
            data2.append([x,y-1])
        if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
            dep[x][y+1] = dep[x][y]
            data.append([x,y+1])
            data2.append([x,y+1])

    while len(data2)>0:
        xy=data2.popleft()
        x,y=xy[0],xy[1]
        for i in range(5):
            for j in range(5):
                if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                    dep[x-2+i][y-2+j]=dep[x][y]+1
                    data.append([x-2+i,y-2+j])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)

Submission status: Wrong Answer

Solution code:
from _collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    s[i+1]=x
s[0]=s[-1]=["#"]*(w+2)


dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy]])
data2=deque([[cx,cy]])
while len(data)>0 or len(data2)>0:
    while len(data)>0:
     xy=data.popleft()
     x,y=xy[0],xy[1]

     if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
         dep[x-1][y]=dep[x][y]
         data.append([x-1,y])
         data2.append([x-1,y])
     if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
         dep[x+1][y] = dep[x][y]
         data.append([x + 1,y])
         data2.append([x + 1, y])
     if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
         dep[x][y-1] = dep[x][y]
         data.append([x,y-1])
         data2.append([x,y-1])
     if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
         dep[x][y+1] = dep[x][y]
         data.append([x,y+1])
         data2.append([x,y+1])

    while len(data2)>0:
     xy=data2.popleft()
     x,y=xy[0],xy[1]
     for i in range(5):
         for j in range(5):
             if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                 dep[x-2+i][y-2+j]=dep[x][y]+1
                 data.append([x-2+i,y-2+j])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [input() for _ in range(H)]

used = [[-1]*W for _ in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
q = deque()
flag = True
num = 0
for k in range(H):
    for l in range(W):
        if S[k][l] == "#" or used[k][l] >= 0:
            continue
        used[k][l] = num
        q.append((num, k, l))
        while q:
            temp = q.popleft()
            num = temp[0]
            i = temp[1]
            j = temp[2]

            if i > 0 and S[i-1][j] == "." and used[i-1][j] == -1:
                used[i-1][j] = num
                q.append((num, i-1, j))
            if j > 0 and S[i][j-1] == "." and used[i][j-1] == -1:
                used[i][j-1] = num
                q.append((num, i, j-1))
            if i < H-1 and S[i+1][j] == "." and used[i+1][j] == -1:
                used[i+1][j] = num
                q.append((num, i+1, j))
            if j < W-1 and S[i][j+1] == "." and used[i][j+1] == -1:
                used[i][j+1] = num
                q.append((num, i, j+1))
        num += 1

E = [[] for _ in range(num)]
for i in range(H):
    for j in range(W):
        for k in range(i-2, i+3):
            for l in range(j-2, j+3):
                if k < 0 or k > H-1 or l < 0 or l > W-1:
                    continue
                if S[k][l] == "#":
                    continue
                if used[i][j] != used[k][l] and used[i][j] not in E[used[k][l]]:
                    E[used[i][j]].append(used[k][l])
                    E[used[k][l]].append(used[i][j])


dist = [10**6]*num
q = deque()
q.append((0, used[Ch][Cw]))
dist[used[Ch][Cw]] = 0
while q:
    temp = q.popleft()
    d = temp[0]
    i = temp[1]
    for e in E[i]:
        if dist[e] > d+1:
            dist[e] = d+1
            q.append((d+1, e))
if num == 1:
    print(0)
elif dist[used[Dh][Dw]] == 10**6:
    print(-1)
else:
    print(dist[used[Dh][Dw]])

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [input() for _ in range(H)]

used = [[-1]*W for _ in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
q = deque()
flag = True
num = 0
for k in range(H):
    for l in range(W):
        if S[k][l] == "#" or used[k][l] >= 0:
            continue
        used[k][l] = num
        q.append((num, k, l))
        while q:
            temp = q.popleft()
            num = temp[0]
            i = temp[1]
            j = temp[2]

            if i > 0 and S[i-1][j] == "." and used[i-1][j] == -1:
                used[i-1][j] = num
                q.append((num, i-1, j))
            if j > 0 and S[i][j-1] == "." and used[i][j-1] == -1:
                used[i][j-1] = num
                q.append((num, i, j-1))
            if i < H-1 and S[i+1][j] == "." and used[i+1][j] == -1:
                used[i+1][j] = num
                q.append((num, i+1, j))
            if j < W-1 and S[i][j+1] == "." and used[i][j+1] == -1:
                used[i][j+1] = num
                q.append((num, i, j+1))
        num += 1

E = [[] for _ in range(num)]
for i in range(H):
    for j in range(W):
        for k in range(i-2, i+3):
            for l in range(j-2, j+3):
                if k < 0 or k > H-1 or l < 0 or l > W-1:
                    continue
                if S[k][l] == "#":
                    continue
                if used[i][j] != used[k][l] and used[i][j] not in E[used[k][l]]:
                    E[used[i][j]].append(used[k][l])
                    E[used[k][l]].append(used[i][j])


dist = [10**6]*num
q = deque()
q.append((0, used[Ch][Cw]))
while q:
    temp = q.popleft()
    d = temp[0]
    i = temp[1]
    for e in E[i]:
        if dist[e] > d+1:
            dist[e] = d+1
            q.append((d+1, e))
if num == 1:
    print(0)
elif dist[used[Dh][Dw]] == 10**6:
    print(-1)
else:
    print(dist[used[Dh][Dw]])

Submission status: Wrong Answer

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]]])
def dfs(dq):
  while dq:
    cnt, h, w = dq.popleft()
    # 도착점에 도착하면 종료
    if [h,w] == D:
      print(cnt)
      exit()
    visited[h][w] = True
    # 상,하,좌,우 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):
        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])
dfs(dq)
print(-1)

Submission status: Wrong Answer

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]]])
def dfs(dq):
  while dq:
    cnt, h, w = dq.popleft()
    # 도착점에 도착하면 종료
    if [h,w] == D:
      print(cnt)
      exit()
    if visited[h][w]:
      continue
    visited[h][w] = True
    # 상,하,좌,우 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])
dfs(dq)
print(-1)

Submission status: Wrong Answer

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]]])
def dfs(dq):
  while dq:
    cnt, h, w = dq.popleft()
    # 도착점에 도착하면 종료
    if [h,w] == D:
      print(cnt)
      exit()
    visited[h][w] = True
    # 상,하,좌,우 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])
dfs(dq)
print(-1)

Submission status: Wrong Answer

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[C[0]][C[1]] = 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: Wrong Answer

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

while dq:
  cnt, h, w = dq.popleft()
  # 도착점에 도착하면 종료
  if [h,w] == D:
    print(cnt)
    exit()
  if visited[h][w]:
    continue
  visited[h][w] = True
  # 상,하,좌,우 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]):
      dq.appendleft([cnt,new_h,new_w])
  # 인접한 5x5 탐색
  for move_h in range(-2,2):
    for move_w in range(-2,2):
      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: Wrong Answer

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 for col in range(W)] for row in range(H)]
# bfs를 위한 큐 
dq = deque([[0,C[0],C[1]]])

while dq:
  cnt, h, w = dq.popleft()
  # 도착점에 도착하면 종료
  if [h,w] == D:
    print(cnt)
    exit()
  if visited[h][w]:
    continue
  visited[h][w] = True
  # 상,하,좌,우 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]):
      dq.appendleft([cnt,new_h,new_w])
  # 인접한 5x5 탐색
  for move_h in range(-2,2):
    for move_w in range(-2,2):
      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: Wrong Answer

Solution code:
from sys import stdin
import collections
def ip(): return [int(i) for i in stdin.readline().split()]
def sp(): return [str(i) for i in stdin.readline().split()]


h,r = ip()
i,j = ip()
ei, ej = ip()
i,j,ei,ej = i-1, j-1, ei-1, ej-1
A = []
for _  in range(h):
    A.append(list(str(input())))

def check(A,i,j):
    if i < 0 or i >= len(A) or j < 0 or j >= len(A[0]):
        return False
    return True

q = collections.deque()
q.append([i, j, 0, set((i,j))])
d = [(-1,0), (0,1), (1,0), (0,-1)]
magic = [(-2,-2), (-2,-1), (-2,0), (-2,1), (-2,2),
            (-1,2), (0,2), (1,2), (2,2),
            (2,1), (2,0), (2,-1), (2,-2),
            (1,-2), (0,-2), (-1,-2)]
ans = float('inf')
while q:
    i,j,n,visited = q.popleft()
    # print(f'[{i},{j}] | {n=}')
    if (i,j) == (ei,ej):
        # print("made it")
        ans = min(ans, n)
    for x,y in d:
        ni, nj = i + x, j + y
        if check(A, ni, nj):
            if (ni,nj) not in visited and A[ni][nj] != '#':
                visited.add((ni,nj))
                q.append([ni,nj,n,visited.copy()])
            elif A[ni][nj] == '#':
                for x,y in magic:
                    ni, nj = i + x, j + y
                    if check(A, ni, nj) and (ni, nj) not in visited:
                        visited.add((ni,nj))
                        q.append([ni,nj,n+1,visited.copy()])

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

Submission status: Wrong Answer

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:
                continue
            if grid[py_new][px_new] == '.':
                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_w:
                        continue
                    if grid[new_h][new_w] == '.' and dp[new_h][new_w] == -1:
                        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:
                        continue
                    if grid[new_h][new_w] == '.'and dp[new_h][new_w] == -1:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                        
                        
                
def main(dp_old):
    for i in range(100000):
        area_move(pos_que)

        if dp[gy][gx] != -1:
            return dp[gy][gx]
        magic_jump(i,ps)

        #print(i)
        if not pos_que:
            return -1
    return -1

print(main([]))

Submission status: Wrong Answer

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]
        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:
                continue
            if grid[py_new][px_new] == '.':
                dp[py_new][px_new] = d
                pos_que.append((px_new,py_new))
                ps.append((px_new,py_new))
                #print(ps)
    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)):
                    new_w = i+dx
                    new_h = j + dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                        continue
                    if grid[new_h][new_w] == '.' and dp[new_h][new_w] == -1:
                        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)):
                    new_w = i-dx
                    new_h = j-dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                        continue
                    if grid[new_h][new_w] == '.'and dp[new_h][new_w] == -1:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                        
                
def main(dp_old):
    for i in range(100000):
        area_move(pos_que)
        if dp[gy][gx] != -1:
            return dp[gy][gx]
        magic_jump(i,ps)

        #print(i)
        if not pos_que:
            return -1
    return -1

print(main([]))

Submission status: Wrong Answer

Solution code:

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]
        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:
                continue
            if grid[py_new][px_new] == '.':
                dp[py_new][px_new] = d
                pos_que.append((px_new,py_new))
                ps.append((px_new,py_new))
                #print(ps)
    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)):
                    new_w = i+dx
                    new_h = j + dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                        continue
                    if grid[new_h][new_w] == '.' and dp[new_h][new_w] == -1:
                        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)):
                    new_w = i-dx
                    new_h = j-dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                        continue
                    if grid[new_h][new_w] == '.'and dp[new_h][new_w] == -1:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                        
                
def main(dp_old):
    for i in range(100):
        area_move(pos_que)
        if dp[gy][gx] != -1:
            return dp[gy][gx]
        magic_jump(i,ps)

        #print(i)
        if not pos_que:
            return -1
    return -1

print(main([]))