結果
問題 | No.2855 Move on Grid |
ユーザー |
|
提出日時 | 2024-08-25 14:11:08 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 426 ms / 3,000 ms |
コード長 | 1,890 bytes |
コンパイル時間 | 4,706 ms |
コンパイル使用メモリ | 179,184 KB |
実行使用メモリ | 25,156 KB |
最終ジャッジ日時 | 2024-08-25 14:11:26 |
合計ジャッジ時間 | 16,048 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
import std;void main () {int N, M, K; readln.read(N, M, K);auto A = new int[][](N, 0);foreach (i; 0..N) A[i] = readln.split.to!(int[]);// 上下左右に動けることを誤読していた...// x未満に動くかどうか?で01bfsをすればよいですね。auto dp = new int[][](N, M);auto q = DList!(Tuple!(int, int))();const dxy = [[0, 1],[0, -1],[1, 0],[-1, 0],];bool is_in (int y, int x) {return 0 <= y && y < N && 0 <= x && x < M;}bool f (int bord) {foreach (d; dp) d[] = int.max;dp[0][0] = 0;if (A[0][0] < bord) dp[0][0] = 1;q.insertBack(tuple(0, 0));while (!q.empty()) {auto pos = q.front(); q.removeFront();int y = pos[0], x = pos[1];foreach (d; dxy) {int ny = y + d[0], nx = x + d[1];if (!is_in(ny, nx)) continue;if (dp[ny][nx] < int.max) continue;// コスト0遷移if (bord <= A[ny][nx]) {dp[ny][nx] = dp[y][x];q.insertFront(tuple(ny, nx));}// コスト1遷移if (A[ny][nx] < bord) {dp[ny][nx] = dp[y][x] + 1;q.insertBack(tuple(ny, nx));}}}return dp[N - 1][M - 1] <= K;}int ok = 1, ng = 10 ^^ 9 + 1;while (1 < abs(ok - ng)) {int mid = (ok + ng) / 2;if (f(mid)) {ok = mid;}else {ng = mid;}}writeln(ok);}void read (T...) (string S, ref T args) {import std.conv : to;import std.array : split;auto buf = S.split;foreach (i, ref arg; args) {arg = buf[i].to!(typeof(arg));}}