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

来源

经典题目

上传者

hzyqazasdf



解题：BFS。。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <vector>
 6 #include <climits>
 7 #include <ctype.h>
 8 #include <cmath>
 9 #include <algorithm>
10 #define LL long long
11 using namespace std;
12 const int maxn = 100000;
13 struct CUP {
14     int d[3],step;
15 };
16 CUP cup[maxn],target,initial;
17 int head,tail;
18 bool vis[100][100][100];
19 int bfs() {
20     tail = head = 0;
21     tail++;
22     CUP temp,temp2;
23     int t,i,j;
24     while(head < tail) {
25         temp = cup[head++];
26         if(temp.d[0] == target.d[0] && temp.d[1] == target.d[1] && temp.d[2] == target.d[2]) {
27             return temp.step;
28         }
29         for(i = 0; i < 3; i++) {
30             for(j = 0; j < 3; j++) {
31                 if((i^j) && temp.d[i] && temp.d[j] < initial.d[j]) {
32                     t = min(initial.d[j] - temp.d[j],temp.d[i]);
33                     temp2 = temp;
34                     temp2.step++;
35                     temp2.d[i] -= t;
36                     temp2.d[j] += t;
37                     if(!vis[temp2.d[0]][temp2.d[1]][temp2.d[2]]) {
38                         vis[temp2.d[0]][temp2.d[1]][temp2.d[2]] = true;
39                         cup[tail++] = temp2;
40                     }
41                 }
42             }
43         }
44     }
45     return -1;
46 }
47 int main() {
48     int kase,temp,i,mx,index;
49     scanf("%d",&kase);
50     while(kase--) {
51         mx = -1;
52         for(i = 0; i < 3; i++) {
53             scanf("%d",&initial.d[i]);
54             if(initial.d[i] > mx) mx = initial.d[index = i];
55         }
56         for(i = 0; i < 3; i++)
57             scanf("%d",&target.d[i]);
58         memset(cup,0,sizeof(cup));
59         memset(vis,false,sizeof(vis));
60         cup[0].d[index] = mx;
61         cup[0].step = 0;
62         vis[cup[0].d[0]][cup[0].d[1]][cup[0].d[2]] = true;
63         if(target.d[0] + target.d[1] + target.d[2] != mx){
64             puts("-1");continue;
65         }else printf("%d
",bfs());
66     }
67     return 0;
68 }

View Code