結果
問題 | No.2913 二次元距離空間 |
ユーザー |
![]() |
提出日時 | 2024-10-06 17:26:20 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 1,428 bytes |
コンパイル時間 | 1,323 ms |
コンパイル使用メモリ | 114,044 KB |
実行使用メモリ | 5,632 KB |
最終ジャッジ日時 | 2024-10-06 17:26:23 |
合計ジャッジ時間 | 2,917 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; using ll = long long; #include<queue> int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int h,w; cin>>h>>w; vector<string> s(h); for(int i = 0;i<h;i++) cin>>s[i]; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; using dat = pair<pair<int,int>,pair<int,int>>; priority_queue<dat,vector<dat>,greater<dat>> que; vector<vector<pair<int,int>>> now(h,vector<pair<int,int>>(w,make_pair(1e9,1e9))); now[0][0] = make_pair(0,0); que.push({{0,0},{0,0}}); while(que.size()){ auto nn = que.top(); que.pop(); int ni = nn.second.first; int nj = nn.second.second; if(now[ni][nj]!=nn.first) continue; for(int k = 0;k<4;k++){ int nni = ni + dx[k]; int nnj = nj + dy[k]; if(nni<0||nni>=h||nnj<0||nnj>=w) continue; if(s[nni][nnj]=='#') continue; int p = nn.first.first; int q = nn.first.second; if(k<=1) q++; else p++; pair<int,int> use = make_pair(p,q); if(now[nni][nnj]<=use) continue; now[nni][nnj] = use; que.push({use,{nni,nnj}}); } } auto ans = now[h-1][w-1]; if(ans.first==1e9) cout<<"No\n"; else{ cout<<"Yes\n"; cout<<ans.first<<" "<<ans.second<<endl; } }