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 heapq import heapify, heappop, heappush, heappushpop
from collections import deque


INF = 1e7

class PriorityQueue:
    """
    優先度付きキューの
    """
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)
    
    def push(self, item):
        heappush(self.heap, item)
    
    def pop(self):
        return heappop(self.heap)
    
    def pushpop(self, item):
        return heappushpop(self.heap, item)
    
    def __call__(self):
        return self.heap
    
    def __len__(self):
        return len(self.heap)
    
    



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

    S = [["#"]*(W+2) for _ in range(H+2)]
    for i in range(1,1+H):
        tmp=list(input())
        for j in range(1,1+W):
            S[i][j]=tmp[j-1]

    idxs = []

    for row in range(1, H+1):
        for col in range(1, W+1):
            if S[row][col] == ".":
                idxs.append((row, col))

    dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    graph = {idx: deque() for idx in idxs}
    for x in range(1, H+1):
        for y in range(1, W+1):
            if S[x][y] == "#":
                continue
            idxs.append((x, y))
            for dx, dy in dxdy:
                if S[x+dx][y+dy] == ".":
                    graph[(x, y)].append((x+dx, y+dy, 0))
                    

    for idx in idxs:
        x = idx[0]
        y = idx[1]
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if x+dx<1 or x+dx>H or y+dy<1 or y+dy>W:
                    continue
                if S[x+dx][y+dy] == ".":
                    graph[idx].append((x+dx, y+dy, 1))

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

        D[sx][sy] = 0
        # P[s] = None
        PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。

        while PQ: # PQに候補がある限り

            min_cost, ux, uy = PQ.pop() # 最小コストなノードu

            Color[ux][uy] = 1 # uをVisitedに。

            if D[ux][uy] < min_cost:
                # 更新の必要なし.
                continue

            for adj_x, adj_y, adj_w in adj[(ux, uy)]:
                if not Color[adj_x][adj_y]: #訪問済みでないなら
                    if D[ux][uy] + adj_w < D[adj_x][adj_y]: #最小コストを更新できるなら、
                        D[adj_x][adj_y] = D[ux][uy] + adj_w
                        # P[adj_idx] = u
                        # PQに(隣接要素のコスト, 隣接要素の番号)を容れる
                        PQ.push((D[adj_x][adj_y], adj_x, adj_y))
                        
        
        return D
    D = dijkstra(graph, ch, cw)
    if D[dh][dw] == INF:
        print(-1)
    else:
        print(D[dh][dw])

main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max
import heapq

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    inf = 10**7
    dp = [[inf]*w for _ in range(h)]
    s = [list(input()) for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rx = (2, 1, 0, -1, -2)
    ry = (2, 1, 0, -1, -2)
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))
    while q:
        cnt = 0
        cost, px, py = heappop(q)
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or y >= w or x < 0 or y < 0 or s[x][y] == "#":
                continue
            cnt += 1
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        if cnt != 4:
            cost += 1
            for di in rx:
                x = px + di
                if x >= h or x < 0:
                    continue
                for dj in ry:
                    y = py + dj
                    if y >= w or y < 0 or s[x][y] == "#":
                        continue
                    if dp[x][y] > cost:
                        dp[x][y] = cost
                        heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    di, dj = D
    dist[di][dj] = 0
    q = deque([(di, dj, 0)])
    while q:
        i, j, d = q.popleft()
        if d > dist[i][j]: continue
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                if dist[ni][nj] > d:
                    dist[ni][nj] = d
                    q.append((ni, nj, d))
        for ni in range(i - 2, i + 2 + 1, 1):
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                    if dist[ni][nj] > d + 1:
                        dist[ni][nj] = d + 1
                        q.append((ni, nj, d + 1))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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 = [[c for c in input()] for _ in range(H)]


h = []
heapq.heappush(h, (0, Ch, Cw))

