結果
問題 |
No.2855 Move on Grid
|
ユーザー |
![]() |
提出日時 | 2025-10-04 16:56:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,108 bytes |
コンパイル時間 | 2,726 ms |
コンパイル使用メモリ | 206,924 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-10-04 16:57:09 |
合計ジャッジ時間 | 7,749 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 WA * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long int N,M,K; int INF = 1e18; int dx[4] = {1,0,0,-1}; int dy[4] = {0,1,-1,0}; signed main(){ 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]; int ok = 0; int ng = INF; while(abs(ok - ng) > 1){ int mid = (ok + ng) / 2; deque<pair<int,int>> Q; vector<vector<int>> dist(N,vector<int>(M,INF)); dist[0][0] = (A[0][0] < mid); Q.push_front({0,0}); while(!Q.empty()){ int nowi = Q.front().first; int nowj = Q.front().second; Q.pop_front(); for(int i = 0; i < 4; i++){ int nei = nowi + dx[i]; int nej = nowj + dy[i]; if(0 <= nei && nei < N && 0 <= nej && nej < M){ if(dist[nei][nej] > dist[nowi][nowj] + (A[nei][nej] < mid)){ dist[nei][nej] = dist[nowi][nowj] + (A[nei][nej] < mid); if(A[nei][nej] >= mid) Q.push_front({nei,nej}); else Q.push_back({nei,nej}); } } } if(dist[N-1][M-1] <= K) ok = mid; else ng = mid; } } cout << min(ok,1000000000ll) << "\n"; }