Submission #16156582


Source Code Expand

Copy
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
from heapq import *

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

@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main(wall, Sx, Sy, Tx, Ty):
    INF = 1 << 30
    H, W = wall.shape
    S = Sx * W + Sy
    T = Tx * W + Ty
    dist = np.full(H * W, INF, np.int64)
    q = [(0,S)]
    while q:
        dv, v = heappop(q)
        if dv > dist[v]:
            continue
        vx, vy = divmod(v, W)
        # そのままあるく
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            wx, wy = vx + dx, vy + dy
            if not (0 <= wx < H):
                continue
            if not (0 <= wy < W):
                continue
            if wall[wx, wy]:
                continue
            w = wx * W + wy
            if dist[w] <= dv:
                continue
            dist[w] = dv
            heappush(q, (dv, w))
        # ワープする
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                wx, wy = vx + dx, vy + dy
                if not (0 <= wx < H):
                    continue
                if not (0 <= wy < W):
                    continue
                if wall[wx, wy]:
                    continue
                w = wx * W + wy
                if dist[w] <= dv + 1:
                    continue
                dist[w] = dv + 1
                heappush(q, (dv+1, w))
    ans = dist[T]
    if ans == INF:
        ans = -1
    return ans

H, W = map(int, readline().split())
Sx, Sy = map(lambda x: int(x) - 1, readline().split())
Tx, Ty = map(lambda x: int(x) - 1, readline().split())
wall = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'#'

print(main(wall, Sx, Sy, Tx, Ty))

Submission Info

Submission Time
Task D - Wizard in Maze
User maspy
Language Python (3.8.2)
Score 400
Code Size 1863 Byte
Status
Exec Time 872 ms
Memory 114828 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
× 3
× 14
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, max_01.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_11.txt, random_12.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt 599 ms 106780 KB
hand_02.txt 583 ms 106016 KB
max_01.txt 599 ms 114828 KB
random_01.txt 590 ms 114624 KB
random_02.txt 570 ms 106828 KB
random_03.txt 661 ms 114648 KB
random_04.txt 603 ms 106320 KB
random_05.txt 872 ms 114452 KB
random_06.txt 637 ms 109256 KB
random_11.txt 561 ms 106716 KB
random_12.txt 554 ms 105940 KB
sample_01.txt 576 ms 106080 KB
sample_02.txt 585 ms 106336 KB
sample_03.txt 582 ms 106704 KB