母亲的奶牛（bfs）

本文主要是介绍母亲的奶牛（bfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

农夫约翰有三个容量分别为 $A,B,C$ 升的挤奶桶。

最开始桶 $A$ 和桶 $B$ 都是空的，而桶 $C$ 里装满了牛奶。

有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。

这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。

请你编写一个程序判断，当 $A$ 桶是空的时候，$C$ 桶中可能包含多少升牛奶，找出所有的可能情况。

输入格式

共一行，包含三个整数 $A,B,C$。

输出格式

共一行，包含若干个整数，表示 $C$ 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

数据范围

$1\le A,B,C\le 20$

输入样例1：

8 9 10

输出样例1：

1 2 8 9 10

输入样例2：

2 5 10

输出样例2：

5 6 7 8 9 10

思路

以输入样例1模拟

可以发现，每个桶都可以倒入另外两个桶中

也就是说，在桶的数量为 $3$ 的情况下，共有 $3\times 2=6$ 种可能。

因此可以枚举 6 种状态或者循环遍历所有所有状态。

这里我们可以用数组模拟队列，每当有新的状态时，就把新状态入队，通过遍历队列进行宽搜。

代码

#include<iostream>
#include<algorithm>
using namespace std;const int N = 21;
int A, B, C; //桶的容量
struct node {int a, b, c;
} q[N * N * N];
bool st[N][N][N];//标记状态int bfs() {int hh = 0, tt = 0; //队头队尾q[0] = {0, 0, C};st[0][0][C] = true;int W[3] = {A, B, C}; //桶的容量while (hh <= tt) {auto t = q[hh++];for (int i = 0; i < 3; i++) //将i桶倒入j桶for (int j = 0; j < 3; j++)if (i != j) {int w[3] = {t.a, t.b, t.c};int r = min(w[i], W[j] - w[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 i = 0; i <= C; i++)for (int j = 0; j <= B; j++)if (st[0][j][i]) {cout << i << ' ';break;}return 0;
}

这篇关于母亲的奶牛（bfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---