POJ 3414

这是一个广搜的题目，不难，就是有些许麻烦。对于练习还是个不错的题目。
题意就是给你两个杯子，这两个杯子的容量分别为a和b，要你通过一些操作，量出c那么多的水来。
fill就是填满那个杯子。无论杯子是否油水
prou（2，1）就是从第二个杯子向第一个杯子里倒水，当第一个满了或者第二个杯子是空的为止。
drop就是把这个杯子里的水都给倒掉。
  1 #include <cstdio>
  2 #include <iostream>
  3 #include <string>
  4 #include <string.h>
  5 #include <queue>
  6 
  7 using namespace std;
  8 
  9 #define judge(x,y) x>=0&&y>=0&&x<=a&&y<=b&&mark[x][y]   //一个判断，也是减少代码量，虽然我这个代码写的还是比较渣，很多东西都要一个一个些。其实完全可以套用模板来搞。
 10 int a,b,c,flog;
 11 
 12 
 13 struct note{
 14     int x,y,step,pos,i;  //step记录当前的步数，pos记录上一步。然后可以进行回溯吧。 
 15     char str[10];     //进行储存这一步的具体操作。
 16 };
 17 
 18 bool mark[105][105];     //代表这个点是否以前出现过。
 19 
 20 char ans[1000][10];
 21 queue<note>s;
 22 
 23 void bfs(int x,int y)
 24 {
 25     note p[10000],q;   
 26     while(!s.empty())
 27         s.pop();
 28     strcpy(p[0].str,"ssss");    //我这个目的完全是为了然s不为空的，因为如果p[0]没有值的话，p[0]是进不了队列的。
 29     p[0].pos=0,p[0].x=0,p[0].y=0,p[0].step=0,p[0].i=0;
 30     s.push(p[0]);
 31     int k=0;
 32     while(!s.empty())
 33     {
 34         q=s.front();
 35         s.pop();
 36         if(q.x==c||q.y==c){    //当量出了那么多的水的时候，就输出答案。
 37             flog=1;             //这个是为了确定找到了答案。
 38             printf("%d
",q.step);  //
 39             int m=0;
 40             strcpy(ans[m],q.str);
 41             m++;
 42             for(int i=q.pos;i!=0;)  //回溯步骤。
 43             {
 44                 strcpy(ans[m],p[i].str);
 45                 m++;
 46                 i=p[i].pos;
 47             }
 48             while(m--)  //倒叙输出答案。
 49                 printf("%s
",ans[m]);  
 50             return ;
 51         }
 52         if(judge(a,q.y))
 53         {
 54             p[++k].x=a;  
 55             p[k].y=q.y;
 56             p[k].pos=q.i;
 57             p[k].i=k;
 58             strcpy(p[k].str,"FILL(1)");
 59             mark[a][q.y]=false;
 60             p[k].step=q.step+1;
 61             s.push(p[k]);
 62         }
 63         if(judge(q.x,b))
 64         {
 65             p[++k].x=q.x;
 66             p[k].y=b;
 67             p[k].pos=q.i;
 68             p[k].i=k;
 69             strcpy(p[k].str,"FILL(2)");
 70             mark[q.x][b]=false;
 71             p[k].step=q.step+1;
 72             s.push(p[k]);
 73         }
 74         if(judge(0,q.y))
 75         {
 76             p[++k].x=0;
 77             p[k].y=q.y;
 78             p[k].pos=q.i;
 79             p[k].i=k;
 80             strcpy(p[k].str,"DROP(1)");
 81             mark[0][q.y]=false;
 82             p[k].step=q.step+1;
 83             s.push(p[k]);
 84         }
 85         if(judge(q.x,0))
 86         {
 87             p[++k].x=q.x;
 88             p[k].y=0;
 89             p[k].pos=q.i;
 90             p[k].i=k;
 91             strcpy(p[k].str,"DROP(2)");
 92             mark[q.x][0]=false;
 93             p[k].step=q.step+1;
 94             s.push(p[k]);
 95         }
 96         if(q.x+q.y>=a&&judge(a,q.y+q.x-a))
 97         {
 98             p[++k].x=a;
 99             p[k].y=q.y+q.x-a;
100             p[k].pos=q.i;
101             p[k].i=k;
102             strcpy(p[k].str,"POUR(2,1)");
103             mark[a][q.x+q.y-a]=false;
104             p[k].step=q.step+1;
105             s.push(p[k]);
106         }
107         if(q.x+q.y<a&&judge(q.x+q.y,0))
108         {
109             p[++k].x=q.x+q.y;
110             p[k].y=0;
111             p[k].pos=q.i;
112             p[k].i=k;
113             strcpy(p[k].str,"POUR(2,1)");
114             mark[q.x+q.y][0]=false;
115             p[k].step=q.step+1;
116             s.push(p[k]);
117         }
118         if(q.x+q.y>=b&&judge(q.x+q.y-b,b))
119         {
120             p[++k].x=q.x+q.y-b;
121             p[k].y=b;
122             p[k].pos=q.i;
123             p[k].i=k;
124             strcpy(p[k].str,"POUR(1,2)");
125             mark[q.x+q.y-b][b]=false;
126             p[k].step=q.step+1;
127             s.push(p[k]);
128         }
129         if(q.x+q.y<b&&judge(0,q.x+q.y))
130         {
131             p[++k].x=0;
132             p[k].y=q.x+q.y;
133             p[k].pos=q.i;
134             p[k].i=k;
135             strcpy(p[k].str,"POUR(1,2)");
136             mark[0][q.x+q.y]=false;
137             p[k].step=q.step+1;
138             s.push(p[k]);
139         }
140     }
141 }
142 
143 int main()
144 {
145     while(scanf("%d%d%d",&a,&b,&c)!=EOF)
146     {
147         flog=0;
148         memset(mark,true,sizeof(mark));
149         bfs(0,0);
150         if(!flog) printf("impossible
"); 
151     }
152     return 0;
153 }