poj 3414 Pots bfs+模拟

 #include<iostream>
#include<cstring>
#define fillA 1
#define pourAB 2
#define dropA 3
#define fillB 4
#define pourBA 5
#define dropB 6 #define N 10000 using namespace std;
int vis[][];
class node
{
public:
int A, B;
int dir;
node()
{
A=;
B=;
}
}; int a, b, c, tot;
node q[N];
int pre[N]; void printPath(int index)
{
if(index==)
{
cout<<tot<<endl;
return ;
}
++tot;
printPath(pre[index]);
switch(q[index].dir)
{
case :
cout<<"FILL(1)";
break;
case :
cout<<"POUR(1,2)";
break;
case :
cout<<"DROP(1)";
break;
case :
cout<<"FILL(2)";
break;
case :
cout<<"POUR(2,1)";
break;
case :
cout<<"DROP(2)";
break;
}
cout<<endl;
} int bfs()
{
int head=, rear=, r;
node cur, next;
memset(vis, , sizeof(vis));
pre[]=;
vis[][]=;
while(head<rear)
{
cur=q[head];
if(cur.A==c || cur.B==c)
{
printPath(head);
return ;
}
next=cur;
if(!vis[a][cur.B])//将 A 装满
{
next.A=a;
next.dir=fillA;
pre[rear]=head;
vis[a][cur.B]=;
q[rear++]=next;
}
if(!vis[][cur.B])//将 A 倒掉
{
next.A=;
next.dir=dropA;
pre[rear]=head;
vis[][cur.B]=;
q[rear++]=next;
}
r=b-cur.B;
next.dir=pourAB;
if(r>cur.A && !vis[][cur.B+cur.A])//将A 倒向 B
{
next.A=;
next.B=cur.B+cur.A;
pre[rear]=head;
q[rear++]=next;
vis[][cur.B+cur.A]=;
}
else if(r<=cur.A && !vis[cur.A-r][cur.B+r])
{
next.A=cur.A-r;
next.B=cur.B+r;
pre[rear]=head;
q[rear++]=next;
vis[cur.A-r][cur.B+r]=;
} next=cur;//开始错在这里了, 忘记了从新给next赋值了
if(!vis[cur.A][b])//将 B 装满
{
next.B=b;
next.dir=fillB;
pre[rear]=head;
q[rear++]=next;
vis[cur.A][b]=;
}
if(!vis[cur.A][])//将 B 倒掉
{
next.B=;
next.dir=dropB;
pre[rear]=head;
q[rear++]=next;
vis[cur.A][]=;
}
r=a-cur.A;
next.dir=pourBA;
if(r>cur.B && !vis[cur.B+cur.A][])//将B 倒向 A
{
next.B=;
next.A=cur.B+cur.A;
pre[rear]=head;
q[rear++]=next;
vis[cur.B+cur.A][]=;
}
else if(r<=cur.B && !vis[cur.A+r][cur.B-r])
{
next.A=cur.A+r;
next.B=cur.B-r;
pre[rear]=head;
q[rear++]=next;
vis[cur.A+r][cur.B-r]=;
}
++head;
}
return ;
} int main()
{
while(cin>>a>>b>>c)
{
tot=;
if(c>a && c>b)
{
cout<<"impossible"<<endl;
continue;
}
if(!bfs())
cout<<"impossible"<<endl;
}
return ;
}
上一篇:用Chrome浏览器模拟手机,android,iphone,ipad访问网站


下一篇:window下mysql数据备份