while len(h) != 0:
    d, nh, nw = heapq.heappop(h)
    if nh == Dh and nw == Dw:
        print(d)
        exit()

    for dh in [-2, -1, 0, 1, 2]:
        for dw in [-2, -1, 0, 1, 2]:
            if dh == 0 and dw == 0:
                continue
            newd = d + 1
            if abs(dh) + abs(dw) == 1:
                newd = d
            newh = nh + dh
            neww = nw + dw
            if 0 <= newh < H and 0 <= neww < W:
                if S[newh][neww] == ".":
                    S[newh][neww] = str(newd)
                    heapq.heappush(h, (newd, newh, neww))
                elif S[newh][neww] == "#":
                    continue
                else:
                    if int(S[newh][neww]) > newd:
                        S[newh][neww] = str(newd)
                        heapq.heappush(h, (newd, newh, neww))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
"""
dp[i][j] => マスi,jに到達するのに必要なワープ回数。
近隣25マスから
"""


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

    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 = [list(input()) for _ in range(H)]

    que = deque([(Ch,Cw,0)])
    adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
    while que:
        h,w,worp = que.popleft()
        if maze[h][w] == "#" or (maze[h][w]!="." and maze[h][w] <= worp):
            continue
        else:
            maze[h][w] = worp
            for a,b in adjecents:
                nxh,nxw = h+a,w+b
                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw]>worp):
                    que.append((nxh,nxw,worp))
                elif 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]=="#":
                    for i in range(-2,3,1):
                        for j in range(-2,3,1):
                            nxh,nxw = h+i,w+j
                            if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw]>worp+1):
                                que.append((nxh,nxw,worp+1))
    
    if maze[Dh][Dw] == "#" or maze[Dh][Dw] == ".":
        print(-1)
    else:
        print(maze[Dh][Dw])
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())

h,w=NM()
sh,sw=NM()
sh-=1
sw-=1
gh,gw=NM()
gh-=1
gw-=1
l=[[j for j in input()] for i in range(h)]
from heapq import *
def dijkstra(s,n,g):
    d = [float('inf') for i in range(n+1)]
    pq = []
    d[s]=0
    heappush(pq,(0,s))
    while pq:
        dist,u = heappop(pq)
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            heappush(pq,(d[v],v))
    return d[g]
edge=[[] for i in range(h*w)]

def v(i,j):
    return (j*h+i)
def f(i,j,x,y):
    if x>=h or y>=w or x<0 or y<0:
        return
    if l[x][y]==".":
        edge[v(i,j)].append((v(x,y),1))
        edge[v(x,y)].append((v(i,j),1))
for x in range(h*w):
        i=x%h
        j=x//h
        if l[i][j]=="#":
            continue
        if i<h-1:
            if l[i+1][j]==".":
                edge[v(i,j)].append((v(i+1,j),0))
                edge[v(i+1,j)].append((v(i,j),0))
        if j<w-1:
            if l[i][j+1]==".":
                edge[v(i,j)].append((v(i,j+1),0))
                edge[v(i,j+1)].append((v(i,j),0))
        f(i,j,i+1,j+1)
        f(i,j,i+2,j+1)
        f(i,j,i+2,j+2)
        f(i,j,i+1,j+2)
        f(i,j,i+2,j)
        f(i,j,i,j+2)
        
        f(i,j,i-1,j+1)
        f(i,j,i-2,j+1)
        f(i,j,i-2,j+2)
        f(i,j,i-1,j+2)


d=dijkstra(v(sh,sw),h*w,v(gh,gw))
if d==float("inf"):
    print(-1)
else:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy

input = sys.stdin.readline

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

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(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)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
q2 = deque([(ch-1, cw-1)])
q3 = deque([])
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))

    for i,j in q2:
        for ii,jj in d2:
            if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp+1
                    q.append((i+ii,j+jj))
                    q3.append((i+ii,j+jj))
    if not q:
        break
    tmp += 1
    q2 = copy.copy(q3)

