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:
import sys
from heapq import *

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

ans=-1
hp=[(0,si,sj)]
dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='#':
                continue
            if abs(di)+abs(dj)==1:
                nk=k
            else:
                nk=k+1
            if nk>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            heappush(hp,(nk,ni,nj))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

    from builtins import max, min, range

    INF = 10 ** 6

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    warp_count = 0
    warpq = []
    while q:
        while q:
            warpq.append(q[0])
            h, w = q.popleft()
            if h - 1 >= 0 and t[h - 1][w] > warp_count:
                q.append((h - 1, w))
                t[h - 1][w] = warp_count
            if h + 1 < H and t[h + 1][w] > warp_count:
                q.append((h + 1, w))
                t[h + 1][w] = warp_count
            if w - 1 >= 0 and t[h][w - 1] > warp_count:
                q.append((h, w - 1))
                t[h][w - 1] = warp_count
            if w + 1 < W and t[h][w + 1] > warp_count:
                q.append((h, w + 1))
                t[h][w + 1] = warp_count

        if t[Dh][Dw] != INF:
            break

        warp_count += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] > warp_count:
                        ti[j] = warp_count
                        q.append((i, j))
        warpq.clear()

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh, dw = map(int, input().split())
    dh -= 1
    dw -= 1
    maze = [input() for i in range(h)]
    visited = [[-1]*w for j in range(h)]
    
    def maze_solver(maze, visited, sy, sx, gy, gx):
        mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        q = deque([[sy, sx]])
        visited[sy][sx] = 0 
        _yx = list()
        _yx.append([sy, sx])
        while q:
            y, x = q.popleft()
            if y == gy and x == gx:
                ans = visited[y][x]
                _yx = list(map(list, set(map(tuple, _yx))))
                return ans, visited, _yx
            for i, j in mv:
                if (0 <= y + i < h) and (0 <= x + j < w):  
                    ny = y+i
                    nx = x+j
                    if visited[ny][nx] != -1:
                        continue
                    if maze[ny][nx] == '.':
                        visited[ny][nx] = visited[y][x] + 1 
                        q.append([ny, nx])
                        _yx.append([ny, nx])
                else:
                    continue
        ans = -1
        _yx = list(map(list, set(map(tuple, _yx))))
        return ans, visited, _yx

    def telepo(maze, visited, _yx, h, w):
        n_yx = list()
        for y, x in _yx:
            for ny in range(-2, 3):
                for nx in range(-2, 3):
                    if 0 <= y+ny < h and \
                        0 <= x+nx < w and \
                        visited[y+ny][x+nx] == -1 and \
                        maze[y+ny][x+nx] != '#': 
                        n_yx.append([y+ny, x+nx])
        n_yx_s = list(map(list, set(map(tuple, n_yx))))
        return n_yx_s

    telepo_cnt = 0
    ans, _visited, _yx = maze_solver(maze, visited, ch, cw, dh, dw)
    if ans != -1:
        print(telepo_cnt)
        exit()
    else:
        p = list()
        q = deque([telepo(maze, visited, _yx, h, w)])
        while len(q[0]) > 0:
            # n_yx_s = telepo(maze, _visited, _yx, h, w)
            p = list()
            n_yx_s = q.popleft()
            telepo_cnt += 1
            for nyx in n_yx_s:
                ans, _visted, _yx= maze_solver(maze, _visited, nyx[0], nyx[1], dh, dw)
                if ans != -1:
                    print(telepo_cnt)
                    exit()
                else:
                    for i in telepo(maze, visited, _yx, h, w):
                        p.append(i)
                        # print('p', p)
                        p = list(map(list, set(map(tuple, p))))
                        # print('p#', p)
            q.append(p) 
        print(-1)
                        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh, dw = map(int, input().split())
    dh -= 1
    dw -= 1
    maze = [input() for i in range(h)]
    visited = [[-1]*w for j in range(h)]
    
    def maze_solver(maze, visited, sy, sx, gy, gx):
        mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        q = deque([[sy, sx]])
        visited[sy][sx] = 0 
        _yx = list()
        _yx.append([sy, sx])
        while q:
            y, x = q.popleft()
            if y == gy and x == gx:
                ans = visited[y][x]
                _yx = list(map(list, set(map(tuple, _yx))))
                return ans, visited, _yx
            for i, j in mv:
                if (0 <= y + i < h) and (0 <= x + j < w):  
                    ny = y+i
                    nx = x+j
                    if visited[ny][nx] != -1:
                        continue
                    if maze[ny][nx] == '.':
                        visited[ny][nx] = visited[y][x] + 1 
                        q.append([ny, nx])
                        _yx.append([ny, nx])
                else:
                    continue
        ans = -1
        _yx = list(map(list, set(map(tuple, _yx))))
        return ans, visited, _yx

    def telepo(maze, visited, _yx, h, w):
        n_yx = list()
        for y, x in _yx:
            for ny in range(-2, 3):
                for nx in range(-2, 3):
                    if 0 <= y+ny < h and \
                        0 <= x+nx < w and \
                        visited[y+ny][x+nx] == -1 and \
                        maze[y+ny][x+nx] != '#': 
                        n_yx.append([y+ny, x+nx])
        n_yx_s = list(map(list, set(map(tuple, n_yx))))
        return n_yx_s

    telepo_cnt = 0
    ans, _visited, _yx = maze_solver(maze, visited, ch, cw, dh, dw)
    if ans != -1:
        print(telepo_cnt)
        exit()
    else:
        q = deque([telepo(maze, visited, _yx, h, w)])
        while len(q[0]) > 0:
            # n_yx_s = telepo(maze, _visited, _yx, h, w)
            p = list()
            n_yx_s = q.popleft()
            telepo_cnt += 1
            for nyx in n_yx_s:
                ans, _visted, _yx= maze_solver(maze, _visited, nyx[0], nyx[1], dh, dw)
                if ans != -1:
                    print(telepo_cnt)
                    exit()
                else:
                    for i in telepo(maze, visited, _yx, h, w):
                        p.append(i)
                        # print('p', p)
                        # p = list(map(list, set(map(tuple, p))))
                        # print('p#', p)
            q.append(p) 
        print(-1)
    
                        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for _ in range(H):
        S.append([s for s in input()])

    # 座標と配列番号を揃える
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    # 上下左右の移動で楽する工夫
    walk = [(-1,0), (0,-1), (1,0), (0,1)]
    warp = [(-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)]

    # コスト格納用の盤面
    INF = 10**9
    dist = [[INF] * W for _ in range(H)]
    dist[Ch][Cw] = -1

    # dequeの定義、(h座標, w座標, コスト)のタプルを格納する
    deq = deque()
    deq.append((Ch, Cw, 0))

    while len(deq) > 0:
        (h, w, d) = deq.popleft()
        # 探索済みマスかどうか
        if dist[h][w] < d and dist[h][w] != -1:
            continue
        # コスト0の移動を検証
        for (dh, dw) in walk:
            nh = h + dh
            nw = w + dw
            # 盤面外かどうか
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            # 道があるかどうか
            if S[nh][nw] == '#':
                continue
            # 探索済みかどうか
            if dist[nh][nw] <= d:
                continue
            dist[nh][nw] = d
            deq.appendleft((nh, nw, d))
        # コスト1の移動を検証
        for (dh, dw) in warp:
            nh = h + dh
            nw = w + dw
            # 盤面外かどうか
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            # 道があるかどうか
            if S[nh][nw] == '#':
                continue
            # 探索済みかどうか
            if dist[nh][nw] <= d+1:
                continue
            dist[nh][nw] = d+1
            deq.append((nh, nw, d+1))
    ans = dist[Dh][Dw]
    if ans == INF:
        ans = -1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for _ in range(H):
        S.append([s for s in input()])

    # 座標と配列番号を揃える
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    # 上下左右の移動で楽する工夫
    walk = [(-1,0), (0,-1), (1,0), (0,1)]
    warp = [(-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)]

    # コスト格納用の盤面
    INF = 10**9
    dist = [[INF] * W for _ in range(H)]
    # dist[Ch][Cw] = 0

    # dequeの定義、(h座標, w座標, コスト)のタプルを格納する
    deq = deque()
    deq.append((Ch, Cw, 0))

    while len(deq) > 0:
        (h, w, d) = deq.popleft()
        # 探索済みマスかどうか
        if dist[h][w] < d:
            continue
        # コスト0の移動を検証
        for (dh, dw) in walk:
            nh = h + dh
            nw = w + dw
            # 盤面外かどうか
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            # 道があるかどうか
            if S[nh][nw] == '#':
                continue
            # 探索済みかどうか
            if dist[nh][nw] <= d:
                continue
            dist[nh][nw] = d
            deq.appendleft((nh, nw, d))
        # コスト1の移動を検証
        for (dh, dw) in warp:
            nh = h + dh
            nw = w + dw
            # 盤面外かどうか
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            # 道があるかどうか
            if S[nh][nw] == '#':
                continue
            # 探索済みかどうか
            if dist[nh][nw] <= d+1:
                continue
            dist[nh][nw] = d+1
            deq.append((nh, nw, d+1))
    ans = dist[Dh][Dw]
    if ans == INF:
        ans = -1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for _ in range(H):
        S.append([s for s in input()])

    # 座標と配列番号を揃える
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    # 上下左右の移動で楽する工夫
    walk = [(-1,0), (0,-1), (1,0), (0,1)]
    warp = [(-2,-2), (-2,-1), (-2,0), (-2,1), (-2,2),
        (-1,-2), (-1,-1), (-1,1), (-1,2),
        (0,-2), (0,0), (0,2),
        (1,-2), (1,-1), (1,1), (1,2),
        (2,-2), (2,-1), (2,0), (2,1), (2,2)]

    # コスト格納用の盤面
    INF = 10**9
    dist = [[INF] * W for _ in range(H)]
    # dist[Ch][Cw] = 0

    # dequeの定義、(h座標, w座標, コスト)のタプルを格納する
    deq = deque()
    deq.append((Ch, Cw, 0))

    while len(deq) > 0:
        (h, w, d) = deq.popleft()
        # 探索済みマスかどうか
        if dist[h][w] < d:
            continue
        # コスト0の移動を検証
        for (dh, dw) in walk:
            nh = h + dh
            nw = w + dw
            # 盤面外かどうか
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            # 道があるかどうか
            if S[nh][nw] == '#':
                continue
            # 探索済みかどうか
            if dist[nh][nw] <= d:
                continue
            dist[nh][nw] = d
            deq.appendleft((nh, nw, d))
        # コスト1の移動を検証
        for (dh, dw) in warp:
            nh = h + dh
            nw = w + dw
            # 盤面外かどうか
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            # 道があるかどうか
            if S[nh][nw] == '#':
                continue
            # 探索済みかどうか
            if dist[nh][nw] <= d+1:
                continue
            dist[nh][nw] = d+1
            deq.append((nh, nw, d+1))
    ans = dist[Dh][Dw]
    if ans == INF:
        ans = -1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for _ in range(H):
        S.append([s for s in input()])

    # 座標と配列番号を揃える
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    # 上下左右の移動で楽する工夫
    dh = [-1, 0, 1, 0]
    dw = [0, -1, 0, 1]

    # コスト格納用の盤面
    INF = 10**9
    dist = [[INF] * W for _ in range(H)]
    dist[Ch][Cw] = 0

    # dequeの定義、(h座標, w座標, コスト)のタプルを格納する
    deq = deque()
    deq.append((Ch, Cw, 0))

    while len(deq) > 0:
        (h, w, d) = deq.popleft()
        # 探索済みマスかどうか
        if dist[h][w] < d:
            continue
        # コスト0の移動を検証
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            # 盤面外かどうか
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            # 道があるかどうか
            if S[nh][nw] == '#':
                continue
            # 探索済みかどうか
            if dist[nh][nw] <= d:
                continue
            dist[nh][nw] = d
            deq.appendleft((nh, nw, d))
        # コスト1の移動を検証
        for nh in range(h-2, h+3):
            for nw in range(w-2, w+3):
                # 盤面外かどうか
                if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                    continue
                # 道があるかどうか
                if S[nh][nw] == '#':
                    continue
                # 探索済みかどうか
                if dist[nh][nw] <= d+1:
                    continue
                dist[nh][nw] = d+1
                deq.append((nh, nw, d+1))
    ans = dist[Dh][Dw]
    if ans == INF:
        ans = -1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def input():return sys.stdin.readline().strip()

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for _ in range(H):
        S.append([s for s in input()])

    # 座標と配列番号を揃える
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    # 上下左右の移動で楽する工夫
    dh = [-1, 0, 1, 0]
    dw = [0, -1, 0, 1]

    # コスト格納用の盤面
    INF = 10**9
    dist = [[INF] * W for _ in range(H)]
    dist[Ch][Cw] = 0

    # dequeの定義、(h座標, w座標, コスト)のタプルを格納する
    deq = deque()
    deq.append((Ch, Cw, 0))

    while len(deq) > 0:
        (h, w, d) = deq.popleft()
        # 探索済みマスかどうか
        if dist[h][w] < d:
            continue
        # コスト0の移動を検証
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            # 盤面外かどうか
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            # 道があるかどうか
            if S[nh][nw] == '#':
                continue
            # 探索済みかどうか
            if dist[nh][nw] <= d:
                continue
            dist[nh][nw] = d
            deq.appendleft((nh, nw, d))
        # コスト1の移動を検証
        for nh in range(h-2, h+3):
            for nw in range(w-2, w+3):
                # 盤面外かどうか
                if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                    continue
                # 道があるかどうか
                if S[nh][nw] == '#':
                    continue
                # 探索済みかどうか
                if dist[nh][nw] <= d+1:
                    continue
                dist[nh][nw] = d+1
                deq.append((nh, nw, d+1))
    ans = dist[Dh][Dw]
    if ans == INF:
        ans = -1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def input():return sys.stdin.readline().strip()

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for _ in range(H):
        S.append([s for s in input()])

    # 座標と配列番号を揃える
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    # 上下左右の移動で楽する工夫
    dh = [-1, 0, 1, 0]
    dw = [0, -1, 0, 1]

    # コスト格納用の盤面
    INF = 10**9
    dist = [[INF] * W for _ in range(H)]
    dist[Ch][Cw] = 0

    # dequeの定義、(h座標, w座標, コスト)のタプルを格納する
    deq = deque()
    deq.append((Ch, Cw, 0))

    while len(deq) > 0:
        (h, w, d) = deq.pop()
        # 探索済みマスかどうか
        if dist[h][w] < d:
            continue
        # コスト0の移動を検証
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            # 盤面外かどうか
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            # 道があるかどうか
            if S[nh][nw] == '#':
                continue
            # 探索済みかどうか
            if dist[nh][nw] <= d:
                continue
            dist[nh][nw] = d
            deq.appendleft((nh, nw, d))
        # コスト1の移動を検証
        for nh in range(h-2, h+3):
            for nw in range(w-2, w+3):
                # 盤面外かどうか
                if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                    continue
                # 道があるかどうか
                if S[nh][nw] == '#':
                    continue
                # 探索済みかどうか
                if dist[nh][nw] <= d+1:
                    continue
                dist[nh][nw] = d+1
                deq.append((nh, nw, d+1))
    ans = dist[Dh][Dw]
    if ans == INF:
        ans = -1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import stdin

