农夫约翰有三个容量分别为 A , B , C A,B,C A,B,C 升的挤奶桶。
最开始桶 A A A 和桶 B B B 都是空的,而桶 C C C 里装满了牛奶。
有时,约翰会将牛奶从一个桶倒到另一个桶中,直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。
这一过程中间不能有任何停顿,并且不会有任何牛奶的浪费。
请你编写一个程序判断,当 A A A 桶是空的时候, C C C 桶中可能包含多少升牛奶,找出所有的可能情况。
输入格式
共一行,包含三个整数 A , B , C A,B,C A,B,C。
输出格式
共一行,包含若干个整数,表示 C C C 桶中牛奶存量的所有可能情况,请将这些数字按升序排列。
数据范围
1 ≤ A , B , C ≤ 20 1≤A,B,C≤20 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
思路
以输入样例1模拟
可以发现,每个桶都可以倒入另外两个桶中
也就是说,在桶的数量为 3 3 3 的情况下,共有 3 × 2 = 6 3 \times 2 = 6 3×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;
}