print(v[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n , m = map(int, input().split())
ch , cw = map(int, input().split())
dh , dw = map(int, input().split())
maze = [['#','#']+list(input())+['#','#'] for i in range(n)]
maze = [['#']*(m+4)]+[['#']*(m+4)]+maze+[['#']*(m+4)]+[['#']*(m+4)]

step = [(0,1),(1,0),(-1,0),(0,-1)]
warp_u = [(-2,0)]
warp_d = [(2,0)]
warp_r = [(0,2)]
warp_l = [(0,-2)]
warp_ur = [(-1,1),(-2,1),(-2,2),(0,2),(-2,0),(-1,2)]
warp_dr = [(2,0),(2,1),(2,2),(1,1),(1,2),(0,2)]
warp_ul = [(-2,0),(-2,-1),(-2,-2),(-1,-1),(-1,-2),(0,-2)]
warp_dl = [(2,0),(2,-1),(2,-2),(1,-1),(1,-2),(0,-2)]



warp=0

v = [[-1]*(m+4) for i in range(n+4)]
d = deque()
d.append((ch+1,cw+1,0))
v[ch+1][cw+1]=0
while d:
    y,x,wa=d.popleft()
    for dy,dx in step:
        if maze[y+dy][x+dx]=='.' and (v[y+dy][x+dx]==-1 or v[y+dy][x+dx]>wa):
            v[y+dy][x+dx]=wa
            d.append((y+dy,x+dx,wa))
        elif maze[y+dy][x+dx]=='#' and dy>0 and maze[y][x+1]=='.' and maze[y][x-1]=='.':
            for dy2,dx2 in warp_d:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dy>0 and maze[y][x+1]=='#':
            for dy2,dx2 in warp_dr:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dy>0 and maze[y][x-1]=='#':
            for dy2,dx2 in warp_dl:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx>0 and maze[y+1][x]=='.' and maze[y-1][x]=='.':
            for dy2,dx2 in warp_r:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx>0 and maze[y+1][x]=='#':
            for dy2,dx2 in warp_dr:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx>0 and maze[y-1][x]=='#':
            for dy2,dx2 in warp_ur:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dy<0 and maze[y][x+1]=='.' and maze[y][x-1]=='.':
            for dy2,dx2 in warp_u:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dy<0 and maze[y][x+1]=='#':
            for dy2,dx2 in warp_ur:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dy<0 and maze[y][x-1]=='#':
            for dy2,dx2 in warp_ul:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx<0 and maze[y+1][x]=='.' and maze[y-1][x]=='.':
            for dy2,dx2 in warp_l:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx<0 and maze[y+1][x]=='#':
            for dy2,dx2 in warp_dl:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx<0 and maze[y-1][x]=='#':
            for dy2,dx2 in warp_ul:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
print(v[dh+1][dw+1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    CH, CW = [int(x) - 1 for x in input().split()]
    DH, DW = [int(x) - 1 for x in input().split()]
    S = [input().strip() for _ in range(H)]

    warp = ((-2, -2), (-2, -2), (-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))

    visited = [[float("inf")] * W for _ in range(H)]

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.popleft()
        cc = visited[cx][cy]

        # 隣接
        kabe_cnt = 0
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == ".":
                    if visited[nnx][nny] > cc:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc
                else:
                    kabe_cnt += 1

        # ワープ
        # if kabe_cnt > 0:
            for nx, ny in warp:
                nnx = cx + nx
                nny = cy + ny
                if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                    if S[nnx][nny] == "." and visited[nnx][nny] > cc + 1:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc + 1

    if visited[DH][DW] == float("inf"):
        print(-1)
    else:
        print(visited[DH][DW])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
S = [list(input()) for _ in range(H)]

cnt = 0
start = (c_h-1, c_w-1)
goal = (d_h-1, d_w-1)

def next_walk(pos):
  x, y = pos
  return (x-1, y), (x, y-1), (x+1, y), (x, y+1)
def next_jump(pos):
  x, y = pos
  return (x-2, y),(x-2, y-1),(x-2, y-2),(x-1, y-2),(x, y-2),(x+1, y-2),(x+2, y-2),(x+2, y-1),(x+2, y),(x+2, y+1),(x+2, y+2),(x+1, y+2),(x, y+2),(x-1, y+2),(x-2, y+2),(x-2, y+1)

past_pos = [start]
next_pos = [start]
jump_cnt = 0
goal_cnt = 0

def search(past_pos, next_pos, goal, jump_cnt, goal_cnt):
  jump_pos = []
  while next_pos:
    pos = next_pos.pop(0)
    if pos == goal:
      goal_cnt += 1
      # print('goal', jump_cnt)
      return jump_cnt
      break
    walk_pos = next_walk(pos)
    for walk in walk_pos:
      x, y = walk
      if x < 0 or x >= H or y < 0 or y >= W:
        continue
      else:
        if S[x][y] == '.' and (x, y) not in past_pos:
          past_pos.append((x, y))
          next_pos.append((x, y))
        elif S[x][y] == '#':
          if pos not in jump_pos:
            jump_pos.append(pos)
  if goal_cnt != 1:
    for jump in jump_pos:
      jump_pos2 = next_jump(jump)
      for pos2 in jump_pos2:
        x, y = pos2
        if x < 0 or x >= H or y < 0 or y >= W:
          continue
        elif S[x][y] == '.' and (x, y) not in past_pos:
          next_pos.append((x, y))
    if next_pos:
      jump_cnt += 1
      # print('jump', jump_cnt)
      return search(past_pos, next_pos, goal, jump_cnt, goal_cnt)
    else:
      return -1
  else:
    return -1

print(search(past_pos, next_pos, goal, jump_cnt, goal_cnt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections

H,W = list(map(int, input().split()))

Chw = list(map(int, input().split()))
Dhw = list(map(int, input().split()))

Ss = []
for _ in range(H):
    tmp = input()
    Ss.append(list(tmp))

mazeArray = np.zeros((H+6, W+6), dtype = 'int64')

for i in range(H+6):
    for j in range(W+6):
        if(i < 3 or i > H+2):
            mazeArray[i][j] = -1
        
        elif(j < 3 or j > W+2):
            mazeArray[i][j] = -1
        
        else:
            if(Ss[i - 3][j-3] == "#"):
                mazeArray[i][j] = -1
            else:
                mazeArray[i][j] = 100000

#前準備完了

H_que = collections.deque()
W_que = collections.deque()

H_que.append(Chw[0])
W_que.append(Chw[1])

mazeArray[Chw[0]+2][Chw[1]+2] = 0

#print(mazeArray)

for _ in range(2 * 10**5):
    H_iti = H_que.popleft() + 2
    W_iti = W_que.popleft() + 2

    #上移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti - 1][W_iti]):
        mazeArray[H_iti - 1][W_iti] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 3)
        W_que.append(W_iti - 2)

    elif(mazeArray[H_iti - 1][W_iti] == -1):
        for i in range(H_iti-2, H_iti):
            for j in range(W_iti -2, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)
                
    #下移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti + 1][W_iti]):
        mazeArray[H_iti + 1][W_iti] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 1)
        W_que.append(W_iti - 2)
        
    elif(mazeArray[H_iti+1][W_iti] == -1):
        for i in range(H_iti+1, H_iti+3):
            for j in range(W_iti -2, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #左移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti][W_iti - 1]):
        mazeArray[H_iti][W_iti - 1] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 2)
        W_que.append(W_iti - 3)

    elif(mazeArray[H_iti][W_iti-1] == -1):
        for i in range(H_iti-2, H_iti+3):
            for j in range(W_iti -2, W_iti):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #右移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti][W_iti + 1]):
        mazeArray[H_iti][W_iti + 1] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 2)
        W_que.append(W_iti - 1)

    elif(mazeArray[H_iti][W_iti-1] == -1):
        for i in range(H_iti-2, H_iti+3):
            for j in range(W_iti +1, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #移動Bパターン


    if(len(H_que) == 0):
        break

#print(mazeArray)

if(mazeArray[Dhw[0]+2][Dhw[1]+2] == 100000):
    print(-1)

else:
    print(mazeArray[Dhw[0]+2][Dhw[1]+2])

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys


def input(): return sys.stdin.readline().rstrip()


H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
data = [[0]*W for i in range(H)]

for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == ".":
            data[i][j] = 1
        else:
            data[i][j] = 0


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


P = [(0, -1), (0, 1), (1, 0), (-1, 0)]
DX = [-2, -1, 0, 1, 2]
DY = [-2, -1, 0, 1, 2]
G = [[] for i in range(H*W)]
for i in range(H):
    for j in range(W):
        if data[i][j] == 1:
            for dx, dy in P:
                if 0 <= dx+i < H:
                    if 0 <= dy+j < W:
                        if data[dx+i][dy+j] == 1:
                            u, v = trans(i, j), trans(dx+i, dy+j)
                            G[u].append((v, 0))
                            G[v].append((u, 0))
            for dx in DX:
                for dy in DY:
                    if 0 <= dx+i < H:
                        if 0 <= dy+j < W:
                            if data[dx+i][dy+j] == 1:
                                u, v = trans(i, j), trans(dx+i, dy+j)
                                G[u].append((v, 1))
                                G[v].append((u, 1))

D = [10**6+100 for i in range(H*W)]
D[trans(ch-1, cw-1)] = 0
que = []
heapq.heapify(que)
heapq.heappush(que, (0, trans(ch-1, cw-1)))

while que:
    cost, v = heapq.heappop(que)
    if D[v] < cost:
        continue
    for node, cost in G[v]:
        if D[node] > D[v] + cost:
            D[node] = D[v] + cost
            heapq.heappush(que, (D[node], node))

ans = D[trans(dh-1, dw-1)]

if ans == 10**6+100:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
sys.setrecursionlimit(500*500)
import itertools
from collections import Counter,deque

def main():
    h,w = map(int, input().split())
    start = list(map(int, input().split()))
    qy, qx = start[0]-1,start[1]-1
    end = list(map(int, input().split()))
    ey, ex = end[0]-1, end[1]-1

    s = [input().rstrip() for i in range(h)]

    visited = [[0]*w for i in range(h)]
    dist = [[INF]*w for i in range(h)]

    que = deque([(qx,qy)])
    visited[qy][qx] = 1

    dx = (1, -1, 0, 0)
    dy = (0, 0, 1, -1)
    cnt = 0

    dxw = (-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,0,1,1,1,1,2,2,2,2,2)
    dyw = (-2,-1,0,1,2,-2,-1,1,2,-2,0,2,-2,-1,1,2,-2,-1,0,1,2)

    while True:
        while len(que) > 0:
            x,y = que.popleft()
            visited[y][x] = 1
            if x==ex  and y== ey: # ゴールまで辿ったら
                break

            for k in range(4): # 上下左右4パターンの移動方法
                nx = x + dx[k]
                ny = y + dy[k]

                if 0<=nx<w and 0<=ny<h and s[ny][nx]=='.' and visited[ny][nx]==0:
                    que.append((nx,ny))
                    visited[ny][nx] = 1
        if visited[ey][ex] == 0:
            cnt += 1
            flg = False
            for i in range(h):
                for j in range(w):
                    if visited[i][j] == 1:
                        for k in range(21):
                            nx = j + dyw[k]
                            ny = i + dxw[k]
                            if 0<=nx<w and 0<=ny<h and s[ny][nx]=='.' and visited[ny][nx]==0:
                                flg = True
                                que.append((nx,ny))
                                break
                    if flg == True:
                        break
                if flg == True:
                    break
            if flg == False:
                print(-1)
                exit()

        else:
            print(cnt)
            exit()

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
h,w = list(map(int,input().split()))
s1,s2 = list(map(int,input().split()))
f1,f2 = list(map(int,input().split()))
 
s1,s2 = s1-1,s2-1
f1,f2 = f1-1,f2-1
 
Q = [(s1,s2)]
V = [[0]*w for _ in range(h)]
G = []
ALL = [(s1,s2)]
V[s1][s2] = 1
 
for _ in range(h):
  tmp = list(input().rstrip())
  G.append(tmp)
 
count = 0
best = 0
 
while True:
  while Q:
    new_Q = []
    for node in Q:
      i,j = node[0], node[1]
      if i-1>0:
        if V[i-1][j]==0 and G[i-1][j]=='.':
          V[i-1][j]=1
          new_Q.append((i-1,j))
          ALL.append((i-1,j))
 
      if j-1>0:
        if V[i][j-1]==0 and G[i][j-1]=='.':
          V[i][j-1]=1
          new_Q.append((i,j-1))
          ALL.append((i,j-1))
 
      if i+1<h:
        if V[i+1][j]==0 and G[i+1][j]=='.':
          V[i+1][j]=1
          new_Q.append((i+1,j))
          ALL.append((i+1,j))
 
      if j+1<w:
        if V[i][j+1]==0 and G[i][j+1]=='.':
          V[i][j+1]=1
          new_Q.append((i,j+1))
          ALL.append((i,j+1))
 
    Q = new_Q
 
  if V[f1][f2]==1:
    print(count)
    break
  else:
    count += 1
    part= []
    
    ALL = list(set(ALL))
    BE = {}
    
    for node in ALL:
      i,j = node[0], node[1]
      
      for x in range(i-2,i+3):
        for y in range(j-2,j+3):
          if (x,y) not in BE:
            BE[(x,y)] = 1
            if x>-1 and y>-1 and x<h and y<w and G[x][y] == '.' and V[x][y]==0:
              part.append((x,y))         	
       
    ALL = list(part)
    Q = list(ALL)
 
    if (f1,f2) in ALL:
      print(count)
      break
 
    if len(ALL)==0:
      print(-1)
      break

Submission status: Time Limit Exceeded

Solution code:
from sys import *
H, W = map(int, stdin.readline().split())
personY, personX = map(int, stdin.readline().split())
gH, gW = map(int, stdin.readline().split())

grid = [list(stdin.readline().strip()) for x in range(H)]
visited = [[10**10 for j in range(W)] for i in range(H)]
options = [(personY-1, personX-1)]

visited[personY-1][personX-1] = 0
while(options):
    y,x = options.pop()

    if y+1 < H and  grid[y+1][x] == ".":
        if visited[y+1][x] > visited[y][x]:
            options.append((y+1, x))
            visited[y+1][x] = visited[y][x]

    if  y-1 >= 0 and grid[y-1][x] == ".":
        if visited[y-1][x] > visited[y][x]:
            options.append((y-1, x))
            visited[y-1][x] = visited[y][x]

    if x+1 < W and grid[y][x+1] == ".":
        if visited[y][x+1] > visited[y][x]:
            options.append((y, x+1))
            visited[y][x+1] = visited[y][x]

    if   x-1 >= 0 and grid[y][x-1] == ".":
        if visited[y][x-1] > visited[y][x]:
            options.append((y, x-1))
            visited[y][x-1] = visited[y][x]
   #-------------------------------------------
    for Y in range(-2, 3):
        for X in range(-2, 3):
            if x+X >= 0 and x+X < W and y+Y >= 0 and y+Y < H and grid[y+Y][x+X] == ".":
                if visited[y+Y][x+X] > visited[y][x] +1:
                    options.append((y+Y, x+X))
                    visited[y+Y][x+X] = visited[y][x]+1

print(-1 if visited[gH-1][gW-1] == 10**10 else visited[gH-1][gW-1] )