簡單的搜索題，用遞歸實(shí)現(xiàn)就行了，開一個(gè)三維數(shù)組來記錄狀態(tài)是否出現(xiàn)過。一共有六種到牛奶的方法，不過如果某個(gè)瓶子沒空了，那不能到給其他瓶子了。直接代碼(自己先想想) 發(fā)現(xiàn)我插不進(jìn)代碼，以后再貼吧，到時(shí)順便把官方給的方法給貼一下
  MY CODE
1/**//*
2 ID:qcx97811
3 PROG:milk3
4 LANG:C++
5 搜索，主要是判重，這里用了excist數(shù)組
6 當(dāng)excist[i][j][k] = 0時(shí)表示(i,j,k)這個(gè)狀態(tài)沒出現(xiàn)過
7 excist[i][j][k] = 1時(shí)表示(i,j,k)這個(gè)狀態(tài)出現(xiàn)過
8 */
9 #include <iostream>
10#include <string.h>
11#include <stdlib.h>
12#include <algorithm>
13using namespace std;
14int A,B,C;//三個(gè)瓶子的容量
15int ans[22];//記錄結(jié)果
16int idx = 0;
17int excist[22][22][22];//記錄是否出現(xiàn)過
18void work(int a,int b,int c)
19 {//搜索
20 if(excist[a][b][c])//該狀態(tài)已出現(xiàn)過，就直接返回
21 return ;
22 else
23  {//該狀態(tài)沒出現(xiàn)過
24 excist[a][b][c] = 1;//把狀態(tài)置為出現(xiàn)
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));//初始化，全部狀態(tài)都沒訪問過
91 work(a,b,c);//初態(tài)搜索
92 for(int i = 0;i <= C;i++)
93 {
94 if(excist[0][i][C-i])
95 ans[idx++] = C-i;//把結(jié)果放到ans數(shù)組中
96 }
97 sort(ans,ans+idx);//結(jié)果排序
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下面是官方的，另外還有兩個(gè)，我覺得那兩個(gè)和我的思路差不多就不貼了，貼一下二維數(shù)組存狀態(tài)的吧
官方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
|