簡單的搜索題，用遞歸實現就行了，開一個三維數組來記錄狀態是否出現過。一共有六種到牛奶的方法，不過如果某個瓶子沒空了，那不能到給其他瓶子了。直接代碼(自己先想想) 發現我插不進代碼，以后再貼吧，到時順便把官方給的方法給貼一下
  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
|