博客

倒水问题

题目

：两个容量不同且互质的杯子相互倒水（相互倒水时必须将其中一个杯子倒水或者倒空，不存在倒半杯的情况，要不然谁也不能确定倒了多少升水不是），直到倒出C升的水。

题目详细描述如下：

思路

：

本道题主要考察bfs，就是从水量（0，0）的时候一直倒水至（C，x）或者（x，C），x为未知量。为了不重复之前的倒水步骤（即陷入死循环），必须对每一个到达过的水量进行标记。然后将六种倒水状态分别编辑成一个函数，例如“empty A”就是将A中的水倒空，B中水量不变。在进行每一层bfs的时候，依次执行六个操作（fill A/fill B/empty A/empty B/pour A to B/po），直到倒出C升的水。为了在倒完水之后回溯整个倒水过程，需要记录下每一次倒水之前的水量与倒水之后的水量。

函数解释与方法选择

：

1.首先进行bfs所以选择了队列，不再具体说明。

2.选择使用pair记录了每一次的水量。

3.选择map记录每次倒水前与倒水后杯中的水量（key:倒水前，value:倒水后），这样便很容易用from[倒水后]的方法回溯倒水过程，同时还可以判断当前倒水状态是否已存在（使用find函数）。

4.check函数检查该倒水状态是否存在，若不存在将当前倒水状态加入map。

5.print3函数，通过递归输出倒水的过程。

6.judge4函数，根据回溯的杯中水量判断进行的是六种倒水操作的哪一种。

说明：


写了好几版print和judge函数，功能一样，具体实现有所不同，最后采用的是print3和judge4！！！！（因为不愿意发生删除删错了的悲剧…就不删了）

PS：

bfs简易版题目：

https://blog.csdn.net/weixin_44876049/article/details/104637717

激动人心的代码：

#include <iostream>
#include <queue>
#include <vector>
#include <map> 
#include <cstring>
using namespace std;

map<pair<int, int>, pair<int, int> > from;//t,f
queue<pair<int, int> > q;
int A, B, C;//容量 
int x[1000];


pair<int, int> AtoB(pair<int, int> &p)
{
	pair<int, int> p1;
	p1.first = max(0, p.first + p.second - B);
	p1.second = min(B, p.first + p.second);
	return p1;
}

pair<int, int> BtoA(pair<int, int> &p)
{
	pair<int, int> p1;
	p1.first = min(A, p.first + p.second);
	p1.second = max(0, p.first + p.second - A);
	return p1;
}

pair<int, int> emptyA(pair<int, int> &p)
{
	pair<int, int> p1(0, p.second);
	return p1;
}

pair<int, int> emptyB(pair<int, int> &p)
{
	pair<int, int> p1(p.first, 0);
	return p1;
}

pair<int, int> fillA(pair<int, int> &p)
{
	pair<int, int> p1(A, p.second);
	return p1;
}

pair<int, int> fillB(pair<int, int> &p)
{
	pair<int, int> p1(p.first, B);
	return p1;
}

void check(pair<int, int> &f, pair<int, int> &t)
{
	if (from.find(t) == from.end())//没有经历过这种情况
	{
		from[t] = f;
		q.push(t);
	}
}

void judge(pair<int, int> &f, pair<int, int> &t)
{
	if (f.first != 0 && t.first == 0 && f.second == t.second)
		cout << "empty A" << endl;
	else if (f.second != 0 && t.second == 0 && f.first == t.first)
		cout << "empty B" << endl;
	else if (f.first != A && t.first == A && f.second == t.second)
		cout << "fill A" << endl;
	else if (f.second != B && t.second == B && f.first == t.first)
		cout << "fill A" << endl;
	else if (f.second < t.second)
		cout << "pour A B" << endl;
	else
		cout << "pour B A" << endl;
}

int judge2(pair<int, int> &f, pair<int, int> &t)
{
	if (f.first != 0 && t.first == 0 && f.second == t.second)
		//cout << "empty A" << endl;
		return 1;
	else if (f.second != 0 && t.second == 0 && f.first == t.first)
		//cout << "empty B" << endl;
		return 2;
	else if (f.first != A && t.first == A && f.second == t.second)
		//cout << "fill A" << endl;
		return 3;
	else if (f.second != B && t.second == B && f.first == t.first)
		//cout << "fill B" << endl;
		return 4;
	else if (f.second < t.second)
		//cout << "pour A B" << endl;
		return 5;
	else
		//cout << "pour B A" << endl;
		return 6;
}

void print4(pair<int, int> &f, pair<int, int> &t)
{
	if (f.first != 0 && t.first == 0 && f.second == t.second)
		cout << "empty A" << endl;
	else if (f.second != 0 && t.second == 0 && f.first == t.first)
		cout << "empty B" << endl;
	else if (f.first != A && t.first == A && f.second == t.second)
		cout << "fill A" << endl;
	else if (f.second != B && t.second == B && f.first == t.first)
		cout << "fill B" << endl;
	else if (f.second < t.second)
		cout << "pour A B" << endl;
	else
		cout << "pour B A" << endl;
		
}

void print(pair<int, int> &p)
{
	cout << "???" << endl;
	pair<int, int> f = from[p];
	if (p.first == 0 && p.second == 0)
	{
		judge(f, p);
	}

	else
	{
		return print(f);
		judge(f, p);
		cout << "go!" << endl;
	}	
}

void print2(pair<int, int> &p)
{
	while (p.first!=0 || p.second!=0)
	{
		pair<int, int> f = from[p];
		judge(f, p);
		p = f;
	}
}

void print3(pair<int, int> &p)
{
	for(int i=999; i>=0;i--)
	{
		pair<int, int> f = from[p];
		x[i] = judge2(f, p);
		p = f;
		if (p.first == 0 && p.second == 0)
			break;
	}
	for (int i = 0; i < 1000; i++)
	{
		//cout << "aaa" << endl;
		if (x[i] == 0)
			continue;
		switch (x[i])
		{
			
			case 1:
				cout << "empty A" << endl;
				break;
			case 2:
				cout << "empty B" << endl;
				break;
			case 3:
				cout << "fill A" << endl;
				break;
			case 4:
				cout << "fill B" << endl;
				break;
			case 5:
				cout << "pour A B" << endl;
				break;
			default:
				cout << "pour B A" << endl;
				break;
		}
	}
}

void bfs()
{
	pair<int, int> p1(0, 0);
	q.push(p1);
	from[p1] = p1;
	int a, b;
	while (!q.empty())
	{
		memset(x, 0, sizeof x);
		pair<int, int> f = q.front();
		q.pop();

		pair<int, int> f1 = fillA(f);
		check(f, f1);

		pair<int, int> f2 = fillB(f);
		check(f, f2);

		pair<int, int> f3 = emptyA(f);
		check(f, f3);

		pair<int, int> f4 = emptyB(f);
		check(f, f4);

		pair<int, int> f5 = BtoA(f);
		check(f, f5);

		pair<int, int> f6 = AtoB(f);
		check(f, f6);


		if (f.first == C || f.second == C)
		{
			a = f.first;
			b = f.second;
			break;
		}
	}
	pair<int, int> result(a, b);
	print3(result);
	cout << "success" << endl;
}


int main()
{
	while (cin >> A >> B >> C)
	{
		bfs();
		from.clear();
		while (!q.empty()) q.pop();
	}
	return 0;
}