poj 3414 Pots（广搜BFS+路径输出）

转载请注明出处：http://blog.csdn.net/u012860063?viewmode=contents

此题和poj1606一样：http://blog.csdn.net/u012860063/article/details/37772275

题目大意：

有二个水壶，对水壶有三种操作：

1)FILL(i)，将i水壶的水填满；

2)DROP(i)，将水壶i中的水全部倒掉；

3)POUR(i,j)将水壶i中的水倒到水壶j中，若水壶 j 满了，则 i 剩下的就不倒了，问进行多少步操作，并且怎么操作，输出操作的步骤，两个水壶中的水可以达到C这个水量。如果不可能则输出impossible。初始时两个水壶是空的，没有水。

思路：

直接BFS就可以了。但是难点是记录路径。

我的方法是用一个 path[]结构体数组记录入队的节点，用pre记录其前一步的下标，然后输出的时候，从最后一个状态一直找到开始状态。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 #include <stack>
  6 using namespace std;
  7 #define N 10000
  8 
  9 int a,b,c;
 10 struct node
 11 {
 12     int l,r,step,flag;//l为左容器，r右容器，step步数，flag为操作
 13     int pre;//记录前驱
 14 };
 15 bool vis[250][250];//访问标记数组
 16 stack<int> s;
 17 void print()
 18 {
 19     while (!s.empty())
 20     {
 21         int i=s.top();
 22         switch (i)
 23         {
 24         case 0:
 25             printf("FILL(1)
");
 26             break;
 27         case 1:
 28             printf("FILL(2)
");
 29             break;
 30         case 2:
 31             printf("DROP(1)
");
 32             break;
 33         case 3:
 34             printf("DROP(2)
");
 35             break;
 36         case 4:
 37             printf("POUR(2,1)
");//注意审题，是从左边倒到右边！！！
 38             break;
 39         case 5:
 40             printf("POUR(1,2)
");
 41             break;
 42         }
 43         s.pop();//记得出栈！！！
 44     }
 45 }
 46 void bfs()
 47 {
 48     node n;
 49     n.l=n.r=n.step=0;
 50     n.flag=7;
 51     n.pre=-1;
 52     queue<node> q;
 53     q.push(n);
 54     node path[N];
 55     int ind=0;//注意要给初值
 56     memset(vis,0,sizeof(vis));
 57     while (!q.empty())
 58     {
 59         path[ind]=q.front();
 60         ind++;
 61         n=q.front();
 62         vis[n.l][n.r]=1;
 63         q.pop();
 64         int i;
 65         node nn;
 66         for (i=0;i<6;i++)
 67         {
 68             switch(i)
 69             {
 70                 case 0:
 71                     nn.l=a;
 72                     nn.r=n.r;
 73                     nn.flag=0;
 74                     break;
 75                 case 1:
 76                     nn.l=n.l;
 77                     nn.r=b;
 78                     nn.flag=1;
 79                     break;
 80                 case 2:
 81                     nn.l=0;
 82                     nn.r=n.r;
 83                     nn.flag=2;
 84                     break;
 85                 case 3:
 86                     nn.l=n.l;
 87                     nn.r=0;
 88                     nn.flag=3;
 89                     break;
 90                 case 4:
 91                     nn.l=min(a,n.r+n.l);
 92                     nn.r=max(0,n.r-(a-n.l));
 93                     nn.flag=4;
 94                     break;
 95                 case 5:
 96                     nn.l=max(0,n.l-(b-n.r));
 97                     nn.r=min(b,n.r+n.l);
 98                     nn.flag=5;
 99                     break;
100             }
101             nn.step=n.step+1;
102             nn.pre=ind-1;//不是ind，因为ind之前已经自加过了！！！
103             if (nn.l==c||nn.r==c)
104             {
105                 printf("%d
",nn.step);
106                 while (nn.pre!=-1)
107                 {
108                     s.push(nn.flag);
109                     nn=path[nn.pre];
110                 }
111                 print();
112                 return;
113             }
114             if (vis[nn.l][nn.r]==1)
115             {
116                 continue;
117             }
118             vis[nn.l][nn.r]=1;
119             q.push(nn);
120         }
121     }
122     printf("impossible
");
123 }
124 
125 int main()
126 {
127     while (scanf("%d %d %d",&a,&b,&c)!=EOF)
128     {
129         bfs();
130     }
131 
132     return 0;
133 }