倒水问题？ c++

来源：百度知道 编辑：UC知道 时间：2024/05/10 11:18:35
有两个杯子，容量分别是x升、y升。现在要经过倒水，在x升的杯子或y升的杯子中盛z升水。水是无限的，可以一直往两个杯子中灌水，可以往外倒水。z不大于x、y中较大的一个。（也就是说z升水肯定能盛得下！）而且给的数据也是以定能倒出来的（例如6、6两个杯子，盛不出4）。

输入x、y、z，输出最少倒（操作）几次。
注意！只有将2个杯子同时灌满，算一次操作。其余的往外倒水、两个杯子互相倒水，灌满一个杯子，都算一次操作。

用C++！最好用递归~谢谢啦！！
就是很经典的倒水问题啦！没有刻度的杯子，只能来回倒水。

这个递归也太慢了
写了一个用的是广度搜索

#include <iostream>
#include <queue>

using namespace std;

const int Limit_Size = 1000;

struct Con
{
int x, y;
int times;
};

queue<Con> q;
int target, x, y, Min_time;
bool use[ Limit_Size ][ Limit_Size ];

void init( )
{
Con tmp;
int i, j, t;
cin >> x >> y >> target;
if ( x > y )
t = x;
else
t = y;
tmp.x = tmp.y = tmp.times = 0;
q.push( tmp );
for ( i = 0; i <= t; i++ )
for ( j = 0; j <= t; j++ )
use[ i ][ j ] = false;
use[ 0 ][ 0 ] = true;
}

void fillwater( Con t )
{
Con tmp;
int c;
if ( !use[ t.x ][ 0 ] ) //倒出y
{
tmp = t;
tmp.y = 0;
tmp.times = t.times + 1;
q.push( tmp );
use[ t.x ][ 0 ] = true;
}
if ( !use[ 0 ][ t.y ] ) //倒出x