def resolve():
    H, W = map(int, stdin.readline().split())
    Ch, Cw = map(int, stdin.readline().split())
    Dh, Dw = map(int, stdin.readline().split())
    S = []
    for _ in range(H):
        S.append([s for s in stdin.readline()])

    # 座標と配列番号を揃える
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    # 上下左右の移動で楽する工夫
    dh = [-1, 0, 1, 0]
    dw = [0, -1, 0, 1]

    # コスト格納用の盤面
    INF = 10**9
    dist = [[INF] * W for _ in range(H)]
    dist[Ch][Cw] = 0

    # dequeの定義、(h座標, w座標, コスト)のタプルを格納する
    deq = deque()
    deq.append((Ch, Cw, 0))

    while len(deq) > 0:
        (h, w, d) = deq.pop()
        # 探索済みマスかどうか
        if dist[h][w] < d:
            continue
        # コスト0の移動を検証
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            # 盤面外かどうか
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            # 道があるかどうか
            if S[nh][nw] == '#':
                continue
            # 探索済みかどうか
            if dist[nh][nw] <= d:
                continue
            dist[nh][nw] = d
            deq.appendleft((nh, nw, d))
        # コスト1の移動を検証
        for nh in range(h-2, h+3):
            for nw in range(w-2, w+3):
                # 盤面外かどうか
                if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                    continue
                # 道があるかどうか
                if S[nh][nw] == '#':
                    continue
                # 探索済みかどうか
                if dist[nh][nw] <= d+1:
                    continue
                dist[nh][nw] = d+1
                deq.append((nh, nw, d+1))
    ans = dist[Dh][Dw]
    if ans == INF:
        ans = -1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for _ in range(H):
        S.append([s for s in input()])

    # 座標と配列番号を揃える
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    # 上下左右の移動で楽する工夫
    dh = [-1, 0, 1, 0]
    dw = [0, -1, 0, 1]

    # コスト格納用の盤面
    INF = int(1e9)
    dist = [[INF] * W for _ in range(H)]
    dist[Ch][Cw] = 0

    # dequeの定義、(h座標, w座標, コスト)のタプルを格納する
    deq = deque()
    deq.append((Ch, Cw, 0))

    while len(deq) > 0:
        (h, w, d) = deq.pop()
        # 探索済みマスかどうか
        if dist[h][w] < d:
            continue
        # コスト0の移動を検証
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            # 盤面外かどうか
            if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                continue
            # 道があるかどうか
            if S[nh][nw] == '#':
                continue
            # 探索済みかどうか
            if dist[nh][nw] <= d:
                continue
            dist[nh][nw] = d
            deq.appendleft((nh, nw, d))
        # コスト1の移動を検証
        for nh in range(h-2, h+3):
            for nw in range(w-2, w+3):
                # 盤面外かどうか
                if (nh < 0) or (nw < 0) or (nh >= H) or (nw >= W):
                    continue
                # 道があるかどうか
                if S[nh][nw] == '#':
                    continue
                # 探索済みかどうか
                if dist[nh][nw] <= d+1:
                    continue
                dist[nh][nw] = d+1
                deq.append((nh, nw, d+1))
    ans = dist[Dh][Dw]
    if ans == INF:
        ans = -1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
