简单的搜索题，用递归实现就行了，开一个三维数组来记录状态是否出现过。一共有六种到牛奶的方法，不过如果某个瓶子没空了，那不能到给其他瓶子了。直接代码(自己先想想) 发现我插不进代码，以后再贴吧，到时顺便把官方给的方法给贴一下
  MY CODE
1/**//*
2 ID:qcx97811
3 PROG:milk3
4 LANG:C++
5 搜索，主要是判重，这里用了excist数组
6 当excist[i][j][k] = 0时表示(i,j,k)这个状态没出现过
7 excist[i][j][k] = 1时表示(i,j,k)这个状态出现过
8 */
9 #include <iostream>
10#include <string.h>
11#include <stdlib.h>
12#include <algorithm>
13using namespace std;
14int A,B,C;//三个瓶子的容量
15int ans[22];//记录结果
16int idx = 0;
17int excist[22][22][22];//记录是否出现过
18void work(int a,int b,int c)
19 {//搜索
20 if(excist[a][b][c])//该状态已出现过，就直接返回
21 return ;
22 else
23  {//该状态没出现过
24 excist[a][b][c] = 1;//把状态置为出现
25 //下面的六种情况分别到牛奶 也就是A-B,A-C,B-A,B-C,C-A,C-B
26 //C-A
27 if(a + c > A)
28 {
29 work(A,b,c+a-A);
30 }
31 else
32 {
33 work(a+c,b,0);
34 }
35 //C-B
36 if(b + c > B)
37 {
38 work(a,B,c+b-B);
39 }
40 else
41 {
42 work(a,b+c,0);
43 }
44 //A-C
45 if(a + c > C)
46 {
47 work(a+c-C,b,C);
48 }
49 else
50 {
51 work(0,b,a+c);
52 }
53 //A-B
54 if(a + b > B)
55 {
56 work(a+b-B,B,c);
57 }
58 else
59 {
60 work(0,a+b,c);
61 }
62 //B-C
63 if(b + c > C)
64 {
65 work(a,b+c-C,C);
66 }
67 else
68 {
69 work(a,0,b+c);
70 }
71 //B-A
72 if(a + b > A)
73 {
74 work(A,a+b-A,c);
75 }
76 else
77 {
78 work(a+b,0,c);
79 }
80 }
81}
82int main(void)
83{
84 freopen("milk3.in","r",stdin);
85 freopen("milk3.out","w",stdout);
86 int a,b,c;
87 scanf("%d %d %d",&A,&B,&C);
88 a = b = 0;
89 c = C;
90 memset(excist,0,sizeof(excist));//初始化，全部状态都没访问过
91 work(a,b,c);//初态搜索
92 for(int i = 0;i <= C;i++)
93 {
94 if(excist[0][i][C-i])
95 ans[idx++] = C-i;//把结果放到ans数组中
96 }
97 sort(ans,ans+idx);//结果排序
98 printf("%d",ans[0]);
99 for(int i = 1;i < idx;i++)
100 printf(" %d",ans[i]);
101 printf("\n");
102 return 0;
103}
104下面是官方的，另外还有两个，我觉得那两个和我的思路差不多就不贴了，贴一下二维数组存状态的吧
官方CODE
1Both other solutions (recursive and non-recursive) use a 3D-array to store the states, so that the memory usage is O(N3). However a 2D Array and O(N2) would be enough since a state is uniquely defined by the amount of milk in bucket B and C. The amount of milk in bucket A is size-of-C minus amount-in-C minus amount-in-B. This solution works with it, and is a little bit shorter (though not more elegant):
2
3#include <stdio.h>
4int A, B, C;
5int CB[21][21]; // All states
6
7void readFile() {
8 FILE *f;
9 f = fopen("milk3.in", "r");
10 fscanf(f, "%d%d%d", &A, &B, &C);
11 fclose(f);
12}
13
14void writeFile() {
15 FILE *f; int i;
16 f = fopen("milk3.out", "w");
17 for(i = 0; i <= C; i++) {
18 if(CB[i][C - i] == 1) {
19 if((i != C-B) && (i != 0)) fprintf(f, " ");
20 fprintf(f, "%d", i);
21 }
22 }
23 fprintf(f, "\n");
24 fclose(f);
25}
26
27// do brute-force search, c/b: current state
28void search(int c, int b) {
29 int a;
30 if(CB[c][b] == 1) return; // already searched
31 CB[c][b] = 1;
32 a = C-b-c; // calc amount in A
33 // do all moves:
34 // c->b
35 if(B < c+b) search(c - (B - b), B);
36 else search(0, c + b);
37 // b->c
38 if(C < c+b) search(C, b - (C - c));
39 else search(c + b, 0);
40 // c->a
41 if(A < c+a) search(c - (A - a), b);
42 else search(0, b);
43 // a->c
44 if(C < c+a) search(C, b);
45 else search(c + a, b);
46 // b->a
47 if(A < b+a) search(c, b - (A - a));
48 else search(c, 0);
49 // a->b
50 if(B < b+a) search(c, B);
51 else search(c, b + a);
52 }
53
54int main () {
55 readFile();
56 search(C, 0);
57 writeFile();
58 return 0;
59}
60
61
|