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
H, W = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
S = sys.stdin.readlines()

INF = 10**6
cnt = [[INF]*W for _ in range(H)]
walk = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def jump(x, y, i):
  if i == 0:
    return [(x-2, y+2),(x-1, y+2),(x, y+2),(x+1, y+2),(x+2, y+2),(x-1, y+1),(x+1, y+1)]
  elif i == 1:
    return [(x+2, y+2),(x+2, y+1),(x+2, y),(x+2, y-1),(x+2, y-2),(x+1, y+1),(x+1, y-1)]
  elif i == 2:
    return [(x-2, y-2),(x-1, y-2),(x, y-2),(x+1, y-2),(x+2, y-2),(x-1, y-1),(x+1, y-1)]
  elif i == 3:
    return [(x-2, y+2),(x-2, y+1),(x-2, y),(x-2, y-1),(x-2, y-2),(x-1, y+1),(x-1, y-1)]
  
next_pos = [(c_h-1, c_w-1)]
warp = 0
jump_pos = []
 
while True:
  while next_pos:
    x, y = next_pos.pop(0)
    cnt[x][y] = warp
    for i in range(4):
      a, b = walk[i]
      walk_x, walk_y = x+a, y+b
      if walk_x < 0 or walk_x >= H or walk_y < 0 or walk_y >= W:
        continue
      elif S[walk_x][walk_y] == '#':
        jump_pos += jump(x, y, i)
      else:
        if cnt[walk_x][walk_y] <= warp:
          continue
        else:
          cnt[walk_x][walk_y] = warp
          next_pos.append((walk_x, walk_y))
  for x, y in set(jump_pos):
    if x < 0 or x >= H or y < 0 or y >= W:
        continue
    elif S[x][y] == '#':
      continue
    elif cnt[x][y] <= warp:
      continue
    else:
      next_pos.append((x, y))
  if next_pos == []:
    break
  else:
    warp += 1
    jump_pos = []
    
# print(cnt)
if cnt[d_h-1][d_w-1] == INF:
  print(-1)
else:
  print(cnt[d_h-1][d_w-1])

Submission status: Time Limit Exceeded

Solution code:
def d_wizard_in_maze():
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Start_row, Start_col = [int(i) - 1 for i in input().split()]
    Goal_row, Goal_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    neighbor = ((-1, 0), (1, 0), (0, -1), (0, 1))  # 上下左右
    warp = tuple((i, j) for i in range(-2, 3) for j in range(-2, 3)
                 if (i, j) not in neighbor)
    # dist[r][c]: スタートから (r, c) に到達するために必要なワープ回数の最小値
    dist = [[float('inf')] * W for _ in range(H)]

    def is_inside(row, col):
        return 0 <= row < H and 0 <= col < W

    def next_query(row, col, time, _next, cost):
        for dr, dc in _next:
            nr, nc = row + dr, col + dc
            if is_inside(nr, nc) and Grid[nr][nc] == '.' and time < dist[nr][nc]:
                if cost == 0:
                    queue.append((nr, nc, time))
                else:
                    queue.appendleft((nr, nc, time + 1))

    queue = deque([(Start_row, Start_col, 0)])
    while queue:
        row, col, time = queue.pop()
        if time > dist[row][col]:
            continue  # キューに入れた時点では候補だったが、後に歩いて行けるとわかった

        dist[row][col] = time
        next_query(row, col, time, neighbor, 0)
        next_query(row, col, time, warp, 1)
    return -1 if dist[Goal_row][Goal_col] == float('inf') else dist[Goal_row][Goal_col]

print(d_wizard_in_maze())

Submission status: Time Limit Exceeded

Solution code:
#入力受け取りの高速化、しなくてもよい
#但し文字列のまま扱うときは注意、例えば . は46として、 # は35として扱われる
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
#ここまでが高速化
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=inputs()
#0 based index (0始まり)にする
nx-=1;ny-=1;gx-=1;gy-=1
from collections import deque
#dqが徒歩、2が魔法での移動を入れる
dq=deque([(nx,ny)])
dq2=deque([])
#かかるコストを保存しておく
T=[[float('inf')]*w for  a in range(h)]
#初期値は0で、スタート地点に保存
T[nx][ny]=0
#徒歩でのx,yの差分
moves=((1,0),(-1,0),(0,1),(0,-1))
from itertools import product as pr
#魔法での移動の差分、tuple( (i,j) |-2<=i,j<=2かつ(i,j)!=(0,0)  )と等価
Mmoves=tuple(i for i in pr((-2,-1,0,1,2),repeat=2)if i!=(0,0) )

