NYOJ21 三个水杯

三个水杯

时间限制：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

这题和前两天写的 poj 中jugs那道题思路一样，用 队列 加上 搜索 搞定

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 
  6 using namespace std;
  7 
  8 int va, vb, vc, ta, tb, tc;
  9 bool visit[205][205][205];
 10 struct state
 11 {
 12     int a;
 13     int b;
 14     int c;
 15     int step;
 16 };
 17 
 18 inline bool check(state t)
 19 {
 20     if(t.a == ta && t.b == tb && t.c == tc)
 21         return true;
 22     return false;
 23 }
 24 
 25 int BFS(int sa, int sb, int sc)
 26 {
 27     queue <state> q;
 28     state t1, t2;
 29     t1.a = sa;
 30     t1.b = sb;
 31     t1.c = sc;
 32     t1.step = 0;
 33     q.push(t1);
 34     while(!q.empty())
 35     {
 36         t1 = q.front();
 37         q.pop();
 38         if(t1.b != vb && t1.a)               //  pour va to vb
 39         {
 40             if(t1.a <= vb - t1.b)
 41             {
 42                 t2.a = 0;
 43                 t2.b = t1.b + t1.a;
 44                 t2.c = t1.c;
 45             }
 46             else
 47             {
 48                 t2.a = t1.a - (vb - t1.b);
 49                 t2.b = vb;
 50                 t2.c = t1.c;
 51             }
 52             if(!visit[t2.a][t2.b][t2.c])
 53             {
 54                 t2.step = t1.step + 1;
 55                 if(check(t2))
 56                     return t2.step;
 57                 visit[t2.a][t2.b][t2.c] = true;
 58                 q.push(t2);
 59             }
 60         }
 61         if(t1.c != vc && t1.a)               //  pour va to vc
 62         {
 63             if(t1.a <= vc - t1.c)
 64             {
 65                 t2.a = 0;
 66                 t2.b = t1.b;
 67                 t2.c = t1.c + t1.a;
 68             }
 69             else
 70             {
 71                 t2.a = t1.a - (vc - t1.c);
 72                 t2.b = t1.b;
 73                 t2.c = vc;
 74             }
 75             if(!visit[t2.a][t2.b][t2.c])
 76             {
 77                 t2.step = t1.step + 1;
 78                 if(check(t2))
 79                     return t2.step;
 80                 visit[t2.a][t2.b][t2.c] = true;
 81                 q.push(t2);
 82             }
 83         }
 84         if(t1.a != va && t1.b)               //  pour vb to va
 85         {
 86             if(t1.b <= va - t1.a)
 87             {
 88                 t2.b = 0;
 89                 t2.a = t1.b + t1.a;
 90                 t2.c = t1.c;
 91             }
 92             else
 93             {
 94                 t2.b = t1.b - (va - t1.a);
 95                 t2.a = va;
 96                 t2.c = t1.c;
 97             }
 98             if(!visit[t2.a][t2.b][t2.c])
 99             {
100                 t2.step = t1.step + 1;
101                 if(check(t2))
102                     return t2.step;
103                 visit[t2.a][t2.b][t2.c] = true;
104                 q.push(t2);
105             }
106         }
107         if(t1.a != va && t1.b)               //  pour vb to vc
108         {
109             if(t1.b <= vc - t1.c)
110             {
111                 t2.b = 0;
112                 t2.a = t1.a;
113                 t2.c = t1.b + t1.c;
114             }
115             else
116             {
117                 t2.b = t1.b - (vc - t1.c);
118                 t2.a = t1.a;
119                 t2.c = vc;
120             }
121             if(!visit[t2.a][t2.b][t2.c])
122             {
123                 t2.step = t1.step + 1;
124                 if(check(t2))
125                     return t2.step;
126                 visit[t2.a][t2.b][t2.c] = true;
127                 q.push(t2);
128             }
129         }
130         if(t1.a != va && t1.c)               //  pour vc to va
131         {
132             if(t1.c <= va - t1.a)
133             {
134                 t2.c = 0;
135                 t2.a = t1.a + t1.c;
136                 t2.b = t1.b ;
137             }
138             else
139             {
140                 t2.c = t1.c - (va - t1.a);
141                 t2.a = va;
142                 t2.b = t1.b;
143             }
144             if(!visit[t2.a][t2.b][t2.c])
145             {
146                 t2.step = t1.step + 1;
147                 if(check(t2))
148                     return t2.step;
149                 visit[t2.a][t2.b][t2.c] = true;
150                 q.push(t2);
151             }
152         }
153         if(t1.b != vb && t1.c)               //  pour vc to vb
154         {
155             if(t1.c <= vb - t1.b)
156             {
157                 t2.c = 0;
158                 t2.b = t1.b + t1.c;
159                 t2.a = t1.a ;
160             }
161             else
162             {
163                 t2.c = t1.c - (vb - t1.b);
164                 t2.b = vb;
165                 t2.a = t1.a;
166             }
167             if(!visit[t2.a][t2.b][t2.c])
168             {
169                 t2.step = t1.step + 1;
170                 if(check(t2))
171                     return t2.step;
172                 visit[t2.a][t2.b][t2.c] = true;
173                 q.push(t2);
174             }
175         }
176     }
177     return -1;
178 }
179 
180 int main()
181 {
182     int T;
183     scanf("%d", &T);
184     while(T--)
185     {
186         memset(visit, false, sizeof(visit));
187         scanf("%d %d %d", &va, &vb, &vc);
188         scanf("%d %d %d", &ta, &tb, &tc);
189         if(va == ta && 0 == tb && 0 == tc)
190         {
191             printf("0\n");
192             continue;
193         }
194         visit[va][0][0] = true;
195         printf("%d\n", BFS(va, 0, 0));
196     }
197     //system("pause");
198     return 0;
199 }

