蓝桥杯真题——约翰的牛奶

输入样例：

8 9 10

输出样例：

1 2 8 9 10

本题是宽搜的模版题，不论怎么倒牛奶，A,B,C 桶里的牛奶可以看做一个三元点集

我们只要找到A桶是空的，B,C桶中的状态即可

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N= 21,M = N*N*N;
int A,B,C;
// 定义结构体，记录队列中三个桶牛奶情况 
struct Node
{int a,b,c;
}node[M];
// 每个桶中有多少牛奶的情况 
bool vis[N][N][N];void bfs()
{int hh=0,tt=0;// 最开始的状态，C桶是满的 node[0] = {0,0,C};// W 记录三个桶的容量 int W[3] = {A,B,C};// 标记初始情况，C桶中是满的 vis[0][0][C] = true;while(hh<=tt){auto t = node[hh++];// 有三个桶可以选择，并且可以向另外的桶倒牛奶 for(int i=0;i<3;i++){for(int j=0;j<3;j++){if(i!=j){// w 记录现在三个桶中的牛奶有多少 int w[3] = {t.a,t.b,t.c};// 我们能倒出的牛奶是能倒出桶的容量// 与要倒入桶的容量取较小值 int cur = min(w[i],W[j]-w[j]);w[i]-=cur,w[j]+=cur;int a = w[0],b=w[1],c=w[2];// 标记状态 if(!vis[a][b][c]){vis[a][b][c] =true;node[++tt] = {a,b,c};}}}}}return;
}int main(void)
{scanf("%d%d%d", &A,&B,&C);bfs();// 当A桶空的时候，有那些状态是合法的 for(int c=0;c<=C;c++){for(int b=0;b<=B;b++){if(vis[0][b][c]){printf("%d ",c);break;}}}return 0;
}

感谢查看！