while dq:
    #先に徒歩で行けるだけ行きたいので、徒歩を使い切るまでは魔法で行った地点たちに手を出さない
    while dq:
        x,y=dq.popleft()
        for i,j in moves:
            nex,ney=x+i,y+j
            #盤面の外や壁にぶつかるのは除外
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]<T[nex][ney]:
                #コストを更新できるなら改めて捜査
                T[nex][ney]=T[x][y]
                dq.append((nex,ney))
        for i,j in Mmoves:
            nex,ney=x+i,y+j
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]+1<T[nex][ney]:
                T[nex][ney]=T[x][y]+1
                dq2.append((nex,ney))
    #徒歩で行ける地点を使い切ったので、今度は魔法で行ける地点を捜査
    dq,dq2=dq2,dq
if T[gx][gy]==float('inf'):print(-1)
else:print(T[gx][gy])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])
INF = 10**18


def to_v(i, j):
    return i*w+j


n = h*w
start = to_v(si, sj)
goal = to_v(gi, gj)


def generate_v2(v):
    i, j = divmod(v, w)
    it = [-2, -1, 0, 1, 2]
    for di, dj in product(it, repeat=2):
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        if (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:
            d = 0
        else:
            d = 1
        yield d, x*w+y


def bfs(init_v):
    next_v = deque([init_v])
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    visited = [0]*n
    while next_v:
        v = next_v.popleft()
        if visited[v]:
            continue
        visited[v] = 1
        for d, v2 in generate_v2(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            if d:
                next_v.append(v2)
            else:
                next_v.appendleft(v2)
    return dist


ans = bfs(start)[goal]
print(-1 if ans == INF else ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy
def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    dummy = tuple(['#'] * (w + 4))
    maze = {e: [] for e in range(h + 4)}
    maze[0] = dummy
    maze[1] = dummy
    for i in range(h):
        dicrow = {e : "" for e in range(w + 4)}
        dicrow[0] = '#'
        dicrow[1] = '#'
        row = tuple(input())
        for j, re in enumerate(row):
            dicrow[j+2] = re
        dicrow[w+2] = '#'
        dicrow[w+3] = '#'
        maze[i+2] = dicrow
    maze[h+2] = dummy
    maze[h+3] = dummy
    maze[ch][cw] = 0

    next_nodes = deque()
    next_nodes.append((ch, cw))
    next2_nodes = deque()
    cnt = 0
    while next_nodes:
        while next_nodes:
            (nextny, nextnx) = next_nodes.popleft()
            flag = False
            curg = maze[nextny][nextnx]
            for j1 in range(4):
                ny = nextny + movey[j1]
                nx = nextnx + movex[j1]
                if maze[ny][nx] == '.':
                    maze[ny][nx] = curg
                    if (ny, nx) in next_nodes:
                        next_nodes.remove((ny, nx))
                    next2_nodes.appendleft((ny, nx))
                elif maze[ny][nx] == '#':
                    flag = True
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.appendleft((ny, nx))
            if flag:
                for j1 in range(20):
                    ny = nextny + warpy[j1]
                    nx = nextnx + warpx[j1]
                    nextg = maze[ny][nx]
                    if nextg == '.':
                        next2_nodes.append((ny, nx))
                        maze[ny][nx] = curg + 1
                    elif nextg == '#':
                        pass
                    elif nextg > curg + 1:
                        maze[ny][nx] = curg + 1
                        next2_nodes.append((ny, nx))
        next_nodes = deepcopy(next2_nodes)
        next2_nodes = deque()
    g = maze[dh][dw]
    if g == '.':
        print(-1)
    else:
        print(g)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説を参考に作成

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(H, W, C, D, Ss):
    cost_map = [[-1] * (W + 4) for _ in range(H + 4)]
    Ss = ['#' * (W + 4)] * 2 + ['##' + S + '##' for S in Ss] + ['#' * (W + 4)] * 2
    C = [c + 1 for c in C]
    D = [d + 1 for d in D]
    cost = 0
    ans = -1
    dq = deque()
    dq.append(C)
    while dq:
        next_dq = deque()
        flg = False
        while dq:
            h, w = dq.popleft()
            if h == D[0] and w == D[1]:
                ans = cost
                flg = True
                break
            if cost_map[h][w] >= 0:
                continue
            cost_map[h][w] = cost
            for i in range(h - 2, h + 2 + 1):
                for j in range(w - 2, w + 2 + 1):
                    if Ss[i][j] == '#':
                        continue
                    if cost_map[i][j] >= 0:
                        continue
                    if abs(h - i) + abs(w - j) == 1:
                        dq.append([i, j])
                    else:
                        next_dq.append([i, j])
        if flg:
            break
        dq = next_dq
        cost += 1
    print(ans)


if __name__ == '__main__':
    # S = input()
    # N = int(input())
    H, W = map(int, input().split())
    C = [int(i) for i in input().split()]
    D = [int(i) for i in input().split()]
    Ss = [input() for _ in range(H)]
    # Bs = [int(i) for i in input().split()]
    solve(H, W, C, D, Ss)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
def main():
    H, W = map(int, input().split())
    sh,sw = map(int, input().split())
    gh,gw = map(int, input().split())
    gh,gw = gh-1,gw-1
    field = [list(input()) for _ in range(H)]

    q = [(0, sh-1, sw-1)]
    INF = 10 ** 30
    dist = [[INF] * W for _ in range(H)]
    dist[sh-1][sw-1] = 0
    while q:
        cnt, h, w = heappop(q)
        if dist[h][w] < cnt: continue
        if h == gh and w == gw: return cnt
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh = h+i
                nw = w+j
                if nh < 0 or nw < 0: continue
                if nh >= H or nw >= W: continue
                if field[nh][nw]  == "#": continue
                if (i, j) in ((1,0),(0,1),(-1,0),(0,-1)):
                    if dist[nh][nw] <= cnt: continue
                    dist[nh][nw] = cnt
                    heappush(q, (cnt, nh, nw))
                else:
                    if dist[nh][nw] <= cnt+1: continue
                    dist[nh][nw] = cnt+1
                    heappush(q, (cnt+1, nh, nw))
    return -1

print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])
INF = 10**18


def to_v(i, j):
    return i*w+j


n = h*w
start = to_v(si, sj)
goal = to_v(gi, gj)


def generate_v2(v):
    i, j = divmod(v, w)
    it = [-2, -1, 0, 1, 2]
    for di, dj in product(it, repeat=2):
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        if (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:
            d = 0
        else:
            d = 1
        yield d, x*w+y


def bfs(init_v):
    next_v = deque([init_v])
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for d, v2 in generate_v2(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            if d:
                next_v.append(v2)
            else:
                next_v.appendleft(v2)
    return dist


ans = bfs(start)[goal]
print(-1 if ans == INF else ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy
def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    dummy = tuple(['#'] * (w + 4))
    maze = {e: [] for e in range(h + 4)}
    maze[0] = dummy
    maze[1] = dummy
    for i in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze[i+2] = row
    maze[h+2] = dummy
    maze[h+3] = dummy
    maze[ch][cw] = 0

    next_nodes = deque()
    next_nodes.append((ch, cw))
    next2_nodes = deque()
    cnt = 0
    while next_nodes:
        while next_nodes:
            (nextny, nextnx) = next_nodes.popleft()
            flag = False
            curg = maze[nextny][nextnx]
            for j1 in range(4):
                ny = nextny + movey[j1]
                nx = nextnx + movex[j1]
                if maze[ny][nx] == '.':
                    maze[ny][nx] = curg
                    if (ny, nx) in next_nodes:
                        next_nodes.remove((ny, nx))
                    next2_nodes.appendleft((ny, nx))
                elif maze[ny][nx] == '#':
                    flag = True
                elif maze[ny][nx] > curg:
                    maze[ny][nx] = curg
                    next2_nodes.appendleft((ny, nx))
            if flag:
                for j1 in range(20):
                    ny = nextny + warpy[j1]
                    nx = nextnx + warpx[j1]
                    nextg = maze[ny][nx]
                    if nextg == '.':
                        next2_nodes.append((ny, nx))
                        maze[ny][nx] = curg + 1
                    elif nextg == '#':
                        pass
                    elif nextg > curg + 1:
                        maze[ny][nx] = curg + 1
                        next2_nodes.append((ny, nx))
        next_nodes = deepcopy(next2_nodes)
        next2_nodes = deque()
    g = maze[dh][dw]
    if g == '.':
        print(-1)
    else:
        print(g)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        if 0 <= px+dx < w and 0 <= py+dy < h:
            childy = py + dy
            childx = px + dx
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            if 0 <= px+dx < w and 0 <= py+dy < h:
                warpx = px + dx
                warpy = py + dy
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
def main():
    H, W = map(int, input().split())
    sh,sw = map(int, input().split())
    gh,gw = map(int, input().split())
    gh,gw = gh-1,gw-1
    field = [list(input()) for _ in range(H)]

    q = [(0, sh-1, sw-1)]
    INF = 10 ** 30
    dist = [[INF] * W for _ in range(H)]
    while q:
        cnt, h, w = heappop(q)
        if dist[h][w] < cnt: continue
        dist[h][w] = cnt
        if h == gh and w == gw: return cnt
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh = h+i
                nw = w+j
                if nh < 0 or nw < 0: continue
                if nh >= H or nw >= W: continue
                if field[nh][nw]  == "#": continue
                if (i, j) in ((1,0),(0,1),(-1,0),(0,-1)):
                    if dist[nh][nw] <= cnt: continue
                    heappush(q, (cnt, nh, nw))
                else:
                    if dist[nh][nw] <= cnt+1: continue
                    heappush(q, (cnt+1, nh, nw))
    return -1

print(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)]
INF = 10**11
cnt = [[INF]*W for _ in range(H)]
walk = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def jump(x, y, i):
  if i == 0:
    return [(x-2, y+2),(x-1, y+2),(x, y+2),(x+1, y+2),(x+2, y+2),(x-1, y+1),(x+1, y+1)]
  elif i == 1:
    return [(x+2, y+2),(x+2, y+1),(x+2, y),(x+2, y-1),(x+2, y-2),(x+1, y+1),(x+1, y-1)]
  elif i == 2:
    return [(x-2, y-2),(x-1, y-2),(x, y-2),(x+1, y-2),(x+2, y-2),(x-1, y-1),(x+1, y-1)]
  elif i == 3:
    return [(x-2, y+2),(x-2, y+1),(x-2, y),(x-2, y-1),(x-2, y-2),(x-1, y+1),(x-1, y-1)]
  
next_pos = [(c_h-1, c_w-1)]
warp = 0
jump_pos = []

while True:
  while next_pos:
    x, y = next_pos.pop(0)
    cnt[x][y] = warp
    for i in range(4):
      a, b = walk[i]
      walk_x, walk_y = x+a, y+b
      if walk_x < 0 or walk_x >= H or walk_y < 0 or walk_y >= W:
        continue
      elif cnt[walk_x][walk_y] <= warp:
          continue
      elif S[walk_x][walk_y] == '#':
        jump_pos += jump(x, y, i)
      else:
        cnt[walk_x][walk_y] = warp
        next_pos.append((walk_x, walk_y))
  for x, y in set(jump_pos):
    if x < 0 or x >= H or y < 0 or y >= W:
      continue
    elif cnt[x][y] <= warp:
      continue
    elif S[x][y] == '#':
      continue
    else:
      next_pos.append((x, y))
  if next_pos == []:
    break
  else:
    warp += 1
    jump_pos = []
    
if cnt[d_h-1][d_w-1] == INF:
  print(-1)
else:
  print(cnt[d_h-1][d_w-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        childy = py + dy
        childx = px + dx
        if 0 <= childx < w and 0 <= childy < h:
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            warpx = px + dx
            warpy = py + dy
            if 0<=warpx<w and 0<=warpy<h:
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

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())

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

S=[]
for _ in range(h):
  s=input()
  sl=[]
  for i in range(w):
    sl.append(s[i])
  S.append(sl)

def isable(X):
  xh,xw=X[0],X[1]
  if 0<=xh<=h-1 and 0<=xw<=w-1 and S[xh][xw]=='.':
    return True
  else:
    return False

def stepA(X):
  xh,xw=X[0],X[1]
  A=[]
  for p,q in [(-1,0),(0,1),(1,0),(0,-1)]:
    if isable([xh+p,xw+q]):
      A.append([xh+p,xw+q])
  return A
    
def stepB(X):
  xh,xw=X[0],X[1]
  B=[]
  for i in range(-2,3):
    for j in range(-2,3):
      if i==0 and j==0:
        continue
      if isable([xh+i,xw+j]):
        B.append([xh+i,xw+j])
  return B

Q=deque()
Q.appendleft((ch,cw))
cost=[[float('inf') for i in range(w)] for j in range(h)]
cost[ch][cw]=0

while Q:
  ph,pw=Q.popleft()
  for v in stepA([ph,pw]):
    ah,aw=v[0],v[1]
    if isable([ah,aw]):
      if cost[ah][aw]>cost[ph][pw]:
        cost[ah][aw]=cost[ph][pw]
        Q.appendleft([ah,aw])
  for bh,bw in stepB([ph,pw]):
    if isable([bh,bw]):
      if cost[bh][bw]>cost[ph][pw]+1:
        cost[bh][bw]=cost[ph][pw]+1
        Q.append([bh,bw])

if cost[dh][dw]==float('inf'):
  print(-1)
else:
  print(cost[dh][dw])

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)]
INF = 10**11
cnt = [[INF]*W for _ in range(H)]
walk = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def jump(x, y, i):
  if i == 0:
    return [(x-2, y+2),(x-1, y+2),(x, y+2),(x+1, y+2),(x+2, y+2),(x-1, y+1),(x+1, y+1)]
  elif i == 1:
    return [(x+2, y+2),(x+2, y+1),(x+2, y),(x+2, y-1),(x+2, y-2),(x+1, y+1),(x+1, y-1)]
  elif i == 2:
    return [(x-2, y-2),(x-1, y-2),(x, y-2),(x+1, y-2),(x+2, y-2),(x-1, y-1),(x+1, y-1)]
  elif i == 3:
    return [(x-2, y+2),(x-2, y+1),(x-2, y),(x-2, y-1),(x-2, y-2),(x-1, y+1),(x-1, y-1)]
  
next_pos = [(c_h-1, c_w-1)]
warp = 0
jump_pos = []
judge = True
while judge:
  while next_pos:
    x, y = next_pos.pop(0)
    cnt[x][y] = warp
    if x == d_h-1 and y == d_w-1:
      judge = False
      break
    for i in range(4):
      a, b = walk[i]
      walk_x, walk_y = x+a, y+b
      if walk_x < 0 or walk_x >= H or walk_y < 0 or walk_y >= W:
        continue
      elif S[walk_x][walk_y] == '#':
        jump_pos += jump(x, y, i)
      else:
        if cnt[walk_x][walk_y] <= warp:
          continue
        else:
          cnt[walk_x][walk_y] = warp
          next_pos.append((walk_x, walk_y))
  for x, y in set(jump_pos):
    if x < 0 or x >= H or y < 0 or y >= W:
        continue
    elif S[x][y] == '#':
      continue
    elif cnt[x][y] <= warp:
      continue
    else:
      next_pos.append((x, y))
  if next_pos == []:
    judge = False
    break
  else:
    warp += 1
    jump_pos = []
    
# print(cnt)
if cnt[d_h-1][d_w-1] == INF:
  print(-1)
else:
  print(cnt[d_h-1][d_w-1])

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)]
INF = 10**11
cnt = [[INF]*W for _ in range(H)]
walk = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def jump(x, y, i):
  if i == 0:
    return [(x-2, y+2),(x-1, y+2),(x, y+2),(x+1, y+2),(x+2, y+2),(x-1, y+1),(x+1, y+1)]
  elif i == 1:
    return [(x+2, y+2),(x+2, y+1),(x+2, y),(x+2, y-1),(x+2, y-2),(x+1, y+1),(x+1, y-1)]
  elif i == 2:
    return [(x-2, y-2),(x-1, y-2),(x, y-2),(x+1, y-2),(x+2, y-2),(x-1, y-1),(x+1, y-1)]
  elif i == 3:
    return [(x-2, y+2),(x-2, y+1),(x-2, y),(x-2, y-1),(x-2, y-2),(x-1, y+1),(x-1, y-1)]
  
