设大中小3个辈子的容量分别为a,b,c, 最初只有大杯子装满水, 其他两个杯子为空. 最少需要多少步才能让某个杯子中的水有x升呢?你需要打印出每步操作后各个杯子中的水量.(0<c<b<a<1000)

倒水问题.cpp

#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

//3个瓶子的大小
int ga[3] = {0};

class CStatus
{
public:
  CStatus(const int a, const int b, const int c, CStatus* last = NULL) {
		arr[0] = a;
		arr[1] = b;
		arr[2] = c;
		this->last = last;
	}
	
	//是否搜索到最终结果
	bool isEnd(const int x) {
		if (arr[0] == x || arr[1] == x || arr[2] == x) {
			return true;
		}
		return false;
	}
	//获取该状态可以迁移至的其他所有状态
	void getNext(vector<CStatus*> &v) {
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) if (i != j && arr[i] != 0) {
				int t = ga[j] - arr[j];
				int re[3] = {0};
				memcpy(re, arr, 3 * sizeof(int));
				if (t > 0 && arr[i] >= t) {
					re[i] = arr[i] - t;
					re[j] = ga[j];
				}else if (t > 0 && arr[i] < t) {
					re[i] = 0;
					re[j] = arr[j] + arr[i];
				}
				v.push_back(new CStatus(re[0], re[1], re[2], this));
			}
		}
	}

	CStatus* last;
	int arr[3];	
};

//打印搜索路径
void printPath(CStatus *cur) {
	if (cur == NULL) return;
	printPath(cur->last);
	printf("(%d, %d, %d)->", cur->arr[0], cur->arr[1], cur->arr[2]);
}

//注意 还需要写判重  
//宽搜  
void bfs(CStatus *start, const int x) {
	queue<CStatus*> q;
	q.push(start);
	while (!q.empty()) {
		CStatus* cur = q.front();
		if (cur->isEnd(x)) {
			printPath(cur);
			printf("suc!\n");
			break;
		}
		vector<CStatus*> v;
		cur->getNext(v);
		q.pop();
		for (vector<CStatus*>::const_iterator i = v.begin(); i != v.end(); ++i) {
			q.push(*i);
		}
	}
}

int main()
{
	int x = 0;
	while (scanf("%d%d%d%d", &ga[0], &ga[1], &ga[2], &x) != EOF) {
		CStatus* start = new CStatus(ga[0], 0, 0);
		bfs(start, x);
	}
	return 0;
}