POJ3414Pots求大神！！

Description

Input

Output

Sample Input

3 5 4

Sample Output

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

这道题我做了好长时间，新手伤不起。。一开始也是有思路，想到了以两个桶中当前的状态逐步搜索，每次可以有6种操作，倒满A，倒满B，倒空A，倒空B，A->B，B->A，只需判断六种操作之后是否被标记过，没被标记就入队，再判断是否已经达到目标，达到目标则记录步数，返回真。

以上思路顺风顺水，可是，题目要求打印具体步骤，想了好半天，还是想不出来，看到网上有保存到达目标每一步的id，很是巧妙，理解了之后就敲了出来。

可是，我只是理解了id数组的意义还有它是如何工作的，如果下次换一种题型，我可能还是不会打印路径，感觉这思想不易想到，尤其是数组里套数组，像我这种新手理解起来都有些困难，能会运用还是要继续继续继续多做题！！

恳请大牛来此寒舍指点新人一二，bfs里打印路径的敲门！！！！小弟在此多谢了！！

#include
#include
struct C
{
int a,b,step,pre,op;
}q[100010];
int a,b,tg,last,ans,vis[105][105],id[100];
int bfs()
{
int frOnt=0,rear=0;
q[rear].a=0;
q[rear].b=0;
q[rear].pre=0;
q[rear++].step=0;
vis[0][0]=1;
while(front {
int na=q[front].a,fa;
int nb=q[front].b,fb;
for(int i=1;i<=6;i++)
{
if(i==1)//倒满A
{
fa=a;
fb=nb;
}
else if(i==2)//倒满B
{
fa=na;
fb=b;
}
else if(i==3)//倒空A
{
fa=0;
fb=nb;
}
else if(i==4)//倒空B
{
fa=na;
fb=0;
}
else if(i==5)//A->B
{
if(na+nb>=b)
{
fa=na+nb-b;
fb=b;
}
else
{
fa=0;
fb=na+nb;
}
}
else//B->A
{
if(na+nb>=a)
{
fa=a;
fb=na+nb-a;
}
else
{
fa=na+nb;
fb=0;
}
}
if(!vis[fa][fb])
{
vis[fa][fb]=1;
q[rear].a=fa;
q[rear].b=fb;
q[rear].step=q[front].step+1;
q[rear].pre=front;
q[rear].op=i;
if(fa==tg || fb==tg)
{
last=rear;
ans=q[rear].step;
return 1;
}
rear++;
}
}
front++;
}
return 0;
}
void printpath() //看了别人的解题报告才来的思路
{
memset(id,0,sizeof(id));
id[ans]=last;
for(int i=ans-1;i>=1;i--)
{
id[i]=q[id[i+1]].pre;
}
for(int i=1;i<=ans;i++)
{
if(q[id[i]].op==1) printf("FILL(1)\n");
else if(q[id[i]].op==2) printf("FILL(2)\n");
else if(q[id[i]].op==3) printf("DROP(1)\n");
else if(q[id[i]].op==4) printf("DROP(2)\n");
else if(q[id[i]].op==5) printf("POUR(1,2)\n");
else printf("POUR(2,1)\n");
}
}
int main()
{
while(~scanf("%d%d%d",&a,&b,&tg))
{
memset(vis,0,sizeof(vis));
if(bfs())
{
printf("%d\n",ans);
printpath();
}
else printf("impossible\n");
}
return 0;
}

POJ 3414 Pots 求大神！！,布布扣,bubuko.com