题目描述
农夫约翰有三个容量分别为 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
算法
经典的分酒问题,因为最大数据量是21的3次方,所以可以直接搜。深搜和宽搜都可以,下面给出的是宽搜的代码。
C++代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 21;
int A, B, C;//三个桶的容量
bool st[N][N][N];//记录三个桶的状态
struct Node
{
int a, b, c;
}q[N * N * N];//宽搜队列
int hh, tt;//hh:队头,tt:队尾
void insert(int a, int b, int c)
{
if (!st[a][b][c])//将未搜索过的状态插入宽搜队列的队尾
{
q[++ tt] = {a, b, c};
st[a][b][c] = true;
}
}
void bfs()
{
q[0] = {0, 0, C};//初始状态插入队头。初始状态是题意给出的
st[0][0][C] = true;
while(hh <= tt)//当宽搜队列不空时
{
auto t = q[hh ++];//取出队头元素进行搜索
int a = t.a, b = t.b, c = t.c;
insert(a - min(a, B - b), min(a + b, B), c);//a->b
insert(a - min(a, C - c), b, min(a + c, C));//a->c
insert(min(a + b, A), b - min(b, A - a), c);//b->a
insert(a, b - min(b, C - c), min(b + c, C));//b->c
insert(min(a + c, A), b, c - min(A - a, c));//c->a
insert(a, min(b + c, B), c - min(B - b, c));//c->b
}
}
int main()
{
cin >> A >> B >> C;
bfs();
for (int c = 0; c <= C; ++c)//根据题意,从小到大遍历C桶的可能值
for (int b = 0; b <= B; ++b)//搜索B桶的可能值
if (st[0][b][c])//将符合A桶为0的状态输出
{
cout << c << ' ';
break;
}
return 0;
}