結果

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

ソースコード

diff # 

from collections import defaultdict, deque
from heapq import heappush, heappop


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 Array2:
    def __init__(self, shape, init):
        assert len(shape) == 2
        assert all(len(dim) == 2 for dim in shape)
        assert all(a < b for a, b in shape)

        self.shape = shape
        dim0 = shape[0]
        dim1 = shape[1]
        nd0 = dim0[1] - dim0[0]
        nd1 = dim1[1] - dim0[0]
        self.data = [init] * (nd0 * nd1)

    def _get_index(self, item):
        dim0 = self.shape[0]
        dim1 = self.shape[1]
        assert dim0[0] <= item[0] < dim0[1], (dim0[0], item[0], dim0[1])
        assert dim1[0] <= item[1] < dim1[1], (dim1[0], item[1], dim1[1])

        nd1 = dim1[1] - dim1[0]
        p0 = item[0] - dim0[0]
        p1 = item[1] - dim1[0]
        return p0 * nd1 + p1

    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


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, r, c))


shape = ((-10, H+10), (-10, W+10))
# costs = defaultdict(lambda: 0)
costs = Array2(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 = defaultdict(lambda: INF)
dists = Array2(shape, INF)
while q:
    d, r, c = heappop(q)
    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
        if costs[nr, nc] == INF: continue

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

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