Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
表示对于0K的代码很是抑郁。我用的爆搜竟然不超时#include <cstdlib> #include <cstdio> #include <iostream> #include <vector> #include <cstring> #include <stack> #define K 10000 using namespace std; int a,b,c; struct NOTE { int voa,vob,pre,op; }ans; vector<NOTE> q; bool vis[10010000]; void reset() { memset(vis,0,sizeof vis); q.clear(); } NOTE bfs() { NOTE tmp,tp; int num; tmp.voa=0;tmp.vob=0;tmp.pre=-1; vis[a*K+b]=true; q.push_back(tmp); for(int i=0;i<q.size();i++) { NOTE sta=q[i]; tp.voa=a;tp.vob=sta.vob; num=K*tp.voa+tp.vob; if(!vis[num]) { tp.pre=i;tp.op=1; if(tp.vob==c) return tp; q.push_back(tp); vis[num]=true; } tp.voa=sta.voa;tp.vob=b; num=K*tp.voa+tp.vob; if(!vis[num]) { tp.pre=i;tp.op=2; if(tp.vob==c) return tp; q.push_back(tp); vis[num]=true; } tp.voa=0;tp.vob=sta.vob; num=K*tp.voa+tp.vob; if(!vis[num]) { tp.pre=i;tp.op=3; if(tp.vob==c) return tp; q.push_back(tp); vis[num]=true; } tp.voa=sta.voa;tp.vob=0; num=K*tp.voa+tp.vob; if(!vis[num]) { tp.pre=i;tp.op=4; if(tp.vob==c) return tp; q.push_back(tp); vis[num]=true; } if(b-sta.vob>=sta.voa) { tp.voa=0;tp.vob=sta.voa+sta.vob; num=K*tp.voa+tp.vob; if(!vis[num]) { tp.pre=i;tp.op=5; if(tp.vob==c) return tp; q.push_back(tp); vis[num]=true; } } else { tp.voa=sta.voa-(b-sta.vob);tp.vob=b; num=K*tp.voa+tp.vob; if(!vis[num]) { tp.pre=i;tp.op=5; if(tp.vob==c) return tp; q.push_back(tp); vis[num]=true; } } if(a-sta.voa>=sta.vob) { tp.voa=sta.voa+sta.vob;tp.vob=0; num=K*tp.voa+tp.vob; if(!vis[num]) { tp.pre=i;tp.op=6; if(tp.vob==c) return tp; q.push_back(tp); vis[num]=true; } } else { tp.voa=a;tp.vob=sta.vob-(a-sta.voa); num=K*tp.voa+tp.vob; if(!vis[num]) { tp.pre=i;tp.op=6; if(tp.vob==c) return tp; q.push_back(tp); vis[num]=true; } } } } void print() { stack<NOTE> st; NOTE x=ans; for(;;) { st.push(x); x=q[x.pre]; if(x.voa==0&&x.vob==0) break; } while(!st.empty()) { NOTE y=st.top(); st.pop(); if(y.op==1) printf("fill A\n"); if(y.op==2) printf("fill B\n"); if(y.op==3) printf("empty A\n"); if(y.op==4) printf("empty B\n"); if(y.op==5) printf("pour A B\n"); if(y.op==6) printf("pour B A\n"); } printf("success\n"); } int main() { while(scanf("%d%d%d",&a,&b,&c)!=EOF) { reset(); ans=bfs(); print(); } system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator