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

def main(H, W, C, D, S):
    def inside(x, y):
        return ((0 <= x and x < H) and (0 <= y and y < W))

    def isroad(x, y):
        return S[x][y] == '.'

    C, D = list(map(lambda x:[x[0]-1, x[1]-1], [C, D])) # python方式に直す


    next = {tuple(C)}
    masu = [[-1 for _ in range(W)] for __ in range(H)]

    def moverange(x, y):
        return inside(x, y) and masu[x][y] == -1 and isroad(x, y)

    def up(x, y):
        return [x-1, y]

    def down(x, y):
        return [x+1, y]

    def right(x, y):
        return [x, y+1]

    def left(x, y):
        return [x, y-1]

    def func(now, direction, kaisu):
        while True:
            canmove = direction(*now)
            if moverange(*canmove):
                que.append(canmove)
                masu[canmove[0]][canmove[1]] = kaisu
            else:
                break

    def make_st(x, y):
        return {(x+i, y+j) for i in range(-2, 3) for j in range(-2, 3)}

    kaisu = -1
    while masu[D[0]][D[1]] == -1 and len(next) != 0:
        kaisu += 1
        que = deque(next)
        next = set()
        while que:
            now = que.popleft()
            if moverange(*now):
                masu[now[0]][now[1]] = kaisu
            func(now, up, kaisu)
            func(now, down, kaisu)
            func(now, right, kaisu)
            func(now, left, kaisu)

            for canmove in make_st(*now):
                if moverange(*canmove):
                    next.add(canmove)
    ans = masu[D[0]][D[1]]
    print(ans)


if __name__ == '__main__':
    H, W = list(map(int, input().split()))
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))
    S = []
    for _ in range(H):
        S.append(input())
    main(H, W, C, D, S)

Submission status: Time Limit Exceeded

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


def validate_pos(y, x, h, w):
    if y < 0 or y >= h or x < 0 or x >= w:
        return False
    else:
        return True


def main():
    h, w = map(int, input().split())
    sy, sx = map(int, input().split())
    gy, gx = map(int, input().split())
    field = [input().rstrip() for _ in range(h)]
    seen = set()
    todo = deque([(sy-1, sx-1)])
    tmp_visited = []

    shifts = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    warp_dist = [-2, -1, 0, 1, 2]
    warps = list(product(warp_dist, repeat=2))
    ans = 0
    while True:
        while todo:
            y, x = todo.popleft()
            tmp_visited.append((y, x))

            for dy, dx in shifts:
                ny, nx = y+dy, x+dx
                if not validate_pos(ny, nx, h, w):
                    continue
                if ny == gy-1 and nx == gx-1:
                    print(ans)
                    return
                if field[ny][nx] == "#":
                    continue
                if (ny, nx) in seen:
                    continue
                todo.append((ny, nx))
                seen.add((ny, nx))
                tmp_visited.append((ny, nx))

        ans += 1
        if not tmp_visited:
            print(-1)
            return

        for y, x in tmp_visited:
            for dy, dx in warps:
                ny, nx = y+dy, x+dx
                if not validate_pos(ny, nx, h, w):
                    continue
                if field[ny][nx] == "#":
                    continue
                if ny == gy-1 and nx == gx-1:
                    print(ans)
                    return
                if (ny, nx) in seen:
                    continue
                todo.append((ny, nx))
                seen.add((ny, nx))

        tmp_visited = []


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def bfs(MAZE, start, goal):
    walks = [(0,1), (1,0), (-1,0), (0, -1)]
    warps = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0: continue
            if not (i,j) in walks:
                warps.append((i, j))
    queue = deque([])
    k = (0,) + start
    queue.append(k)
    seen = set()
    seen.add(start)

    while queue:
        count, ci, cj = queue.pop()
        seen.add((ci, cj))
        if (ci, cj) == goal:
            return count
        for ii, jj in walks:
            ni, nj = ci + ii, cj + jj
            if MAZE[ni][nj] == '.' and not (ni, nj) in seen:
                queue.append((count, ni, nj))
        for ii, jj in warps:
            ni, nj = ci + ii, cj + jj
            if MAZE[ni][nj] == '.' and not (ni, nj) in seen:
                queue.appendleft((count+1, ni, nj))
    return -1