ch,cw=map(lambda x: int(x)-1,input().split())
dh,dw=map(lambda x: int(x)-1,input().split())
s=[input() for _ in range(h)]

isVisited = [[False for _ in range(w)]for __ in range(h) ]
check = [[False for _ in range(w)]for __ in range(h) ]
isVisited[ch][cw] = True

dx =[1,0,-1,0]
dy = [0,1,0,-1]
ans = 0

from heapq import heappush,heappop

li=[]
heappush(li,[0,ch,cw])

while li:
    cost,nowh,noww = heappop(li)
    if check[nowh][noww]:continue
    check[nowh][noww] = True
    isVisited[nowh][noww] = True
    if nowh == dh and noww == dw:
        print(cost)
        exit()
    for i in range(4):
        neh, new = nowh+dx[i], noww+ dy[i]
        if neh <0 or new < 0 or h<= neh or w<=new:continue
        if isVisited[neh][new]:continue
        if check[neh][new]:continue
        if s[neh][new] == '#': continue
        isVisited[neh][new] = True
        heappush(li,[cost,neh,new])
    

    for i in range(-2,3):
        for j in range(-2,3):
            neh,new = nowh + i,noww + j
            if neh <0 or new < 0 or h<= neh or w<=new:continue
            if s[neh][new] == '#': continue
            if check[neh][new]:continue
            if isVisited[neh][new]:continue
            heappush(li,[cost+1,neh, new])



