nyoj 题目21 三个水杯

三个水杯

时间限制：1000 ms | 内存限制：65535 KB

难度：4

描述: 给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。

输入

第一行一个整数N(0<N<50)表示N组测试数据
接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态

输出

每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1

样例输入

样例输出

3
-1

虽然一看就知道用广度优先搜索，但是具体怎么做却还需要动一番脑筋。
代码如下

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 struct Bottle {
 8     int v[3];
 9     int step;
10     Bottle() {};
11     Bottle(int u, int v, int w, int s) {
12         this->v[0] = u; this->v[1] = v; this->v[2] = w;
13         step = s;
14     }
15 };
16 
17 queue <Bottle> bot;
18 int visit[102][102][102];
19 
20 bool isEqual(Bottle p, int e[]) {
21     for(int i = 0; i < 3; i++) {
22         if(p.v[i] != e[i]) {
23             return false;
24         }
25     }
26     return true;
27 }
28 int main(int argc, char const *argv[])
29 {
30     int N;
31     scanf("%d",&N);
32     while(N--) {
33         int v[3];
34         int e[3];
35         scanf("%d %d %d",&v[0],&v[1],&v[2]);
36         scanf("%d %d %d",&e[0],&e[1],&e[2]);
37 
38         while(!bot.empty()) {
39             bot.pop();
40         }
41         memset(visit, 0, sizeof(visit));
42         bot.push(Bottle(v[0],0,0,0));
43 
44         int ans = -1;
45         while(!bot.empty()) {
46             Bottle p = bot.front(); 
47             bot.pop();
48             if(isEqual(p,e)) 
49             {
50                 ans = p.step;
51                 break;
52             }
53             else {
54                 for(int i = 0; i < 3; i++) {
55                     for(int j = 1; j < 3; j++) {
56                         int k = (i+j)%3;
57                         //from i to k
58                         if(p.v[i] > 0 && p.v[k] < v[k]) {
59                             int cha = v[k] - p.v[k];
60                             int pour = min(p.v[i], cha);
61                             Bottle t;
62                             t.v[i] = p.v[i] - pour;
63                             t.v[k] = p.v[k] + pour;
64                             t.v[3-i-k] = p.v[3-i-k];
65                             t.step = p.step+1;
66                             if(visit[t.v[0]][t.v[1]][t.v[2]] != 1) {
67                                 visit[t.v[0]][t.v[1]][t.v[2]] = 1;
68                                 bot.push(t);
69                             }
70                         }
71                     }
72                 }
73             }
74         }
75         printf("%d
", ans);
76 
77     }
78     return 0;
79 }