POJ 3414 Pots

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define sc(x) scanf("%d",&(x))
  6 #define pf(x) printf("%d
", x)
  7 #define CL(x, y) memset(x, y, sizeof(x))
  8 using namespace std;
  9 const int MAX = 105;
 10 int front, rear;
 11 int used[MAX][MAX];
 12 char str[6][10]= {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};
 13 struct node
 14 {
 15     int a, b;
 16     int n;
 17     int step;
 18     node *pre;
 19 } Q[MAX*MAX];   //数组模拟队列    queue<Node> q;
 20 void back(node a);
 21 void BFS(int a, int b, int c);
 22 int main()
 23 {
 24     int a,b,c;
 25     CL(used, 0);
 26     sc(a);
 27     sc(b);
 28     sc(c);
 29     BFS(a, b, c);
 30     pf(Q[rear].step);
 31     back(Q[rear]);
 32 }
 33 void back(node a)
 34 {
 35     if(a.pre != NULL)
 36     {
 37         //printf("%s
", str[a.n]);
 38         back(*(a.pre));//递归，找出初始操作
 39         printf("%s
", str[a.n]);
 40     }
 41     return ;
 42 }
 43 void BFS(int a, int b, int c)
 44 {
 45     front = 0;
 46     rear = 0;
 47     Q[front].a = 0;
 48     Q[front].b = 0;
 49     Q[front].pre = NULL;
 50     Q[front].step = 0;
 51     used[0][0] = 1;
 52     rear++;
 53     while(front != rear)
 54     {
 55         node now = Q[front];  //{0, 0, NULL, 0}
 56         used[now.a][now.b] = 1;
 57         if(!used[a][now.b] && now.a!=a)//FILL(1)   将 A 加满
 58         {
 59             Q[rear].n = 0;    //记录执行的操作
 60             Q[rear].step = Q[front].step + 1;     //步骤 +1
 61             Q[rear].a = a;
 62             Q[rear].b = now.b;
 63             Q[rear].pre = &Q[front];
 64             used[a][now.b] = 1;
 65             if(a==c || now.b==c) break; //完成操作
 66             rear++;
 67         }
 68         if(!used[now.a][b] && now.b!=b)//FILL(2)   将 B 加满
 69         {
 70             Q[rear].n = 1;
 71             Q[rear].step = Q[front].step+1;
 72             Q[rear].a = now.a;
 73             Q[rear].b = b;
 74             Q[rear].pre = &Q[front];
 75             used[now.a][b] = 1;
 76             if(now.a==c || b==c) break;
 77             rear++;
 78         }
 79         if(!used[0][now.b] && now.a!=0)//DROP(1)
 80         {
 81             Q[rear].n = 2;
 82             Q[rear].step = Q[front].step + 1;
 83             Q[rear].a = 0;
 84             Q[rear].b = now.b;
 85             Q[rear].pre = &Q[front];
 86             used[0][now.b] = 1;
 87             if(now.b == c) break;//A中没有水
 88             rear++;
 89         }
 90         if(!used[now.a][0] && now.b!=0)//DROP(2)
 91         {
 92             Q[rear].n = 3;
 93             Q[rear].step = Q[front].step + 1;
 94             Q[rear].a = now.a;
 95             Q[rear].b = 0;
 96             Q[rear].pre = &Q[front];
 97             used[now.a][0] = 1;
 98             if(now.a == c) break;//B中没有水
 99             rear++;
100         }
101         int x = now.a < b-now.b ? now.a : b-now.b;
102         if(!used[now.a-x][now.b+x])//POUR(1,2)
103         {
104             Q[rear].n = 4;
105             Q[rear].step = Q[front].step+1;
106             Q[rear].a = now.a - x;
107             Q[rear].b = now.b + x;
108             Q[rear].pre = &Q[front];
109             used[now.a-x][now.b+x] = 1;
110             if(now.a-x==c || now.b+x==c) break;
111             rear++;
112         }
113         int y = a-now.a < now.b ? a-now.a : now.b;//找到与自己本壶最接近的到水量
114         if(!used[now.a+y][now.b-y])//POUR(2,1)
115         {
116             Q[rear].n = 5;
117             Q[rear].step = Q[front].step+1;
118             Q[rear].a = now.a+y;
119             Q[rear].b = now.b-y;
120             Q[rear].pre = &Q[front];
121             used[now.a+y][now.b-y] = 1;
122             if(now.a+y==c || now.b-y==c) break;
123             rear++;
124         }
125         front++;
126     }//跳出循环时， front==rear
127     if(front == rear) printf("impossible
");//条件判断
128 }
View Code
//BFS倒水问题,对于需要打印解得广搜题，必须保存搜索状态和状态的父亲指针，然后逆推，根据状态和状态之间的关系