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: Time Limit Exceeded

Solution code:
from collections import deque
import sys

H,W = map(int,sys.stdin.readline().split())
C = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
D = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
# matrix 배열
board = [sys.stdin.readline() for _ in range(H)]
# 방문경로 배열
visited = [[False] * W for _ in range(H)]
# 좌/우/위/아래 방향 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 5x5 방향 이동
dx2 = [-2,-2,-2,-2,-2,
       -1,-1,-1,-1,-1,
        0, 0, 0, 0,
        1, 1, 1, 1, 1,
        2, 2, 2, 2, 2]   
dy2 = [-2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2]
# bfs를 위한 큐 
dq = deque([[0,C[0],C[1]]])

while dq:
  cnt, x, y = dq.popleft()
  # 도착점에 도착하면 종료
  if [x,y] == D:
    print(cnt)
    exit()
  # 상,하,좌,우 1칸씩 이동
  for k in range(4):
    newX = x + dx[k]
    newY = y + dy[k]
    # 걸어서 갈 수 있는 경우 앞에서부터 큐에 넣음
    if newX < 0 or newY < 0 or newX >= H or newY >= W:
      continue
    if visited[newX][newY] == True:
      continue
    if board[newX][newY] != '.':
      continue
    dq.appendleft([cnt,newX,newY])
    visited[x][y] = True
  # 인접한 5x5 탐색
  for k in range(24):
    newX = x + dx2[k]
    newY = y + dy2[k]
    # 마법을 사용한 경우 뒤에서부터 큐에 넣음
    if newX < 0 or newY < 0 or newX >= H or newY >= W:
      continue
    if visited[newX][newY] == True:
      continue
    if board[newX][newY] != '.':
      continue
    dq.append([cnt+1,newX,newY])
    visited[x][y] = True
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

H,W = map(int,sys.stdin.readline().split())
C = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
D = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
# matrix 배열
board = [sys.stdin.readline() for _ in range(H)]
# 방문경로 배열
visited = [[False] * W for _ in range(H)]
# 좌/우/위/아래 방향 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 5x5 방향 이동
dx2 = [-2,-2,-2,-2,-2,
       -1,-1,-1,-1,-1,
        0, 0, 0, 0,
        1, 1, 1, 1, 1,
        2, 2, 2, 2, 2]   
dy2 = [-2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2]
# bfs를 위한 큐 
dq = deque([[0,C[0],C[1]]])

while dq:
  cnt, x, y = dq.popleft()
  # 도착점에 도착하면 종료
  if [x,y] == D:
    print(cnt)
    exit()
  visited[x][y] = True
  # 상,하,좌,우 1칸씩 이동
  for k in range(4):
    newX = x + dx[k]
    newY = y + dy[k]
    # 걸어서 갈 수 있는 경우 앞에서부터 큐에 넣음
    if newX < 0 or newY < 0 or newX >= H or newY >= W:
      continue
    if visited[newX][newY] == True:
      continue
    if board[newX][newY] != '.':
      continue
    dq.appendleft([cnt,newX,newY])
  # 인접한 5x5 탐색
  for k in range(24):
    newX = x + dx2[k]
    newY = y + dy2[k]
    # 마법을 사용한 경우 뒤에서부터 큐에 넣음
    if newX < 0 or newY < 0 or newX >= H or newY >= W:
      continue
    if visited[newX][newY] == True:
      continue
    if board[newX][newY] != '.':
      continue
    dq.append([cnt+1,newX,newY])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

H,W = map(int,sys.stdin.readline().split())
C = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
D = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
# matrix 배열
board = [sys.stdin.readline() for _ in range(H)]
# 방문경로 배열
visited = [[False] * W for _ in range(H)]
# 좌/우/위/아래 방향 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 5x5 방향 이동
dx2 = [-2,-2,-2,-2,-2,
       -1,-1,-1,-1,-1,
        0, 0, 0, 0,
        1, 1, 1, 1, 1,
        2, 2, 2, 2, 2]   
dy2 = [-2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2]
# bfs를 위한 큐 
dq = deque([[0,C[0],C[1]]])

