| ||||||||||
| 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