这是本题OJ上的最优代码：---好短

 1  
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<bitset>
 7 using namespace std;
 8 #define CLR(arr,val) memset(arr,val,sizeof(arr))
 9 bitset<1000000> Hash;
10 const int MAX_STEP=100000;
11 int WQ[MAX_STEP][4],Goal[3],Cap[3],goalval;
12 int head=0,tail=0;
13 void movw(int numfrom,int numto,int other)
14 {
15     int total=WQ[head][numfrom]+WQ[head][numto];
16     WQ[tail][other]=WQ[head][other];
17     WQ[tail][3]=WQ[head][3]+1;
18     if(total>Cap[numto])
19     {
20         WQ[tail][numfrom]=total-Cap[numto];
21         WQ[tail][numto]=Cap[numto];
22     }
23     else
24     {
25         WQ[tail][numfrom]=0;
26         WQ[tail][numto]=total;
27     }
28     int hashval=WQ[tail][0]*10000+WQ[tail][1]*100+WQ[tail][2];
29     if(hashval==goalval) throw WQ[head][3]+1;
30     if(WQ[head][numfrom]!=0 && !Hash[hashval]) 
31     {
32         Hash[hashval]=true;
33         if(++tail==MAX_STEP) tail=0;
34     }
35 }
36 int main()
37 {
38     int t;
39     scanf("%d",&t);
40     while(t--)
41     {
42         Hash.reset();
43         scanf("%d%d%d%d%d%d",&Cap[0],&Cap[1],&Cap[2],&Goal[0],&Goal[1],&Goal[2]);
44         head=0,tail=0,goalval=Goal[0]*10000+Goal[1]*100+Goal[2];
45         if(Goal[1]==0 && Goal[2]==0 && Goal[0]==Cap[0]) {puts("0");continue;}
46         WQ[tail][0]=Cap[0];WQ[tail][1]=0;WQ[tail][2]=0;WQ[tail][3]=0;
47         ++tail;
48         try{
49             while(head!=tail)
50             {
51                 movw(0,1,2);movw(1,2,0);movw(0,2,1);movw(1,0,2);movw(2,1,0);movw(2,0,1);
52                 if(++head==MAX_STEP) head=0;
53             }
54             puts("-1");
55         }catch(int step)
56         {
57             printf("%d\n",step);
58         }
59     }
60 }

功不成，身已退