while dq:
  cnt, x, y = dq.popleft()
  # 도착점에 도착하면 종료
  if [x,y] == D:
    print(cnt)
    exit()
  visited[x][y] = True
  # 상,하,좌,우 1칸씩 이동
  for k in range(4):
    newX = x + dx[k]
    newY = y + dy[k]
    # 걸어서 갈 수 있는 경우 앞에서부터 큐에 넣음
    if 0 <= newX < H and 0 <= newY < W and board[newX][newY] == '.' and (not visited[newX][newY]):
        dq.appendleft([cnt,newX,newY])
  # 인접한 5x5 탐색
  for k in range(24):
    newX = x + dx2[k]
    newY = y + dy2[k]
    # 마법을 사용한 경우 뒤에서부터 큐에 넣음
    if 0 <= newX < H and 0 <= newY < W and board[newX][newY] == '.' and (not visited[newX][newY]):
        dq.append([cnt+1,newX,newY])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

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()))
# matrix 배열
board = [input() for _ in range(H)]
# 방문경로 배열
visited = [[False] * W for _ in range(H)]
# 좌/우/위/아래 방향 이동
dx = [-1, 1, 0, 0, 0]
dy = [0, 0, 0, -1, 1]
# 5x5 방향 이동
dx2 = [-2,-2,-2,-2,-2,
       -1,-1,-1,-1,-1,
        0, 0, 0, 0, 0,
        1, 1, 1, 1, 1,
        2, 2, 2, 2, 2]   
dy2 = [-2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2]
# bfs를 위한 큐 
dq = deque([[0,C[0],C[1]]])

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

Submission status: Time Limit Exceeded

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]):
        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]):
          dq.append([cnt+1,new_h,new_w])
dfs(dq)
print(-1)

Submission status: Time Limit Exceeded

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
  # 상,하,좌,우 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[h][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[h][w] = True
        dq.append([cnt+1,new_h,new_w])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
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()))
S = [input() for _ in range(H)]
check_visited = [[False] * W for _ in range(H)]
dq = deque([[0, C[0], C[1]]])
while dq:
   d, i, j = dq.popleft()
   if [i, j] == D:
      print(d)
      exit()
   if check_visited[i][j]:
      continue
   check_visited[i][j] = True
   for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
      new_i = i + move_h
      new_j = j + move_w
      if 0 <= new_i <= H-1 and 0 <= new_j <= W-1 and S[new_i][new_j] == '.' and (not check_visited[new_i][new_j]) :
         dq.appendleft([d, new_i, new_j])
   for move_h in range(-2, 3):
      for move_w in range(-2, 3):
         if [move_h, move_w] == [0, 0]:
            continue
         new_i = i + move_h
         new_j = j + move_w
         if 0 <= new_i <= H-1 and 0 <= new_j <= W-1 and S[new_i][new_j] == '.' and (not check_visited[new_i][new_j]) :
            dq.append([d+1, new_i, new_j])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
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()))
S = [input() for _ in range(H)]
check_visited = [[False] * W for _ in range(H)]
dq = deque([[0, C[0], C[1]]])
while dq:
  d, i, j = dq.popleft()
  if [i, j] == D:
    print(d)
    exit()
  if check_visited[i][j]:
      continue
  check_visited[i][j] = True
  for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
    new_i = i + move_h
    new_j = j + move_w
    if 0 <= new_i <= H-1 and 0 <= new_j <= W-1 and S[new_i][new_j] == '.' and (not check_visited[new_i][new_j]) :
       dq.appendleft([d, new_i, new_j])
  for move_h in range(-2, 3):
     for move_w in range(-2, 3):
        if [move_h, move_w] == [0, 0]:
           continue
        new_i = i + move_h
        new_j = j + move_w
        if 0 <= new_i <= H-1 and 0 <= new_j <= W-1 and S[new_i][new_j] == '.' and (not check_visited[new_i][new_j]) :
           dq.append([d+1, new_i, new_j])
print(-1)

Submission status: Time Limit Exceeded

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,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: Time Limit Exceeded

Solution code:
from collections import deque
import copy
import sys

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,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: Time Limit Exceeded

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,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: Time Limit Exceeded

