POJ

Sample Input

3 5 4
Sample Output

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

分析：有一个瓶子A和一个瓶子B，可以有三种操作倒满，倒空，或者把瓶子A倒向瓶子B（或者把瓶子B倒向瓶子A），可以扩展出6种操作，没什么简单的写法，只能一种一种的写.....

广搜，直到一个瓶子里面有C升水，或者倒不出来这种结果，还需要输出到得步骤，可以递归输出路径

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<queue>
  6 #include<stdlib.h>
  7 #include<map>
  8 #include<cmath>
  9 
 10 using namespace std;
 11 
 12 #define N 500
 13 #define INF 0x3f3f3f3f
 14 
 15 int a,b,c;
 16 char A[10][10]= { "FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)" };
 17 
 18 struct no
 19 {
 20     int x,y;
 21 };
 22 
 23 struct node
 24 {
 25     int fx,fy,step,op;
 26 } v[N][N];
 27 
 28 
 29 void dfs(int x,int y)
 30 {
 31     if(x==0&&y==0)
 32         return ;
 33     dfs(v[x][y].fx,v[x][y].fy);
 34 
 35     printf("%s
", A[v[x][y].op]);
 36 }
 37 
 38 void bfs()
 39 {
 40     int i;
 41 
 42     queue<no>Q;
 43     no s,q;
 44     s.x=0;
 45     s.y=0;
 46     v[0][0].step=1;
 47     Q.push(s);
 48 
 49     while(Q.size())
 50     {
 51         s=Q.front();
 52         Q.pop();
 53 
 54         if(s.x==c||s.y==c)
 55         {
 56             printf("%d
", v[s.x][s.y].step-1);
 57             /*?*/
 58             dfs(s.x,s.y);
 59 
 60             return ;
 61         }
 62 
 63         for(i=0; i<6; i++) ///6种情况
 64         {
 65             q=s;
 66 
 67             if(i==0)///FILL(1)
 68                 q.x=a;
 69             else if(i==1)///FILL(2)
 70                 q.y=b;
 71             else if(i==2)///DROP(1)
 72                 q.x=0;
 73             else if(i==3)///DROP(2)
 74                 q.y=0;
 75             else if(i==4)///POUR
 76             {
 77                 ///a倒入b中
 78                 if(q.x+q.y<=b)
 79                 {///a倒完了
 80                     q.y+=q.x;
 81                     q.x=0;
 82                 }
 83                 else///b倒满了
 84                 {
 85                     q.x-=(b-q.y);
 86                     q.y=b;
 87                 }
 88             }
 89             else
 90             {///b倒入a中
 91                 if(q.x+q.y<=a)
 92                 {///b倒完了
 93                     q.x+=q.y;
 94                     q.y=0;
 95                 }
 96                 else
 97                 {///a倒满了
 98                     q.y-=(a-q.x);
 99                     q.x=a;
100                 }
101             }
102 
103             if(v[q.x][q.y].step==0)
104             {
105                 v[q.x][q.y].step=v[s.x][s.y].step+1;
106                 v[q.x][q.y].fx=s.x;
107                 v[q.x][q.y].fy=s.y;
108                 v[q.x][q.y].op=i;
109 
110                 Q.push(q);
111             }
112         }
113     }
114     printf("impossible
");
115 }
116 
117 int main()
118 {
119     while(scanf("%d %d %d", &a,&b,&c) != EOF)
120     {
121         memset(v,0,sizeof(v));
122 
123         bfs();
124     }
125     return 0;
126 }