結果
問題 | 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 heapqH,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]:continuefor 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] = tempheapq.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)