本文主要是介绍【BFS】母亲的牛奶，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
农夫约翰有三个容量分别为 A,B,C升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。
请你编写一个程序判断，当 A 桶是空的时候，C 桶中可能包含多少升牛奶，找出所有的可能情况。
输入格式
共一行，包含三个整数 A,B,C
输出格式
共一行，包含若干个整数，表示 C桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
数据范围
1≤A,B,C≤20
输入样例1：
8 9 10
输出样例1：
1 2 8 9 10
输入样例2：
2 5 10
输出样例2：
5 6 7 8 9 10
#include<iostream>
#include<algorithm>
#define N 21
#define M N*N*N
using namespace std;int A,B,C;struct Node{int a,b,c;
}q[M];
bool st[N][N][N];//标记有无被遍历
void bfs(){int hh=0,tt=0;q[0]={0,0,C};//刚开始只有c桶有st[0][0][C]=true;int Ws[3]={A,B,C};//表示总容量while(hh<=tt){auto t=q[hh++];for(int i=0;i<3;i++){for(int j=0;j<3;j++){if(i!=j){//从i桶往j桶倒int w[3]={t.a,t.b,t.c};//现在每个容器已有的量int r=min(w[i],Ws[j]-w[j]);//i桶的全部和j桶所剩容量的最小值w[i]-=r,w[j]+=r;int a=w[0],b=w[1],c=w[2];if(!st[a][b][c]){st[a][b][c]=true;q[++tt]={a,b,c};}}}}}}
int main(){cin>>A>>B>>C;bfs();for(int c=0;c<=C;c++){for(int b=0;b<=B;b++){if(st[0][b][c]){//可以枚举到cout<<c<<" ";break;}}}return 0;
}这篇关于【BFS】母亲的牛奶的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
