結果
問題 | No.2855 Move on Grid |
ユーザー |
![]() |
提出日時 | 2024-08-25 15:30:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 185 ms / 3,000 ms |
コード長 | 1,777 bytes |
コンパイル時間 | 3,215 ms |
コンパイル使用メモリ | 256,616 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-25 15:30:42 |
合計ジャッジ時間 | 9,769 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, l, r) for (int i = (int)(l); i<(int)(r); i++) #define ll long long template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;} template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;} const int inf = 1e9; const ll INF = 4e18; vector<int> di = {1, -1, 0, 0}, dj = {0, 0, 1, -1}; int main() { int N, M, K; cin >> N >> M >> K; vector<vector<int>> A(N, vector<int>(M)); rep(i, 0, N) rep(j, 0, M) cin >> A[i][j]; auto isok = [&](int x) -> bool{ deque<pair<int, int>> Q; vector<vector<int>> dist(N, vector<int>(M, -1)); dist[0][0] = (A[0][0] < x? 1 : 0); Q.push_back({0, 0}); while(!Q.empty()) { auto[r, c] = Q.front(); Q.pop_front(); //cout << r << " " << c << " " << dist[r][c] << endl; rep(k, 0, 4) { int ni = r + di[k], nj = c + dj[k]; if (ni < 0 || nj < 0 || ni >= N || nj >= M) continue; if (A[ni][nj] < x) { if (dist[ni][nj] == -1 || chmin(dist[ni][nj], dist[r][c] + 1)) { dist[ni][nj] = dist[r][c] + 1; Q.push_back({ni, nj}); } } else { if (dist[ni][nj] == -1 || chmin(dist[ni][nj], dist[r][c])) { dist[ni][nj] = dist[r][c]; Q.push_front({ni, nj}); } } } } return dist[N-1][M-1] <= K; }; int ng = 1'000'000'001, ok = 1; while(ng-ok > 1) { int mid = (ok+ng)/2; if (isok(mid)) ok = mid; else ng = mid; } cout << ok << endl; }