結果
問題 |
No.2855 Move on Grid
|
ユーザー |
![]() |
提出日時 | 2024-08-25 19:10:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 184 ms / 3,000 ms |
コード長 | 1,535 bytes |
コンパイル時間 | 2,060 ms |
コンパイル使用メモリ | 205,912 KB |
最終ジャッジ日時 | 2025-02-24 02:08:57 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<int> di = {-1, 0, 1, 0}; vector<int> dj = {0, 1, 0, -1}; int main() { int n, m, k; cin >> n >> m >> k; vector<vector<int>> a(n, vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; } } auto inc = [&](int i, int j) { return (0 <= i && i < n && 0 <= j && j < m); }; int l = 1, r = 1000000001; while (r - l > 1) { int mid = (l + r) / 2; deque<pair<int, int>> d; vector<vector<int>> cnt(n, vector<int>(m, 2000000000)); d.push_front({0, 0}); cnt[0][0] = (a[0][0] < mid); while (!d.empty()) { auto [i, j] = d.front(); d.pop_front(); for (int k = 0; k < 4; k++) { int ni = i + di[k], nj = j + dj[k]; if (!inc(ni, nj)) { continue; } if (a[ni][nj] >= mid) { if (cnt[ni][nj] > cnt[i][j]) { cnt[ni][nj] = cnt[i][j]; d.push_front({ni, nj}); } } else { if (cnt[ni][nj] > cnt[i][j] + 1) { cnt[ni][nj] = cnt[i][j] + 1; d.push_back({ni, nj}); } } } } if (cnt[n - 1][m - 1] <= k) { l = mid; } else { r = mid; } } cout << l << endl; }