結果
問題 | No.2855 Move on Grid |
ユーザー |
![]() |
提出日時 | 2024-08-25 13:57:46 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,893 bytes |
コンパイル時間 | 2,177 ms |
コンパイル使用メモリ | 207,644 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-08-25 13:57:55 |
合計ジャッジ時間 | 7,714 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 WA * 4 |
ソースコード
#include<bits/stdc++.h>using namespace std;int H,W,K,A[303][303];int dist[303][303],B[303][303];int dr[4]={1,0,-1,0},dc[4]={0,1,0,-1};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>H>>W>>K;for(int i=1;i<=H;i++)for(int j=1;j<=W;j++)cin>>A[i][j];int L=0,R=int(1e9)+1;while(R-L>1){int mid=(L+R)/2;for(int i=1;i<=W;i++)for(int j=1;j<=W;j++){B[i][j]=A[i][j]<mid;dist[i][j]=1<<30;}dist[1][1]=B[1][1];deque<pair<int,int>>q;q.push_back(make_pair(1,1));while(q.size()){auto[r,c]=q.front();q.pop_front();for(int d=0;d<4;d++){int tr=r+dr[d],tc=c+dc[d];if(1<=tr&&tr<=H&&1<=tc&&tc<=W){if(B[tr][tc]==1){if(dist[tr][tc]>dist[r][c]+1){dist[tr][tc]=dist[r][c]+1;q.push_back(make_pair(tr,tc));}}else{if(dist[tr][tc]>dist[r][c]){dist[tr][tc]=dist[r][c];q.push_front(make_pair(tr,tc));}}}}}// cout<<"mid = "<<mid<<endl;// for(int i=1;i<=H;i++)// {// for(int j=1;j<=W;j++)cout<<B[i][j]<<' ';// cout<<endl;// }// for(int i=1;i<=H;i++)// {// for(int j=1;j<=W;j++)cout<<dist[i][j]<<' ';// cout<<endl;// }// cout<<endl;if(dist[H][W]<=K)L=mid;else R=mid;}cout<<L<<endl;}