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
from numba import njit, b1, i4, i8, f8
import numpy as np
import sys

read = sys.stdin.read
readline = sys.stdin.readline

@njit
def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[0]*(W) for _ in range(H)]
  for i in range(H):
    for j in range(W):
      dist[i][j] = INF
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  que1 = [(C_h,C_w)]
  que2 = []
  i,j = 0,0

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-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)]

  while True:
    if i==len(que1) and j==len(que2):
      break;
    while i<len(que1):
      h,w = que1[i]
      i += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
    while j<len(que2):
      h,w = que2[j]
      j += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = np.array([readline() for _ in range(H)])
solve(H,W,C_h,C_w,D_h,D_w,S)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from sys import stdin
from collections import deque


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

q = deque()

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

ch -= 1
cw -= 1
dh -= 1
dw -= 1

INF = 10 ** 18
org_list = deque()
cost_list = [[INF]*w for i in range(h)]

# for i in range(h):
#   # 文字列の入力
#   s = stdin.readline()
#   org_list.append(s)


org_list=list(map(lambda x: list(x.decode()), readlines()))

cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
# ido_h = [-1, 0, 1, 0]
# ido_w = [0, 1, 0, -1]
ido_x = [[-1, 0], [0, 1], [1, 0], [0, -1]]

magic = [[-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]]
# print(len(magic))

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]


  for ih, iw in ido_x:
    nh = ph + ih
    nw = pw + iw


  # for i in range(4):
  #   nh = ph + ido_h[i]
  #   nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]


    if val == "#" or val_cost <= cost:
      continue

    cost_list[nh][nw] = cost
    q.appendleft([nh, nw])


  # ワープ
  for ih, iw in magic:
    nh = ph + ih
    nw = pw + iw
    if nh < 0 or h -1 < nh:
      continue
    if nw < 0 or w -1 < nw:
      continue
    if cost_list[nh][nw] <= cost:
      continue

    if org_list[nh][nw] == ".":
      cost_list[nh][nw] = cost + 1
      q.append([nh, nw])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections

    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())
    grid = [[item for item in input()] for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from numba import njit, b1, i4, i8, f8
import sys

read = sys.stdin.read
readline = sys.stdin.readline

@njit
def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[0]*(W) for _ in range(H)]
  for i in range(H):
    for j in range(W):
      dist[i][j] = INF
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  que1 = [(C_h,C_w)]
  que2 = []
  i,j = 0,0

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-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)]

  while True:
    if i==len(que1) and j==len(que2):
      break;
    while i<len(que1):
      h,w = que1[i]
      i += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
    while j<len(que2):
      h,w = que2[j]
      j += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = [readline() for _ in range(H)]
solve(H,W,C_h,C_w,D_h,D_w,S)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections

    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())
    grid = [[item for item in input()] for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                    que.appendleft([ny, nx, w_num])
                    fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                nw = w_num +1
                if grid[ny][nx] == '.' and fp[ny][nx] > nw:
                    que.append([ny, nx, nw])
                    fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import collections

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())
grid = [[item for item in input()] for _ in range(H)]
max_num = 10**6
fp = [[max_num for _ in range(W)] for _ in range(H)]

que = collections.deque([[Ch, Cw, 0]])
fp[Ch][Cw] = 0
next_y_x = []
for i in range(5):
    for j in range(5):
        next_y_x.append([-2 + i, -2 + j])
next_y_x.remove([0,0])

while que:
    y, x, w_num = que.popleft()

    for dy, dx in next_y_x:
        ny = y + dy
        nx = x + dx

        if 0 <= ny <= H-1 and 0 <= nx <= W-1:
            if abs(dy) + abs(dx) == 1:
                if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                    que.appendleft([ny, nx, w_num])
                    fp[ny][nx] = w_num
            else:
                nw = w_num +1
                if grid[ny][nx] == '.' and fp[ny][nx] > nw:
                    que.append([ny, nx, nw])
                    fp[ny][nx] = nw

if fp[Dh][Dw] != max_num:
    print(fp[Dh][Dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections

    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())
    grid = [[item for item in input()] for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]
    
    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = []
    for i in range(5):
        for j in range(5):
            next_y_x.append([-2 + i, -2 + j])
    next_y_x.remove([0,0])

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in next_y_x:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if abs(dy) + abs(dx) == 1:
                    if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                        que.appendleft([ny, nx, w_num])
                        fp[ny][nx] = w_num
                else:
                    nw = w_num +1
                    if grid[ny][nx] == '.' and fp[ny][nx] > nw:
                        que.append([ny, nx, nw])
                        fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]
    
    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = []
    for i in range(5):
        for j in range(5):
            next_y_x.append([-2 + i, -2 + j])
    next_y_x.remove([0,0])

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in next_y_x:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if abs(dy) + abs(dx) == 1:
                    if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                        que.appendleft([ny, nx, w_num])
                        fp[ny][nx] = w_num
                else:
                    nw = w_num +1
                    if grid[ny][nx] == '.' and fp[ny][nx] > nw:
                        que.append([ny, nx, nw])
                        fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from sys import stdin
