Submission #23334257

---

Source Code Expand

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

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

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

"""
空は壁としてよい。
街は草原としてよい。
"""
FREE = -1
WALL = -2

def parse_input(T, W, H, G):
    GG = np.empty((T, H, W), np.int64)
    UP = np.full((T, 2), -1, np.int64)
    DOWN = np.full((T, 2), -1, np.int64)
    for t in range(T):
        for h in range(H):
            for w in range(W):
                a, b = G[t, h, 2 * w:2 * w + 2]
                s = a + b
                if s == '==':
                    GG[t, h, w] = FREE
                elif s == '@@':
                    GG[t, h, w] = FREE
                elif s.isdigit():
                    GG[t, h, w] = int(s)
                elif s == 'HC':
                    GG[t, h, w] = 100
                elif s == '##':
                    GG[t, h, w] = WALL
                elif s == '  ':
                    GG[t, h, w] = WALL
                elif s == '_-':
                    UP[t] = (h, w)
                    GG[t, h, w] = FREE
                elif s == '-_':
                    DOWN[t] = (h, w)
                    GG[t, h, w] = FREE
                elif s == '$$':
                    TO = (t, h, w)
                    GG[t, h, w] = FREE
                elif s == 'KR':
                    FRM = (t, h, w)
                    GG[t, h, w] = FREE
                else:
                    raise ValueError(s)
    t, h, w = FRM
    GG = GG[t:]
    FRM = (0, h, w)
    TO = (TO[0] - t, TO[1], TO[2])
    return GG, UP, DOWN, FRM, TO

t = numba.typeof((1, 1, 1))


@njit((i8, i8[:, :, :], i8[:, :], i8[:, :], t, t), cache=True)
def main(L, G, UP, DOWN, FRM, TO):
    T, H, W = G.shape
    MAX = 101
    INF = 1 << 60
    dist = np.full((T, H, W, MAX + 1), INF, np.int64)
    init = FRM + (min(MAX, L), )
    que = [(0, init)]
    dist[init] = 0

    def update(frm, to, cost):
        if dist[to] > dist[frm] + cost:
            dist[to] = dist[frm] + cost
            heappush(que, (dist[to], to))

    while que:
        D, frm = heappop(que)
        t, h, w, lv = frm
        if D > dist[frm]:
            continue
        """
        階段
        """
        frm = (t, h, w, lv)
        if UP[t, 0] == h and UP[t, 1] == w:
            to = (t + 1, DOWN[t + 1, 0], DOWN[t + 1, 1], lv)
            if to[1] == -1:
                continue
            update(frm, to, 1)
        if t > 0 and DOWN[t, 0] == h and DOWN[t, 1] == w:
            to = (t - 1, UP[t - 1, 0], UP[t - 1, 1], lv)
            if to[1] == -1:
                continue
            update(frm, to, 1)
        """
        通常移動
        """
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            h1, w1 = h + dx, w + dy
            if not (0 <= h1 < H):
                continue
            if not (0 <= w1 < W):
                continue
            x = G[t, h1, w1]
            if x == WALL:
                continue
            if x == FREE:
                to = (t, h1, w1, lv)
                update(frm, to, 1)
                continue
            assert 0 <= x <= MAX
            if x > lv:
                continue
            to = (t, h1, w1, lv + (x == lv))
            update(frm, to, x + 1)
    ans = dist[TO].min()
    if ans == INF:
        print('Impossible')
    else:
        print(ans)

T, W, H, L = from_readline()
G = np.array(list(read().decode())).reshape(T, H, W + W + 1)[:, :, :-1]

main(
    L,
    *parse_input(T, W, H, G),
)

Submission Info

Judge Result