Solution code:
def main():
    H, W = [int(s) for s in input().split()]
    sh, sw = [int(s) -1 for s in input().split()]
    gh, gw = [int(s) -1 for s in input().split()]
    maze = []
    for i in range(H):
        maze.append(input())
    queue = [(sh, sw)]
    skip = 0
    seen = {(sh, sw)}
    nqs = set()
    while queue:
        nq = []
        while queue:
            x, y = queue.pop()
            if x == gh and gw == y:
                print(skip)
                return
            for i,j in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                if 0 <= i+x < H and 0 <= j+y < W:
                    ns = (i+x, j+y)
                    if maze[i+x][j+y] == '.':
                        if ns in seen:
                            continue
                        seen.add(ns)
                        queue.append(ns)
            ns = (x,y)
            if ns not in nqs:
                nqs.add(ns)
                nq.append(ns)

        skip += 1
        queue = []
        for x, y in nq:
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if 0 <= i+x < H and 0 <= j+y < W:
                        if maze[i+x][j+y] == '.':
                            ns = (i+x, j+y)
                            if ns not in seen:
                                seen.add(ns)
                                queue.append(ns)
        # print(queue)
    print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	H, W = [int(h) for h in input().split(" ")]
	sH, sW = [int(st) for st in input().split(" ")]
	gH, gW = [int(gl) for gl in input().split(" ")]
	S = []
	S.append(["X"] * (W + 4))
	S.append(["X"] * (W + 4))
	for i in range(H):
		S.append(["X", "X"] + list(input()) + ["X", "X"])
	S.append(["X"] * (W + 4))
	S.append(["X"] * (W + 4))

	sH += 1
	sW += 1
	gH += 1
	gW += 1
	neighbor = [[1, 0], [-1, 0], [0, 1], [0, -1]]
	warp = [[1, 1], [1, -1], [-1, 1], [-1, -1], [2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [0, 2], [-1, 2], [-2, 2], [1, -2], [0, -2], [-1, -2], [-2, -2], [-2, 1], [-2, 0], [-2, -1]]
	to_visit = [[sH, sW]]
	checked = [[0 for i in range(W + 4)] for j in range(H + 4)]
	steps = [[-1 for i in range(W + 4)] for j in range(H + 4)]
	checked[sH][sW] = 1
	steps[sH][sW] = 0
	while len(to_visit) > 0:
		visiting = to_visit.pop(0)
		y = visiting[0]
		x = visiting[1]
		s = steps[y][x]
		for d in neighbor:
			dy = d[0]
			dx = d[1]
			if S[y + dy][x + dx] == "." and checked[y + dy][x + dx] != 1:
				checked[y + dy][x + dx] = 1
				to_visit.append([y + dy, x + dx])
				if steps[y + dy][x + dx] == -1 or steps[y + dy][x + dx] > s:
					steps[y + dy][x + dx] = s
		for d in warp:
			dy = d[0]
			dx = d[1]
			if S[y + dy][x + dx] == "." and checked[y + dy][x + dx] != 1:
				checked[y + dy][x + dx] = 2
				to_visit.append([y + dy, x + dx])
				if steps[y + dy][x + dx] == -1 or steps[y + dy][x + dx] > s:
					steps[y + dy][x + dx] = s + 1
	print(steps[gH][gW])

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    h, w = map(int, input().split())
    S = list(map(lambda x: int(x) + 1, input().split()))
    G = list(map(lambda x: int(x) + 1, input().split()))
    A = ['#' * (w + 4)] * 2 + ['##' + input() + '##' for _ in range(h)] + ['#' * (w + 4)] * 2
    INF = 1000000
    score = [[INF] * (w + 2) for _ in range(h + 2)]
    score[S[0]][S[1]] = 0
    stack = deque([S])
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    magic = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in walk + [(0, 0)]]
    while stack:
        y, x = stack.popleft()
        for dx, dy in walk:
            X, Y = x + dx, y + dy 
            if A[Y][X] == '#': continue
            if score[Y][X] > (s := score[y][x]):
                stack.appendleft([Y, X])
                score[Y][X] = s
        for dx, dy in magic:
            X, Y = x + dx, y + dy 
            if A[Y][X] == '#': continue
            if score[Y][X] > (s := score[y][x] + 1):
                stack.append([Y, X])
                score[Y][X] = s
    print(ans if (ans := score[G[0]][G[1]]) != INF else -1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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]) or A[i][j] == '#':
        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):
        ans = min(ans, n)
        break
    for x,y in d:
        ni, nj = i + x, j + y
        if check(A, ni, nj) and (ni,nj) not in visited:
            visited.add((ni,nj))
            q.appendleft([ni,nj,n,visited.copy()])
    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: Time Limit Exceeded

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]) or A[i][j] == '#':
        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) and (ni,nj) not in visited:
            visited.add((ni,nj))
            q.append([ni,nj,n,visited.copy()])
    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: Time Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b, w):
		self.graph[a].append([b, w])

