結果

問題 No.2328 Build Walls
ユーザー norioc
提出日時 2025-07-10 03:19:06
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,491 bytes
コンパイル時間 410 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 245,396 KB
最終ジャッジ日時 2025-07-10 03:19:48
合計ジャッジ時間 38,545 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 TLE * 5 -- * 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)

        dim0 = shape[0]
        dim1 = shape[1]
        nd0 = dim0[1] - dim0[0]
        nd1 = dim1[1] - dim0[0]
        self.shape = shape
        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]
        assert 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


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 = 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, 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
        if costs[nr, nc] == INF: continue

        nd = d + costs[nr, nc]
        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