結果
問題 | No.1638 Robot Maze |
ユーザー |
![]() |
提出日時 | 2021-06-27 11:24:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,921 bytes |
コンパイル時間 | 2,447 ms |
コンパイル使用メモリ | 114,300 KB |
最終ジャッジ日時 | 2025-01-22 13:51:20 |
ジャッジサーバーID (参考情報) |
judge1 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 WA * 10 |
ソースコード
//元のwriter解嘘でした #include <iostream> #include <vector> #include <queue> #include <utility> #include <stdio.h> #include <algorithm> #include <string> #include <math.h> using namespace std; #define ll long long #define Pll pair<ll,ll> typedef struct edge{ ll to; ll cost; }Edge; typedef pair<int,int> P; long long INF=1000000000000000000; int V; vector<Edge> G[10000]; long long d[10000]; vector<ll> defa; void dijkstra(ll s){ priority_queue<P,vector<P>,greater<P>> que; fill(d,d+V,INF); d[s]=0; que.push(P(0,s)); while(!que.empty()){ P p=que.top();que.pop(); int v=p.second; if(d[v]<p.first)continue; for(unsigned int i=0;i<G[v].size();i++){ Edge e=G[v][i]; if(d[e.to]>d[v]+e.cost){ d[e.to]=d[v]+e.cost; que.push(P(d[e.to],e.to)); } } } } ostream& operator<<(ostream& os,vector<Edge>& a){ for(Edge e:a){ os<<"to:"<<e.to<<",cots:"<<e.cost<<" "; } return os; } ostream& operator<<(ostream& os,vector<Pll>& a){ for(Pll i:a){ os<<"("<<i.first<<","<<i.second<<") , "; } return os; } ostream& operator<<(ostream& os,vector<string>& a){ for(string i:a){ os<<i<<"\n"; } return os; } ll H,W,U,D,R,L,K,xs,ys,xt,yt,cnt,m,ans,x,y,co,Po; vector<string>C; vector<Pll> B; vector<Pll> u; int main(){ cnt=0; ans=INF; cin>>H>>W>>U>>D>>R>>L>>K; cin>>Po; cin>>xs>>ys>>xt>>yt; V=H*W;//don't forget co=(U+1)*(D+1)*(R+1)*(L+1); C.resize(H); defa.resize(V); for(int i=0;i<H;i++){ cin>>C.at(i); for(int j=0;j<W;j++){ if(C.at(i).at(j)=='@')B.push_back({i,j}); } C.at(i).append("#"); } string s; for(int i=0;i<W;i++)s.append("#"); C.push_back(s); //cin>>xs>>ys>>xt>>yt; xs--;ys--;xt--;yt--; for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(C.at(i).at(j)=='#')continue; if(C.at(i).at(j)=='@')continue; if(C.at(i+1).at(j)=='.'){ //cerr<<i<<" "<<j<<"push_back tate\n"; G[W*i+j].push_back({W*(i+1)+j,D}); G[W*(i+1)+j].push_back({W*i+j,U}); } if(C.at(i).at(j+1)=='.'){ //cerr<<i<<" "<<j<<"push_back yoko\n"; G[W*i+j].push_back({W*i+j+1,R}); G[W*i+j+1].push_back({W*i+j,L}); } } } for(int i=0;i<V;i++){ defa.at(i)=G[i].size(); } cnt=B.size(); m=pow(2,cnt); //cerr<<cnt<<" "<<m<<endl; for(int i=0;i<m;i++){ u.clear(); ll debug1=0,debug2=0; for(int j=0;j<cnt;j++){ if((i>>j)&1){ x=B.at(j).first; y=B.at(j).second; u.push_back({x,y}); C.at(x).at(y)='.'; debug1++; } } for(int j=0;j<cnt;j++){ if((i>>j)&1){ x=B.at(j).first; y=B.at(j).second; debug2++; if(C.at(x+1).at(y)=='.'){ G[W*x+y].push_back({W*(x+1)+y,D}); G[W*(x+1)+y].push_back({W*x+y,U}); } if(C.at(x).at(y+1)=='.'){ G[W*x+y].push_back({W*x+y+1,R}); G[W*x+y+1].push_back({W*x+y,L}); } if(x>0 && C.at(x-1).at(y)=='.'){ G[W*x+y].push_back({W*(x-1)+y,U}); G[W*(x-1)+y].push_back({W*x+y,D}); } if(y>0 && C.at(x).at(y-1)=='.'){ G[W*x+y].push_back({W*x+y-1,L}); G[W*x+y-1].push_back({W*x+y,R}); } } } dijkstra(W*xs+ys); // if(d[W*xt+yt]<INF){ // //cerr<<d[W*xt+yt]<<","<<(ll)u.size()<<endl; // //cerr<<u<<endl; // cout<<"size:"<<u.size()<<endl; // cout<<debug1<<" "<<debug2<<endl; // cout<<C<<endl; // for(int k=0;k<V;k++){ // cout<<"i:"<<k<<endl; // cout<<G[k]<<endl; // } // } ans=min(ans,d[W*xt+yt]+(ll)u.size()*co); //cerr<<u.size()<<" "<<d[W*xt+yt]<<endl; for(int i=0;i<V;i++){ while(G[i].size()>defa.at(i)){ G[i].pop_back(); } } for(Pll j:u){ C.at(j.first).at(j.second)='@'; } } if(ans<=K)cout<<"Yes\n"; else cout<<"No\n"; cerr<<"ans:"<<ans<<endl; return 0; }