結果
問題 | 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 longtemplate<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;}