class BFS0_1(object):
	def  __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque()
		self.Q.append(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i, w in self.g[v]:
				if w:
					dis = self.dist[v]
					if dis + 1 >= self.dist[i]:
						continue
					self.dist[i] = dis + 1
					self.Q.append(i)
				else:
					dis = self.dist[v]
					if dis >= self.dist[i]:
						continue
					self.dist[i] = dis
					self.Q.appendleft(i)

def main():
	H, W = getlist()
	Ch, Cw = getlist()
	Dh, Dw = getlist()
	L = [[0] * (W + 4)]
	L.append([0] * (W + 4))
	for i in range(H):
		l = list(input())
		l = [0 if l[j] == "#" else 1 for j in range(W)]
		L.append([0, 0] + l + [0, 0])

	L.append([0] * (W + 4))
	L.append([0] * (W + 4))

	G = Graph()

	for p in range(-2, 3):
		for q in range(-2, 3):
			for h in range(2, H + 2):
				for w in range(2, W + 2):
					if L[h][w] and L[h + p][w + q]:
						d = abs(p) + abs(q)
						if d >= 2:
							G.add_edge(W * h + w, W * (h + p) + w + q, 1)
						elif d == 1:
							G.add_edge(W * h + w, W * (h + p) + w + q, 0)


	N = (H + 4) * (W + 4)
	BF = BFS0_1(G, W * (Ch + 1) + Cw + 1, N)
	ans = BF.dist[W * (Dh + 1) + Dw + 1]
	if ans == INF:
		print(-1)
	else:
		print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b, w):
		self.graph[a].append([b, w])

class BFS0_1(object):
	def  __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque()
		self.Q.append(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i, w in self.g[v]:
				if w:
					dis = self.dist[v]
					if dis + 1 >= self.dist[i]:
						continue
					self.dist[i] = dis + 1
					self.Q.append(i)
				else:
					dis = self.dist[v]
					if dis >= self.dist[i]:
						continue
					self.dist[i] = dis
					self.Q.appendleft(i)

def main():
	H, W = getlist()
	Ch, Cw = getlist()
	Dh, Dw = getlist()
	L = [[0] * (W + 4)]
	L.append([0] * (W + 4))
	for i in range(H):
		l = list(input())
		l = [0 if l[j] == "#" else 1 for j in range(W)]
		L.append([0, 0] + l + [0, 0])

	L.append([0] * (W + 4))
	L.append([0] * (W + 4))


	G = Graph()
	for h in range(2, H + 2):
		for w in range(2, W + 2):
			if L[h][w]:
				for p in range(-2, 3):
					for q in range(-2, 3):
						if L[h + p][w + q]:
							d = abs(p) + abs(q)
							if d >= 2:
								G.add_edge(W * h + w, W * (h + p) + w + q, 1)
							elif d == 1:
								G.add_edge(W * h + w, W * (h + p) + w + q, 0)


	N = (H + 4) * (W + 4)
	BF = BFS0_1(G, W * (Ch + 1) + Cw + 1, N)
	ans = BF.dist[W * (Dh + 1) + Dw + 1]
	if ans == INF:
		print(-1)
	else:
		print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b, w):
		self.graph[a].append([b, w])

