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

  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)\n");
 26             break;
 27         case 1:
 28             printf("FILL(2)\n");
 29             break;
 30         case 2:
 31             printf("DROP(1)\n");
 32             break;
 33         case 3:
 34             printf("DROP(2)\n");
 35             break;
 36         case 4:
 37             printf("POUR(2,1)\n");//注意审题，是从左边倒到右边！！！
 38             break;
 39         case 5:
 40             printf("POUR(1,2)\n");
 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\n",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\n");
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 }