给了三个木桶的容量,起始状态下C木桶装满,然后三个木桶相互倒牛奶,问当A木桶为空时的C木桶的牛奶体积的可能情况。
直接深度优先搜索,模拟三个木桶相互倒的情况
相互倒得情况本可以写的更简洁,但为了可阅读性我并没有这么干
不过这道题在本机上调试时,我曾将一个我认为无关紧要的地方写错,因为两个数组大小一样,所以在sizeof的括号中写了另外一个,结果却出不了正解。
有机会要好好查查memcyp函数的用法。
/* ID: modengd1 PROG: milk3 LANG: C++ */ #include <iostream> #include <stdio.h> #include <memory.h> bool tag[21]; using namespace std; bool vis[21][21][21]; int buc[3]; void slove(int L[3]) { int Lcopy[3]; if(vis[L[0]][L[1]][L[2]]) return ; vis[L[0]][L[1]][L[2]]=true; //如果A桶空了,则将C桶的数标记 if(L[0]==0) tag[L[2]]=true; for(int i=0;i<3;i++) { for(int j=i+1;j<3;j++) { memcpy(Lcopy,L,sizeof(Lcopy)); //i->j //j还未满,i未空 if(buc[j]!=Lcopy[j]&&Lcopy[i]!=0) { //取j的剩余空间和i的剩余牛奶的最小值 int change=min(Lcopy[i],buc[j]-Lcopy[j]); Lcopy[j]+=change; Lcopy[i]-=change; slove(Lcopy); } memcpy(Lcopy,L,sizeof(Lcopy));//此处我曾将sizeof括号中Lcopy写成L,但跑不对,主观觉着本应该不会影响的。 //j->i //i还未满,j未空 if(buc[i]!=Lcopy[i]&&Lcopy[j]!=0) { //取i的剩余空间和j的剩余牛奶的最小值 int change=min(Lcopy[j],buc[i]-Lcopy[i]); Lcopy[i]+=change; Lcopy[j]-=change; slove(Lcopy); } } } } int main() { freopen("milk3.in","r",stdin); freopen("milk3.out","w",stdout); int L[3]; memset(vis,false,sizeof(vis)); memset(tag,false,sizeof(tag)); scanf("%d%d%d",&buc[0],&buc[1],&buc[2]); L[0]=L[1]=0; L[2]=buc[2]; slove(L); bool isfrist=true; for(int i=0;i<=20;i++) { if(tag[i]) { if(isfrist) { cout<<i; isfrist=false; } else { cout<<‘ ‘<<i; } } } cout<<endl; return 0; }
原文:http://www.cnblogs.com/modengdubai/p/4767066.html