[宽度优先搜索BFS]母亲的牛奶
题目描述
农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数， 最初，A和B桶都是空的，而C桶是装满牛奶的。有时，农民把牛奶从一个桶倒到 另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约， 牛奶不会有丢失。写一个程序去帮助农民找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。
输入
单独的一行包括三个整数A,B和C。
输出
只有一行，升序地列出当A桶是空的时候，C桶牛奶所剩量的所有可能性。
样例输入
8 9 10
样例输出
1 2 8 9 10
参考了某些大佬DFS的解法，看不懂，穷举：A给B倒，A给C倒，B给C倒，这三种再反过来，就一共是6种倒法，然后每种操作有两个情况，比如，A向B倒，一种情况是A倒干净了，还有一种情况是A没倒干净，B已经满了。
下面上代码。
#include<bits/stdc++.h>
using namespace std;
int d[10005][4];
int n[10005];
bool bz[20][20][20];
int a[4];
void dg()
{
int head=0,tail=1;
d[1][1]=d[1][2]=0;
d[1][3]=a[3];
bz[0][0][a[3]]=1;
while(head<tail)
{
head++;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
if(d[tail][1]==0)
{
n[d[tail][3]]++;
}
if(i!=j && d[head][i]>0 && d[head][j]<a[j])
{
tail++;
int z=6-i-j;
d[tail][z]=d[head][z];
if(d[head][i]<(a[j]-d[head][j]))
{
d[tail][i]=0;
d[tail][j]=d[head][j]+d[head][i];
}
else
{
d[tail][i]=d[head][i]-(a[j]-d[head][j]);
d[tail][j]=a[j];
}
if(bz[d[tail][1]][d[tail][2]][d[tail][3]])
{
tail--;
}
else
{
bz[d[tail][1]][d[tail][2]][d[tail][3]]=1;
}
}
}
}
}
}
int main()
{
cin>>a[1]>>a[2]>>a[3];
dg();
for(int i=0;i<=10005;i++)
{
if(n[i]>=1)
{
cout<<i<<" ";
}
}
} 在CSDN博客上也有发布：http://t.csdn.cn/iYYDS
查看11道真题和解析