def run():
    H, W = map(int, sysread().split())
    Ci, Cj = map(int, sysread().split())
    Ci += 1
    Cj += 1
    Di, Dj = map(int, sysread().split())
    Di += 1
    Dj += 1
    MAZE = []
    MAZE.append('#' * (W + 4))
    MAZE.append('#' * (W + 4))
    for i in range(H):
        s = input()
        s = '##' + s + '##'
        MAZE.append(s)
    MAZE.append('#' * (W + 4))
    MAZE.append('#' * (W + 4))
    print(bfs(MAZE, (Ci, Cj), (Di, Dj)))





if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch,cw]]
    used_map = np.full((h,w),-1,dtype=np.int64)

    #move walk
    while used_map[dh][dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,th,tw = dot[0],dot[1],dot[2]
        used_map[th][tw] = tl

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(th+ x < 0 or tw+y < 0 or th+x >= h or tw+y >= w):
                    if (used_map[th+x][tw+y] == -1 or used_map[th+x][tw+y] > tl+1) and road_map[th+x][tw+y] == False:
                        if x == y == 0:
                            continue
                        if abs(x)+abs(y) <= 1:
                            heapq.heappush(queue,[tl,th+x,tw+y])
                        else:
                            heapq.heappush(queue,[tl+1,th+x,tw+y])

    print(used_map[dh,dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main(H, W, C, D, S):
    def inside(x, y):
        return ((0 <= x and x < H) and (0 <= y and y < W))

    def isroad(x, y):
        return S[x][y] == '.'

    C, D = list(map(lambda x:[x[0]-1, x[1]-1], [C, D])) # python方式に直す

    '''
    上:up
    下:down
    右:right
    左:left
    '''

    next = {tuple(C)}
    masu = [[-1 for _ in range(W)] for __ in range(H)]

    def moverange(x, y):
        return inside(x, y) and masu[x][y] == -1 and isroad(x, y)

    def up(x, y):
        return [x-1, y]

    def down(x, y):
        return [x+1, y]

    def right(x, y):
        return [x, y+1]

    def left(x, y):
        return [x, y-1]

    def func(now, direction, kaisu):
        while True:
            canmove = direction(*now)
            if moverange(*canmove):
                que.append(canmove)
                masu[canmove[0]][canmove[1]] = kaisu
            else:
                break

    def make_lst(x, y):
        return [[x+i, y+j] for i in range(-2, 3) for j in range(-2, 3)]

    kaisu = -1
    while masu[D[0]][D[1]] == -1 and len(next) != 0:
        kaisu += 1
        que = deque(next)
        next = set()
        while que:
            now = que.popleft()
            if moverange(*now):
                masu[now[0]][now[1]] = kaisu
            func(now, up, kaisu)
            func(now, down, kaisu)
            func(now, right, kaisu)
            func(now, left, kaisu)

            for canmove in make_lst(*now):
                if moverange(*canmove):
                    next.add(tuple(canmove))
    ans = masu[D[0]][D[1]]
    print(ans)


if __name__ == '__main__':
    H, W = list(map(int, input().split()))
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))
    S = []
    for _ in range(H):
        S.append(input())
    main(H, W, C, D, S)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main(H, W, C, D, S):
    def inside(x, y):
        return ((0 <= x and x < H) and (0 <= y and y < W))

    def isroad(x, y):
        return S[x][y] == '.'

    C, D = list(map(lambda x:[x[0]-1, x[1]-1], [C, D])) # python方式に直す

    '''
    上:up
    下:down
    右:right
    左:left
    '''

    next = {tuple(C)}
    masu = [[-1 for _ in range(W)] for __ in range(H)]

    def moverange(x, y):
        return inside(x, y) and masu[x][y] == -1 and isroad(x, y)

    def up(x, y):
        return [x-1, y]

    def down(x, y):
        return [x+1, y]

    def right(x, y):
        return [x, y+1]

    def left(x, y):
        return [x, y-1]

    def func(now, direction, kaisu):
        while True:
            canmove = direction(*now)
            if moverange(*canmove):
                que.append(canmove)
                masu[canmove[0]][canmove[1]] = kaisu
            else:
                break

    def make_lst(x, y):
        return [[x+i, y+j] for i in range(-2, 3) for j in range(-2, 3)]

    kaisu = -1
    while masu[D[0]][D[1]] == -1 and len(next) != 0:
        kaisu += 1
        que = deque(next)
        next = set()
        while que:
            now = que.popleft()
            if moverange(*now):
                masu[now[0]][now[1]] = kaisu
            func(now, up, kaisu)
            func(now, down, kaisu)
            func(now, right, kaisu)
            func(now, left, kaisu)

            for canmove in make_lst(*now):
                if moverange(*canmove):
                    next.add(tuple(canmove))
    ans = masu[D[0]][D[1]]
    print(ans)


if __name__ == '__main__':
    H, W = list(map(int, input().split()))
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))
    S = []
    for _ in range(H):
        S.append(input())
    main(H, W, C, D, S)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch,cw]]
    used_map = np.full((h,w),-1,dtype=np.int64)

    #move walk
    while used_map[dh][dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,th,tw = dot[0],dot[1],dot[2]
        if used_map[th][tw] > -1 and used_map[th][tw] <= tl:
            continue
        used_map[th][tw] = tl

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(th+ x < 0 or tw+y < 0 or th+x >= h or tw+y >= w):
                    if used_map[th+x][tw+y] == -1 and road_map[th+x][tw+y] == False:
                        if x == y == 0:
                            continue
                        if abs(x)+abs(y) <= 1:
                            heapq.heappush(queue,[tl,th+x,tw+y])
                        else:
                            heapq.heappush(queue,[tl+1,th+x,tw+y])

    print(used_map[dh,dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch,cw]]
    used_map = np.full((h,w),-1,dtype=np.int64)

    #move walk
    while used_map[dh][dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
            continue
        used_map[dot[1]][dot[2]] = dot[0]

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(dot[1]+ x < 0 or dot[2]+y < 0 or dot[1]+x >= h or dot[2]+y >= w):
                    if used_map[dot[1]+x][dot[2]+y] == -1 and road_map[dot[1]+x][dot[2]+y] == False:
                        if x == y == 0:
                            continue
                        if abs(x)+abs(y) <= 1:
                            heapq.heappush(queue,[dot[0],dot[1]+x,dot[2]+y])
                        else:
                            heapq.heappush(queue,[dot[0]+1,dot[1]+x,dot[2]+y])

    print(used_map[dh,dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch,cw]]
    used_map = np.full((h,w),-1,dtype=np.int64)

    #move walk
    while used_map[dh][dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
            continue
        used_map[dot[1]][dot[2]] = dot[0]

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(dot[1]+ x < 0 or dot[2]+y < 0 or dot[1]+x >= h or dot[2]+y >= w):
                    if used_map[dot[1]+x][dot[2]+y] == -1 and road_map[dot[1]+x][dot[2]+y] == False:
                        if abs(x)+abs(y) <= 1:
                            heapq.heappush(queue,[dot[0],dot[1]+x,dot[2]+y])
                        else:
                            heapq.heappush(queue,[dot[0]+1,dot[1]+x,dot[2]+y])

    print(used_map[dh,dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch,cw]]
    used_map = np.full((h,w),-1,dtype=np.int64)

    #move walk
    while used_map[dh][dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        if dot[1] < 0 or dot[2] < 0 or dot[1] >= h or dot[2] >= w:
            continue
        if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
            continue
        if road_map[dot[1]][dot[2]] == True:
            continue
        used_map[dot[1]][dot[2]] = dot[0]

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(dot[1]+ x < 0 or dot[2]+y < 0 or dot[1]+x >= h or dot[2]+y >= w):
                    if used_map[dot[1]+x][dot[2]+y] == -1 and road_map[dot[1]+x][dot[2]+y] == False:
                        if abs(x)+abs(y) <= 1:
                            heapq.heappush(queue,[dot[0],dot[1]+x,dot[2]+y])
                        else:
                            heapq.heappush(queue,[dot[0]+1,dot[1]+x,dot[2]+y])

    print(used_map[dh,dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
# 縦(H)x横(W)
H, W = map(int, input().split())
# 魔法使いの座標
CH, CW = map(int, input().split())
# ゴール
DH, DW = map(int, input().split())
# マップ
S = [list(input()) for _ in range(H)]
# 移動Aの動き方
move_a = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 移動Bの動き方
move_b = [(x, y) for x in range(-2, 3)
          for y in range(-2, 3) if (x, y) not in move_a + [(0, 0)]]

INF = 10 ** 10
# 各マスへの移動コスト
path = [[INF] * W for _ in range(H)]

q = deque()
path[CH-1][CW-1] = 0
q.append((CH-1, CW-1, 0))

while q:

    x, y, s = q.popleft()

    # 移動Aについて
    for dx, dy in move_a:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))

# 移動Bについて
    for dx, dy in move_b:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and path[nx][ny] > s+1:
            path[nx][ny] = s+1
            q.append((nx, ny, s+1))


print(path[DH-1][DW-1]) if path[DH-1][DW-1] < INF else print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
# 縦(H)x横(W)
H, W = map(int, input().split())
# 魔法使いの座標
CH, CW = map(int, input().split())
# ゴール
DH, DW = map(int, input().split())
# マップ
S = [list(input()) for _ in range(H)]
# 移動Aの動き方
move_a = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 移動Bの動き方
move_b = [(x, y) for x in range(-2, 3)
          for y in range(-2, 3) if (x, y) not in move_a + [(0, 0)]]

INF = 10 ** 10

# 各マスへの移動コスト
path = [[INF] * W for _ in range(H)]

q = deque()
path[CH-1][CW-1] = 0
q.append((CH-1, CW-1, 0))

while q:

    x, y, s = q.popleft()

    # 移動Aについて
    for dx, dy in move_a:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))

    # 移動Bについて
        for dx, dy in move_b:
            nx = x + dx
            ny = y + dy

            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and path[nx][ny] > s+1:
                path[nx][ny] = s+1
                q.append((nx, ny, s+1))


print(path[DH-1][DW-1]) if path[DH-1][DW-1] < INF else print(-1)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
# 縦(H)x横(W)
H, W = map(int, input().split())
# 魔法使いの座標
CH, CW = map(int, input().split())
# ゴール
DH, DW = map(int, input().split())
# マップ
S = [list(input()) for _ in range(H)]
# 移動Aの動き方
move_a = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 移動Bの動き方
move_b = [(x, y) for x in range(-2, 3)
          for y in range(-2, 3) if (x, y) not in move_a + [(0, 0)]]

# 各マスへの移動コスト
path = [[10**10] * W for _ in range(H)]

q = deque()
path[CH-1][CW-1] = 0
q.append((CH-1, CW-1, 0))

while q:

    x, y, s = q.popleft()

    # 移動Aについて
    for dx, dy in move_a:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))

    # 移動Bについて
        for dx, dy in move_b:
            nx = x + dx
            ny = y + dy

            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and path[nx][ny] > s+1:
                path[nx][ny] = s+1
                q.append((nx, ny, s+1))


