結果
問題 | No.2328 Build Walls |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:06:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,139 ms / 3,000 ms |
コード長 | 1,105 bytes |
コンパイル時間 | 672 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 92,848 KB |
最終ジャッジ日時 | 2024-12-27 04:35:55 |
合計ジャッジ時間 | 12,618 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#壁の置き方を経路と考える。 #8方向すべてに行くことができる #左端から右端に到達出来たら可能 #すべてのHについて探索する。DFSするのでH*H*W #800**3って通るんすか?通らなそう #ダイクストラ法みたいなことをすればよい? import heapq H,W = map(int,input().split()) A = [list(map(int,input().split())) for i in range(H-2)] queue = [] costs = [[float('inf')]*W for i in range(H-2)] for i in range(H-2): if A[i][0] != -1: costs[i][0] = A[i][0] heapq.heappush(queue,(A[i][0],i,0)) while queue: cost,h,w = heapq.heappop(queue) if cost > costs[h][w]: continue for dh,dw in ((0,1),(1,0),(-1,0),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1)): if 0 <= h+dh < H-2 and 0 <= w+dw < W and A[h+dh][w+dw] != -1: temp = costs[h][w] + A[h+dh][w+dw] if temp < costs[h+dh][w+dw]: costs[h+dh][w+dw] = temp heapq.heappush(queue,(temp,h+dh,w+dw)) ans = min([costs[i][-1] for i in range(H-2)]) if ans == float("inf"): print(-1) else: print(ans)