print(-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
ch,cw=map(lambda x: int(x)-1,input().split())
dh,dw=map(lambda x: int(x)-1,input().split())
s=[input() for _ in range(h)]

isVisited = [[False for _ in range(w)]for __ in range(h) ]
check = [[False for _ in range(w)]for __ in range(h) ]
isVisited[ch][cw] = True

dx =[1,0,-1,0]
dy = [0,1,0,-1]
ans = 0

from heapq import heappush,heappop

li=[]
heappush(li,[0,ch,cw])

while li:
    cost,nowh,noww = heappop(li)
    if check[nowh][noww]:continue
    check[nowh][noww] = True
    isVisited[nowh][noww] = True
    if nowh == dh and noww == dw:
        print(cost)
        exit()
    for i in range(4):
        neh, new = nowh+dx[i], noww+ dy[i]
        if neh <0 or new < 0 or h<= neh or w<=new:continue
        if isVisited[neh][new]:continue
        if s[neh][new] == '#': continue
        isVisited[neh][new] = True
        heappush(li,[cost,neh,new])
    

    for i in range(-2,3):
        for j in range(-2,3):
            neh,new = nowh + i,noww + j
            if neh <0 or new < 0 or h<= neh or w<=new:continue
            if s[neh][new] == '#': continue
            if isVisited[neh][new]:continue
            heappush(li,[cost+1,neh, new])



print(-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
ch,cw=map(lambda x: int(x)-1,input().split())
dh,dw=map(lambda x: int(x)-1,input().split())
s=[input() for _ in range(h)]

isVisited = [[False for _ in range(w)]for __ in range(h) ]
isVisited[ch][cw] = True

dx =[1,0,-1,0]
dy = [0,1,0,-1]
ans = 0

from heapq import heappush,heappop

li=[]
heappush(li,[0,ch,cw])

while li:
    cost,nowh,noww = heappop(li)
    isVisited[nowh][noww] = True
    if nowh == dh and noww == dw:
        print(cost)
        exit()
    for i in range(4):
        neh, new = nowh+dx[i], noww+ dy[i]
        if neh <0 or new < 0 or h<= neh or w<=new:continue
        if isVisited[neh][new]:continue
        if s[neh][new] == '#': continue
        isVisited[neh][new] = True
        heappush(li,[cost,neh,new])
    

    for i in range(-2,3):
        for j in range(-2,3):
            neh,new = nowh + i,noww + j
            if neh <0 or new < 0 or h<= neh or w<=new:continue
            if s[neh][new] == '#': continue
            if isVisited[neh][new]:continue
            heappush(li,[cost+1,neh, new])



print(-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
ch,cw=map(lambda x: int(x)-1,input().split())
dh,dw=map(lambda x: int(x)-1,input().split())
s=[input() for _ in range(h)]

isVisited = [[False for _ in range(w)]for __ in range(h) ]
isVisited[ch][cw] = True

dx =[1,0,-1,0]
dy = [0,1,0,-1]
ans = 0

from heapq import heappush,heappop

li=[]
heappush(li,[0,ch,cw])

while li:
    cost,nowh,noww = heappop(li)
    if nowh == dh and noww == dw:
        print(cost)
        exit()
    for i in range(4):
        neh, new = nowh+dx[i], noww+ dy[i]
        if neh <0 or new < 0 or h<= neh or w<=new:continue
        if isVisited[neh][new]:continue
        if s[neh][new] == '#': continue
        isVisited[neh][new] = True
        heappush(li,[cost,neh,new])
    

    for i in range(-2,3):
        for j in range(-2,3):
            neh,new = nowh + i,noww + j
            if neh <0 or new < 0 or h<= neh or w<=new:continue
            if s[neh][new] == '#': continue
            if isVisited[neh][new]:continue
            heappush(li,[cost+1,neh, new])



print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

indice = lambda s: int(s)-1 

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

world = ''.join(input().strip() for _ in range(H))
available = {divmod(i, W) for i, p in enumerate(world) if p=='.'}

q = deque()
q.append((ch, cw, 0))
available.discard((ch, cw, 0))
# 01-BFS
res = -1
while q:
    h, w, dist = q.popleft()
    if h == dh and w == dw:
        res = dist
        break

    # 距離0の動き
    A_move = [(1, 0), (-1, 0), (0, 0), (0, 1), (0, -1)]
    for dx, dy in A_move:
        if (h+dx, w+dy) in available:
            available.discard((h+dx, w+dy)) # 距離が確定したマスは除く
            q.appendleft((h+dx, w+dy, dist))

    # 距離1の動き        
    B_move = [(dx, dy) for dx in (-2, -1, 0, 1, 2) for dy in (-2, -1, 0, 1, 2)]
    for dx, dy in B_move:
        if (h+dx, w+dy) in available:
            q.append((h+dx, w+dy, dist+1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import *

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]

big=10**9
A=[]
for row in sys.stdin:
    A.append([big if x=='.' else '#' for x in row])
A[si][sj]=0

ans=-1
hp=[(0,si,sj)]
dirs=[-2,-1,0,1,2]
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='#':
                continue
            if (abs(di)==1 and dj==0) or (di==0 and abs(dj)==1):
                nk=k
            else:
                nk=k+1
            if nk>=A[ni][nj]:
                continue
            A[ni][nj]=nk
            heappush(hp,(nk,ni,nj))

print(ans)