class BFS0_1(object):
	def  __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque()
		self.Q.append(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i, w in self.g[v]:
				if w:
					dis = self.dist[v]
					if dis + 1 >= self.dist[i]:
						continue
					self.dist[i] = dis + 1
					self.Q.append(i)
				else:
					dis = self.dist[v]
					if dis >= self.dist[i]:
						continue
					self.dist[i] = dis
					self.Q.appendleft(i)

def main():
	H, W = getlist()
	Ch, Cw = getlist()
	Dh, Dw = getlist()
	L = [[0] * (W + 4)]
	L.append([0] * (W + 4))
	for i in range(H):
		l = list(input())
		l = [0 if l[j] == "#" else 1 for j in range(W)]
		L.append([0, 0] + l + [0, 0])

	L.append([0] * (W + 4))
	L.append([0] * (W + 4))


	G = Graph()
	for h in range(2, H + 2):
		for w in range(2, W + 2):
			if L[h][w]:
				v = W * h + w
				for p in range(-2, 3):
					for q in range(-2, 3):
						if L[h + p][w + q]:
							d = abs(p) + abs(q)
							if d == 0:
								pass
							elif d >= 2:
								G.add_edge(v, W * (h + p) + w + q, 1)
							else:
								G.add_edge(v, W * (h + p) + w + q, 0)


	N = (H + 4) * (W + 4)
	BF = BFS0_1(G, W * (Ch + 1) + Cw + 1, N)
	ans = BF.dist[W * (Dh + 1) + Dw + 1]
	if ans == INF:
		print(-1)
	else:
		print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b, w):
		self.graph[a].append([b, w])

class BFS0_1(object):
	def  __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque()
		self.Q.append(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i, w in self.g[v]:
				if w:
					dis = self.dist[v]
					if dis + 1 >= self.dist[i]:
						continue
					self.dist[i] = dis + 1
					self.Q.append(i)
				else:
					dis = self.dist[v]
					if dis >= self.dist[i]:
						continue
					self.dist[i] = dis
					self.Q.appendleft(i)

def main():
	H, W = getlist()
	Ch, Cw = getlist()
	Dh, Dw = getlist()
	L = [[0] * (W + 4)]
	L.append([0] * (W + 4))
	for i in range(H):
		l = list(input())
		l = [0 if l[j] == "#" else 1 for j in range(W)]
		L.append([0, 0] + l + [0, 0])

	L.append([0] * (W + 4))
	L.append([0] * (W + 4))


	G = Graph()
	for h in range(2, H + 2):
		for w in range(2, W + 2):
			if L[h][w]:
				for p in range(-2, 3):
					for q in range(-2, 3):
						if L[h + p][w + q]:
							d = abs(p) + abs(q)
							if d == 0:
								pass
							elif d >= 2:
								G.add_edge(W * h + w, W * (h + p) + w + q, 1)
							else:
								G.add_edge(W * h + w, W * (h + p) + w + q, 0)


	N = (H + 4) * (W + 4)
	BF = BFS0_1(G, W * (Ch + 1) + Cw + 1, N)
	ans = BF.dist[W * (Dh + 1) + Dw + 1]
	if ans == INF:
		print(-1)
	else:
		print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b, w):
		self.graph[a].append([b, w])

class BFS0_1(object):
	def  __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque()
		self.Q.append(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i, w in self.g[v]:
				if w:
					if self.dist[v] + 1 >= self.dist[i]:
						continue
					self.dist[i] = self.dist[v] + 1
					self.Q.append(i)
				else:
					if self.dist[v] >= self.dist[i]:
						continue
					self.dist[i] = self.dist[v]
					self.Q.appendleft(i)

def main():
	H, W = getlist()
	Ch, Cw = getlist()
	Dh, Dw = getlist()
	L = [[0] * (W + 4)]
	L.append([0] * (W + 4))
	for i in range(H):
		l = list(input())
		l = [0 if l[j] == "#" else 1 for j in range(W)]
		L.append([0, 0] + l + [0, 0])

	L.append([0] * (W + 4))
	L.append([0] * (W + 4))


	G = Graph()
	for h in range(2, H + 2):
		for w in range(2, W + 2):
			if L[h][w]:
				for p in range(-2, 3):
					for q in range(-2, 3):
						if L[h + p][w + q]:
							d = abs(p) + abs(q)
							if d == 0:
								pass
							elif d >= 2:
								G.add_edge(W * h + w, W * (h + p) + w + q, 1)
								# G.add_edge(W * (h + p) + w + q, W * h + w, 1)
							else:
								G.add_edge(W * h + w, W * (h + p) + w + q, 0)
								# G.add_edge(W * (h + p) + w + q, W * h + w, 0)


	N = (H + 4) * (W + 4)
	BF = BFS0_1(G, W * (Ch + 1) + Cw + 1, N)
	ans = BF.dist[W * (Dh + 1) + Dw + 1]
	if ans == INF:
		print(-1)
	else:
		print(ans)


if __name__ == '__main__':
	main()