結果
| 問題 |
No.2855 Move on Grid
|
| コンテスト | |
| ユーザー |
yu23578
|
| 提出日時 | 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";
}
yu23578