next_pos = [(c_h-1, c_w-1)]
warp = 0
jump_pos = []

while True:
  while next_pos:
    x, y = next_pos.pop(0)
    cnt[x][y] = warp
    for i in range(4):
      a, b = walk[i]
      walk_x, walk_y = x+a, y+b
      if walk_x < 0 or walk_x >= H or walk_y < 0 or walk_y >= W:
        continue
      elif S[walk_x][walk_y] == '#':
        jump_pos += jump(x, y, i)
      else:
        if cnt[walk_x][walk_y] <= warp:
          continue
        else:
          cnt[walk_x][walk_y] = warp
          next_pos.append((walk_x, walk_y))
  for x, y in set(jump_pos):
    if x < 0 or x >= H or y < 0 or y >= W:
        continue
    elif S[x][y] == '#':
      continue
    elif cnt[x][y] <= warp:
      continue
    else:
      next_pos.append((x, y))
  if next_pos == []:
    break
  else:
    warp += 1
    jump_pos = []
    
# print(cnt)
if cnt[d_h-1][d_w-1] == INF:
  print(-1)
else:
  print(cnt[d_h-1][d_w-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

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

def main():
    row=[]
    col=[]
    data=[]
    for h in range(H):
        for w in range(W):
            idx_from=idx(h,w)
            if Ss[h][w]==0:
                continue
            adj=[(-1,0), (0,1), (1,0), (0,-1)]
            #for dp in [(-1,0), (0,1), (1,0), (0,-1)]:
            #    dh,dw = dp
            #    h_dst=h+dh
            #    w_dst=w+dw
            #    if (0<= h_dst <H) and (0<= w_dst<W) and (Ss[h_dst][w_dst]==1):
            #        row.append(idx_from)
            #        col.append(idx(h_dst,w_dst))
            #        data.append(0)
            for dh in [-2,-1, 0, 1, 2]:
                for dw in [-2, -1, 0, 1, 2]:
                    h_dst=h+dh
                    w_dst=w+dw
                    if (0<=h_dst<H) and (0<=w_dst<W) and (dh!=0 or dw!=0) and (Ss[h_dst][w_dst]==1):
                        row.append(idx_from)
                        col.append(idx(h_dst,w_dst))
                        if (dh,dw) in adj:
                            data.append(1)
                        else:
                            data.append(10**6)
    row=np.array(row)
    col=np.array(col)
    data=np.array(data)
    graph=csr_matrix((data,(row,col)), shape=(N,N))
    #print(graph.toarray())

    dist_matrix = dijkstra(csgraph=graph, directed=False, indices=idx(Ch,Cw), return_predecessors=False)
    #print(dist_matrix)
    #print(predecessors)
    #print(dist_matrix[idx(Dh,Dw)])
    ans=dist_matrix[idx(Dh,Dw)]
    ans=-1 if ans==np.inf else int(ans)//10**6

    print(ans)


H,W=map(int,input().split())
N=H*W
Ch,Cw=[int(e)-1 for e in input().split()]
Dh,Dw=[int(e)-1 for e in input().split()]
Ss=[]
for _ in range(H):
    Ss.append([(1 if c=='.'else 0) for c in input()])
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

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

def main():
    row=[]
    col=[]
    data=[]
    for h in range(H):
        for w in range(W):
            idx_from=idx(h,w)
            if Ss[h][w]==0:
                continue
            adj=[(-1,0), (0,1), (1,0), (0,-1)]
            #for dp in [(-1,0), (0,1), (1,0), (0,-1)]:
            #    dh,dw = dp
            #    h_dst=h+dh
            #    w_dst=w+dw
            #    if (0<= h_dst <H) and (0<= w_dst<W) and (Ss[h_dst][w_dst]==1):
            #        row.append(idx_from)
            #        col.append(idx(h_dst,w_dst))
            #        data.append(0)
            for dh in [-2,-1, 0, 1, 2]:
                for dw in [-2, -1, 0, 1, 2]:
                    h_dst=h+dh
                    w_dst=w+dw
                    if (0<=h_dst<H) and (0<=w_dst<W) and (dh!=0 or dw!=0) and (Ss[h_dst][w_dst]==1):
                        row.append(idx_from)
                        col.append(idx(h_dst,w_dst))
                        if (dh,dw) in adj:
                            data.append(1)
                        else:
                            data.append(10**6)
    row=np.array(row)
    col=np.array(col)
    data=np.array(data)
    graph=csr_matrix((data,(row,col)), shape=(N,N))
    #print(graph.toarray())

    dist_matrix, predecessors = dijkstra(csgraph=graph, directed=False, indices=idx(Ch,Cw), return_predecessors=True)
    #print(dist_matrix)
    #print(predecessors)
    #print(dist_matrix[idx(Dh,Dw)])
    ans=dist_matrix[idx(Dh,Dw)]
    ans=-1 if ans==np.inf else int(ans)//10**6

    print(ans)


H,W=map(int,input().split())
N=H*W
Ch,Cw=[int(e)-1 for e in input().split()]
Dh,Dw=[int(e)-1 for e in input().split()]
Ss=[]
for _ in range(H):
    Ss.append([(1 if c=='.'else 0) for c in input()])
main()