結果
問題 | No.2855 Move on Grid |
ユーザー |
![]() |
提出日時 | 2024-07-15 09:01:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 98 ms / 3,000 ms |
コード長 | 1,570 bytes |
コンパイル時間 | 936 ms |
コンパイル使用メモリ | 89,196 KB |
最終ジャッジ日時 | 2025-02-23 15:44:14 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include <deque>#include <vector>#include <iostream>#include <algorithm>using namespace std;struct cell {int x, y;};int main() {// step #1. inputint 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];}}// step #2. compressionvector<int> cand(N * M + 1);for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cand[i * M + j] = A[i][j];}}cand[N * M] = 1'000'000'000;sort(cand.begin(), cand.end());// step #3. bfsauto bfs = [&](int b) -> int {const int INF = 1012345678;const vector<cell> dir = {cell{1, 0}, cell{0, 1}, cell{-1, 0}, cell{0, -1}};vector<vector<int> > d(N, vector<int>(M, INF));d[0][0] = (A[0][0] < b ? 1 : 0);deque<cell> que;que.push_back(cell{0, 0});while (!que.empty()) {cell c = que.front();que.pop_front();for (int i = 0; i < 4; i++) {cell nc = cell{c.x + dir[i].x, c.y + dir[i].y};if (0 <= nc.x && nc.x < N && 0 <= nc.y && nc.y < M) {int f = (A[nc.x][nc.y] < b ? 1 : 0);int nd = d[c.x][c.y] + f;if (d[nc.x][nc.y] > nd) {d[nc.x][nc.y] = nd;if (f == 1) {que.push_back(nc);} else {que.push_front(nc);}}}}}return d[N - 1][M - 1];};// step #3. binary searchint l = 0, r = N * M + 1;while (r - l > 1) {int m = (l + r) / 2;int res = bfs(cand[m]);if (res <= K) {l = m;} else {r = m;}}// step #4. outputcout << cand[l] << endl;return 0;}