from collections import deque


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

q = deque()

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

ch -= 1
cw -= 1
dh -= 1
dw -= 1

INF = 10 ** 18
org_list = deque()
cost_list = [[INF]*w for i in range(h)]

# for i in range(h):
#   # 文字列の入力
#   s = stdin.readline()
#   org_list.append(s)


org_list=list(map(lambda x: list(x.decode()), readlines()))

cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

magic = [[-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]]
# print(len(magic))

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]

    # if val == "#" or val_cost == cost:
    #   continue
    # if val == "." or val_cost < val:
    #   cost_list[nh][nw] = cost
    #   q.appendleft([nh, nw])


    if val == "#" or val_cost <= cost:
      continue

    cost_list[nh][nw] = cost
    q.appendleft([nh, nw])


  # ワープ
  for ih, iw in magic:
    nh = ph + ih
    nw = pw + iw
    if nh < 0 or h -1 < nh:
      continue
    if nw < 0 or w -1 < nw:
      continue
    if cost_list[nh][nw] <= cost:
      continue

    if org_list[nh][nw] == ".":
      cost_list[nh][nw] = cost + 1
      q.append([nh, nw])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]
    
    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = []
    for i in range(5):
        for j in range(5):
            next_y_x.append([-2 + i, -2 + j])
    next_y_x.remove([0,0])

    while que:
        temp = que.popleft()
        w_num = temp[2]

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if abs(dy) + abs(dx) == 1:
                    if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                        que.appendleft([ny, nx, w_num])
                        fp[ny][nx] = w_num
                else:
                    nw = w_num +1
                    if grid[ny][nx] == '.' and fp[ny][nx] > nw:
                        que.append([ny, nx, nw])
                        fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()


if __name__ == "__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())
    maze = ["#"*(W+4), "#"*(W+4)]
    maze += [list("##"+input()+"##") for _ in range(H)]
    maze += ["#"*(W+4), "#"*(W+4)]
    INF = 10**8
    mc = [[INF]*(W+4) for _ in range(H+4)]
    mc[ch][cw] = 0
    walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    warp = [(y, x) for x in range(-2, 3) for y in range(-2, 3) if abs(y) + abs(x) > 1]
    que = deque()
    que.append((ch, cw, 0))
    while que:
        y, x, w = que.popleft()
        if mc[y][x] < w:
            continue
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if maze[ny][nx] == "." and mc[ny][nx] > w:
                mc[ny][nx] = w
                que.appendleft((ny, nx, w))
        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            if maze[ny][nx] == "." and mc[ny][nx] > w+1:
                mc[ny][nx] = w+1
                que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    import sys
    input = sys.stdin.readline

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]
    
    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = []
    for i in range(5):
        for j in range(5):
            next_y_x.append([-2 + i, -2 + j])
    next_y_x.remove([0,0])

    while que:
        temp = que.popleft()
        w_num = temp[2]

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if abs(dy) + abs(dx) == 1:
                    if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                        que.appendleft([ny, nx, w_num])
                        fp[ny][nx] = w_num
                else:
                    nw = w_num +1
                    if grid[ny][nx] == '.' and fp[ny][nx] == max_num:
                        que.append([ny, nx, nw])
                        fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()