print(path[DH-1][DW-1]) if path[DH-1][DW-1] < 10 ** 10 else print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch,cw]]
    used_map = np.full((h,w),-1,dtype=np.int64)

    layer_set = set()
    layer_set.add((ch,cw))
    loop = 0
    while used_map[dh][dw] == -1 and len(queue) != 0:
        #move walk
        while len(queue) != 0:
            dot = heapq.heappop(queue)
            if dot[1] < 0 or dot[2] < 0 or dot[1] >= h or dot[2] >= w:
                continue
            if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
                continue
            if road_map[dot[1]][dot[2]] == True:
                continue
            used_map[dot[1]][dot[2]] = dot[0]
            layer_set.add((dot[1],dot[2]))

            if not (dot[2] - 1 < 0):
                heapq.heappush(queue,[dot[0],dot[1],dot[2]-1])
            if not (dot[2] + 1 >= w):
                heapq.heappush(queue,[dot[0],dot[1],dot[2]+1])
            if not (dot[1]+1 >= h):
                heapq.heappush(queue,[dot[0],dot[1]+1,dot[2]])
            if not (dot[1]-1 < 0):
                heapq.heappush(queue,[dot[0],dot[1]-1,dot[2]])

        for s in layer_set:
            for x in range(-2,3,1):
                for y in range(-2,3,1):
                    if not(s[0]+ x < 0 or s[1]+y < 0 or s[0]+x >= h or s[1]+y >= w):
                        if used_map[s[0]+x][s[1]+y] == -1 and road_map[s[0]+x][s[1]+y] == False:
                            heapq.heappush(queue,[loop+1,s[0]+x,s[1]+y])
            
        loop+=1

    print(used_map[dh,dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)

Submission status: Time Limit Exceeded

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

def main():
    h, w = map(int, input().split())
    ch,cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ls = [input() for _ in range(h)]

    widou = []
    for i in range(-2,3):
        for j in range(-2, 3):
            widou.append((i, j))
    widou.remove((0,0))
    widou.remove((1,0))
    widou.remove((0,1))
    widou.remove((-1,0))
    widou.remove((0,-1))

    start = (ch-1, cw-1)
    goal = (dh-1, dw-1)

    explored = set()
    tempexplored = set()

    ytemp= deque()
    ytemp.append(start)

    wap = 0

    while ytemp:
        now = ytemp.popleft()

        if now == goal:
            print(wap)
            exit(0)

        x = now[0]
        y = now[1]

        explored.add((x, y))
        tempexplored.add((x, y))

        idou = [(1,0), (0,1), (0,-1), (-1,0)]
        for i, j in idou:
            a = x + i
            b = y + j
            if 0 <= a < h and 0 <= b < w:
                if ls[a][b] == '.':
                    if (a, b) not in explored:
                        ytemp.append((a,b))
                        explored.add((a,b))
                        tempexplored.add((a,b))

        if len(ytemp) ==0:
            wap += 1
            tempx = set()
            for s,t in tempexplored:
                for i, j in widou:
                    a = s + i
                    b = t + j
                    if 0 <= a < h and 0 <= b < w:
                        if ls[a][b] == '.':
                            if (a, b) not in explored:
                                ytemp.append((a, b))
                                explored.add((a, b))
                                tempx = set()
            tempexplored = tempx
    print('-1')
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch,cw = map(int, input().split())
dh, dw = map(int, input().split())
ls = [input() for _ in range(h)]


widou = []
for i in range(-2,3):
    for j in range(-2, 3):
        widou.append((i, j))
widou.remove((0,0))
widou.remove((1,0))
widou.remove((0,1))
widou.remove((-1,0))
widou.remove((0,-1))


start = (ch-1, cw-1)
goal = (dh-1, dw-1)

explored = set()
tempexplored = set()

ytemp= deque()
ytemp.append(start)

wap = 0

while ytemp:
    now = ytemp.popleft()

    if now == goal:
        print(wap)
        exit(0)

    x = now[0]
    y = now[1]

    explored.add((x, y))
    tempexplored.add((x, y))

    idou = [(1,0), (0,1), (0,-1), (-1,0)]
    for i, j in idou:
        a = x + i
        b = y + j
        if 0 <= a < h and 0 <= b < w:
            if ls[a][b] == '.':
                if (a, b) not in explored:
                    ytemp.append((a,b))
                    explored.add((a,b))
                    tempexplored.add((a,b))

    if len(ytemp) ==0:
        wap += 1
        tempx = set()
        for s,t in tempexplored:
            for i, j in widou:
                a = s + i
                b = t + j
                if 0 <= a < h and 0 <= b < w:
                    if ls[a][b] == '.':
                        if (a, b) not in explored:
                            ytemp.append((a, b))
                            explored.add((a, b))
                            tempx = set()
        tempexplored = tempx
print('-1')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C = tuple(map(lambda a: int(a) - 1, input().split()))
D = tuple(map(lambda a: int(a) - 1, input().split()))
S = [input() for _ in range(H)]
INF = 10**18

def cord(h, w):
    return h * W + w

minDist = [INF] * (H * W + 10)
que = deque([(C, 0)])
minDist[cord(*C)] = 0

while que:
    (h, w), dist = que.popleft()

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            toH, toW = h + dh, w + dw
            if not (0 <= toH < H and 0 <= toW < W) or (h, w) == (toH, toW):
                continue
            if S[toH][toW] == '#':
                continue

            d = 0 if (abs(dh) + abs(dw) <= 1) else 1
            if minDist[cord(toH, toW)] > dist + d:
                minDist[cord(toH, toW)] = dist + d
                if d == 0: que.appendleft(((toH, toW), dist + d))
                else: que.append(((toH, toW), dist + d))

print(minDist[cord(*D)] if minDist[cord(*D)] < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
INF = 1e7

H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]

D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, sx, sy)]
heapify(PQ)
while PQ: # PQに候補がある限り
    _, ux, uy = heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heappush(PQ, (D[xx][yy], xx, yy))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
