結果

問題 No.2328 Build Walls
コンテスト
ユーザー norioc
提出日時 2025-07-10 08:25:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,334 bytes
コンパイル時間 473 ms
コンパイル使用メモリ 82,700 KB
実行使用メモリ 126,152 KB
最終ジャッジ日時 2025-07-10 08:25:44
合計ジャッジ時間 27,602 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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]]:
    ds = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    res = []
    for d in ds:
        nr = r + d[0]
        nc = c + d[1]
        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)))


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

    cost = A[r][c]
    if cost == -1: return INF
    return cost


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 < -1 or c >= W: continue

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

        cost = get_cost(nr, nc)
        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