简单的搜索题,用递归实现就行了,开一个三维数组来记录状态是否出现过。一共有六种到牛奶的方法,不过如果某个瓶子没空了,那不能到给其他瓶子了。直接代码(自己先想想) 发现我插不进代码,以后再贴吧,到时顺便把官方给的方法给贴一下
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
|