結果

問題 No.2328 Build Walls
コンテスト
ユーザー norioc
提出日時 2025-07-10 09:10:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,396 bytes
コンパイル時間 527 ms
コンパイル使用メモリ 81,840 KB
実行使用メモリ 138,168 KB
最終ジャッジ日時 2025-07-10 09:11:22
合計ジャッジ時間 25,963 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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)

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

    def _get_index(self, item: tuple[tuple[int, int]]) -> int:
        assert len(item) == len(self.shape)
        offset = 0
        stride = 1
        for i in reversed(range(len(self.shape))):
            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.extend([INF] * W)
    else:
        a = list(map(int, input().split()))
        A.extend([(x if x != -1 else INF) for x in a])

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

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


def get_cost(r, c):
    if r < 0 or r >= H: return 0
    if c < 0 or c >= W: return 0

    return A[r * W + c]


shape = ((-10, H+10), (-10, W+10))
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 c == W-1: break

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

        cost = get_cost(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