if __name__ == "__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())
    maze = [list(input()) for _ in range(H)]
    INF = 10**8
    mc = [[INF]*W for _ in range(H)]
    mc[ch][cw] = 0
    walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    warp = [(y, x) for x in range(-2, 3) for y in range(-2, 3) if abs(y) + abs(x) > 1]
    que = deque()
    que.append((ch, cw, 0))
    while que:
        y, x, w = que.popleft()
        if mc[y][x] < w:
            continue
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w and maze[ny][nx] == ".":
                mc[ny][nx] = w
                que.appendleft((ny, nx, w))
        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w+1 and maze[ny][nx] == ".":
                mc[ny][nx] = w + 1
                que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    import sys
    input = sys.stdin.readline

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    fp = [[10**6 for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = []
    for i in range(5):
        for j in range(5):
            next_y_x.append([-2 + i, -2 + j])
    next_y_x.remove([0,0])

    while que:
        temp = que.popleft()
        w_num = temp[2]

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if abs(dy) + abs(dx) == 1:
                    if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                        que.appendleft([ny, nx, w_num])
                        fp[ny][nx] = w_num
                else:
                    nw = w_num +1
                    if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                        que.append([ny, nx, nw])
                        fp[ny][nx] = nw

    if fp[Dh][Dw] != 10**6:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# import numpy as np
# from numba import njit

from sys import stdin
from collections import deque

def mytest():

  q = deque()

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

  ch -= 1
  cw -= 1
  dh -= 1
  dw -= 1

  INF = 10 ** 18
  org_list = deque()
  cost_list = [[INF]*w for i in range(h)]

  for _ in range(h):
    org_list.append(stdin.readline())

  cost_list[ch][cw] = 0

  cost = 0
  ph = ch
  pw = cw

  q.append([ph, pw])

  # 上右下左
  ido_h = [-1, 0, 1, 0]
  ido_w = [0, 1, 0, -1]

  magic = [[-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]]
  while q:

    ph, pw = q.popleft()
    cost = cost_list[ph][pw]

    for i in range(4):
      nh = ph + ido_h[i]
      nw = pw + ido_w[i]

      if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
        continue
      val = org_list[nh][nw]
      val_cost = cost_list[nh][nw]

      if val == "#" or val_cost <= cost:
        continue

      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])

    # ワープ
    for ih, iw in magic:
      nh = ph + ih
      nw = pw + iw
      if nh < 0 or h -1 < nh:
        continue
      if nw < 0 or w -1 < nw:
        continue
      if cost_list[nh][nw] <= cost:
        continue

      if org_list[nh][nw] == ".":
        cost_list[nh][nw] = cost + 1
        q.append([nh, nw])

  result = cost_list[dh][dw]
  if result == INF:
    result = -1

  print(result)

mytest()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve(H, W, Ch, Cw, Dh, Dw, maze):
    INF = 1 << 30
    path = [[INF] * W for _ in range(H)]

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    while q:
        y, x, s = q.popleft()
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and path[ny][nx] > s:
                path[ny][nx] = s
                q.appendleft((ny, nx, s))
        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and path[ny][nx] > s + 1:
                path[ny][nx] = s + 1
                q.append((ny, nx, s + 1))

    ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
    print(ans)


if __name__ == "__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())
    maze = [input() for _ in range(H)]
    solve(H, W, Ch, Cw, Dh, Dw, maze)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve(H, W, Ch, Cw, Dh, Dw, maze):
    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    while q:
        y, x, s = q.popleft()
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and path[ny][nx] > s:
                path[ny][nx] = s
                q.appendleft((ny, nx, s))
        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and path[ny][nx] > s + 1:
                path[ny][nx] = s + 1
                q.append((ny, nx, s + 1))

    ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
    print(ans)


if __name__ == "__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())
    maze = [input() for _ in range(H)]
    solve(H, W, Ch, Cw, Dh, Dw, maze)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    import sys
    input = sys.stdin.readline

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    fp = [[10**6 for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    w_goto = []
    for i in range(5):
        for j in range(5):
            if [i, j] in next_y_x:
                pass
            else:
                w_goto.append([-2 + i, -2 + j])
    w_goto.remove([0,0])

    while que:
        temp = que.popleft()
        w_num = temp[2]

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                    que.appendleft([ny, nx, temp[2]])
                    fp[ny][nx] = w_num
        
        for dy, dx in w_goto:
            nwy = temp[0] + dy
            nwx = temp[1] + dx
            nw = w_num +1

            if 0 <= nwy <= H-1 and 0 <= nwx <= W-1:
                if grid[nwy][nwx] == '.' and fp[nwy][nwx] > w_num:
                    que.append([nwy, nwx, nw])
                    fp[nwy][nwx] = nw


    if fp[Dh][Dw] != 10**6:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(sy, sx):
    t = ((-1,0),(0,-1),(1,0),(0,1))
    dist = [[inf]*w for i in range(h)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])
    while(q):
        y,x = q.popleft()
        d = dist[y][x]
        for i,j in t:
            ny,nx = y+i,x+j
            if (0 <= nx < w and 0 <= ny < h):
                if dist[ny][nx] <= d or s[ny][nx] == "#":
                    continue
                q.appendleft((y+i,x+j))
                dist[ny][nx] = d
        for i in range(-2,3):
            for j in range(-2,3):
                ny,nx = y+i,x+j
                if (0 <= nx < w and 0 <= ny < h):
                    if dist[ny][nx] <= d+1 or s[ny][nx] == "#":
                        continue
                    q.append((ny,nx))
                    dist[ny][nx] = d+1
    return dist

inf = 10**9
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [input() for i in range(h)]
ch, cw = ch - 1, cw - 1
dh, dw = dh - 1, dw - 1
dist = bfs(ch,cw)
ans = dist[dh][dw]
if ans == inf:
    ans = -1
print(ans)