結果

問題 No.2328 Build Walls
ユーザー norioc
提出日時 2025-07-10 05:30:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,389 bytes
コンパイル時間 351 ms
コンパイル使用メモリ 82,324 KB
実行使用メモリ 156,224 KB
最終ジャッジ日時 2025-07-10 05:30:59
合計ジャッジ時間 29,042 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappush, heappop
import math


def neighbors8(r: int, c: int) -> list[tuple[int, int]]:
    res = []
    for dr in range(-1, 2):
        for dc in range(-1, 2):
            if abs(dr) + abs(dc) == 0: continue
            nr = r + dr
            nc = c + dc
            res.append((nr, nc))

    return res


class NDArray:
    def __init__(self, shape, init):
        assert all(len(b) == 2 and b[0] < b[1] for b in shape)

        sizes = [e - s for s, e in shape]
        self.shape = shape
        self.ndim = len(shape)
        self.data = [init] * math.prod(sizes)

    def _get_index(self, item: tuple[tuple[int, int]]) -> int:
        assert len(item) == self.ndim
        offset = 0
        stride = 1
        for i in reversed(range(self.ndim)):
            p = item[i]
            start, end = self.shape[i]
            assert start <= p < end
            offset += (p - start) * stride
            stride *= end - start

        return offset

    def __getitem__(self, item):
        ind = self._get_index(item)
        return self.data[ind]

    def __setitem__(self, key, value):
        ind = self._get_index(key)
        self.data[ind] = value


def encode(a, b):
    x = a + 10
    y = b + 10
    return (x << 16) | y


def decode(v):
    x = (v >> 16)
    y = v & 0xffff
    return (x-10), (y-10)


INF = 1 << 60
H, W = map(int, input().split())
A = []
for i in range(H):
    if i == 0 or i == H-1:
        A.append([INF] * W)
    else:
        A.append(list(map(int, input().split())))

starts = []
goals = []
for r in range(1, H):
    starts.append((r, -1))
    goals.append((r, W))

q = []
for r, c in starts:
    heappush(q, (0, encode(r, c)))

shape = ((-10, H+10), (-10, W+10))
costs = NDArray(shape, 0)
for i in range(H):
    for j in range(W):
        c = A[i][j]
        costs[i, j] = c if c != -1 else INF

dists = NDArray(shape, INF)
while q:
    d, v = heappop(q)
    r, c = decode(v)
    if dists[r, c] <= d: continue
    dists[r, c] = d
    if r < -1 or r >= H: continue
    if c < -1 or c >= W: continue

    for nr, nc in neighbors8(r, c):
        if nr in (0, H-1): continue

        cost = costs[nr, nc]
        if cost == INF: continue
        nd = d + cost
        if dists[nr, nc] <= nd: continue
        heappush(q, (nd, encode(nr, nc)))

ans = min(dists[r, c] for r, c in goals)
if ans == INF:
    print(-1)
else:
    print(ans)
0