結果
問題 | No.2855 Move on Grid |
ユーザー |
|
提出日時 | 2024-08-25 14:05:35 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 607 ms / 3,000 ms |
コード長 | 1,242 bytes |
コンパイル時間 | 4,689 ms |
コンパイル使用メモリ | 293,068 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-25 14:05:56 |
合計ジャッジ時間 | 20,481 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;template<class T>using min_priority_queue = priority_queue<T,vector<T>,greater<T>>;constexpr int dx[] = {0, 1, 0, -1};constexpr int dy[] = {-1, 0, 1, 0};int main(){int N, M, K;cin >> N >> M >> K;vector A(N, vector<ll>(M));for(int i=0; i<N; i++){for(int j=0; j<M; j++){cin >> A[i][j];}}auto check = [&](ll m) -> bool{vector cost(N, vector<int>(M));for(int i=0; i<N; i++){for(int j=0; j<M; j++){if(A[i][j]<m) cost[i][j] = 1;}}vector dist(N, vector<int>(M, 1<<30));min_priority_queue<tuple<int,int,int>> que;dist[0][0] = cost[0][0];que.emplace(dist[0][0], 0, 0);while(!que.empty()){auto [d, y, x] = que.top();que.pop();if(dist[y][x]<d) continue;for(int i=0; i<4; i++){int ny = y + dy[i];int nx = x + dx[i];if(clamp(0,ny,N-1)!=ny || clamp(nx,0,M-1)!=nx) continue;int nd = d + cost[ny][nx];if(nd<dist[ny][nx]){dist[ny][nx] = nd;que.emplace(nd, ny, nx);}}}return dist[N-1][M-1]<=K;};ll ok = 0, ng = 1e9 + 1;while(1<abs(ok-ng)){ll mid = (ok+ng)/2;if(check(mid)) ok = mid;else ng = mid;}cout << ok << endl;return 0;}