INF = 1e7

H,W=map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

S = [input() for _ in range(H)]

D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
def dijkstra(sx, sy):
    # Color = [[0]*(W) for _ in range(H)] # 0: 未訪問 1: Seen 2: Visited
    # P = [None]*N #親

    D[sx][sy] = 0
    # P[s] = None
    # PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。
    PQ = [(0, sx, sy)]
    heapify(PQ)
    while PQ: # PQに候補がある限り
        min_cost, ux, uy = heappop(PQ) # 最小コストなノードu
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                xx, yy = ux+dx, uy+dy
                if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                    is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                    # neighborでなければコストが1増える
                    if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                        D[xx][yy] = D[ux][uy] + is_not_neighbor
                        heappush(PQ, (D[xx][yy], xx, yy))
    

dijkstra(ch-1, cw-1)
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
INF = 1e10

H,W=map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

S = [input() for _ in range(H)]

D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
def dijkstra(sx, sy):
    # Color = [[0]*(W) for _ in range(H)] # 0: 未訪問 1: Seen 2: Visited
    # P = [None]*N #親

    D[sx][sy] = 0
    # P[s] = None
    # PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。
    PQ = [(0, sx, sy)]
    heapify(PQ)
    while PQ: # PQに候補がある限り
        min_cost, ux, uy = heappop(PQ) # 最小コストなノードu
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                xx, yy = ux+dx, uy+dy
                if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                    is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                    # neighborでなければコストが1増える
                    if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                        D[xx][yy] = D[ux][uy] + is_not_neighbor
                        heappush(PQ, (D[xx][yy], xx, yy))
    

dijkstra(ch-1, cw-1)
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])