結果
問題 |
No.34 砂漠の行商人
|
ユーザー |
|
提出日時 | 2025-08-02 14:58:11 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 2,029 ms / 5,000 ms |
コード長 | 1,258 bytes |
コンパイル時間 | 4,285 ms |
コンパイル使用メモリ | 203,464 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-02 14:58:20 |
合計ジャッジ時間 | 8,694 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
module main; // https://kmjp.hatenablog.jp/entry/2015/07/14/0930 より // 2次元グリッド、幅優先探索 import std; // 多次元配列をある値で埋める void fill(A, T)(ref A a, T value) if (isArray!A) { alias E = ElementType!A; static if (isArray!E) { foreach (ref e; a) fill(e, value); } else { a[] = value; } } alias P = Tuple!(int, "y", int, "x"); auto dir = [P(-1, 0), P(0, 1), P(1, 0), P(0, -1)]; int N, V, sx, sy, gx, gy; int[][] L; int[][][] HP; void main() { // 入力 readln.chomp.formattedRead("%d %d %d %d %d %d", N, V, sx, sy, gx, gy); sx--, sy--, gx--, gy--; auto L = new int[][](N); foreach (ref row; L) row = readln.split.to!(int[]); // 答えの計算と出力 HP = new int[][][](2, N, N); HP[0][sy][sx] = V; foreach (i; 0 .. 10_001) { int cur = i % 2, tar = cur ^ 1; fill(HP[tar], 0); foreach (y; 0 .. N) { foreach (x; 0 .. N) { if (HP[cur][y][x] <= 0) continue; foreach (d; dir) { int ty = y + d.y, tx = x + d.x; if (ty < 0 || ty >= N || tx < 0 || tx >= N) continue; if (HP[cur][y][x] > L[ty][tx]) HP[tar][ty][tx] = max(HP[tar][ty][tx], HP[cur][y][x] - L[ty][tx]); } } } if (HP[tar][gy][gx] > 0) { writeln(i + 1); return; } } writeln(-1); }