本文涉及知识点

C++BFS算法

P9038 [PA 2021] Butelki

题目描述

Byteasar 有三瓶橙汁。他现在想通过把橙汁从一个瓶子倒入另一个瓶子的方式，让其中一个瓶子恰好装有 k k k 升橙汁。因为他家里没有量筒，所以唯一允许的操作是在两个瓶子之间转移橙汁——要么把一个瓶子倒空，要么把一个瓶子倒满。橙汁不能撒到地上，也不能在这三个瓶子之外添加橙汁。

Byteasar 现在想知道，对于每一个 k k k，最少需要转移多少次橙汁才能让三个瓶子中的一个装有恰好 k k k 升橙汁。他希望你帮帮他。

输入格式

第一行，三个整数 A , B , C A, B, C A,B,C，表示第一、二、三个瓶子的容积；

第二行，三个整数 a , b , c a, b, c a,b,c，表示第一、二、三个瓶子中最初装的橙汁体积。

输出格式

一行， C + 1 C + 1 C+1 个整数，其中第 i i i 个整数在存在一种操作方式使得让三个瓶子中的一个装有 i − 1 i - 1 i−1 升橙汁时为最小操作次数，否则为 − 1 -1 −1。

输入输出样例 #1

输入 #1

2 7 9
1 3 6

输出 #1

1 0 1 0 1 1 0 1 2 1

说明/提示

对于 100 % 100\% 100% 的数据， 1 ≤ A ≤ B ≤ C ≤ 1 0 5 1 \leq A \leq B \leq C \leq 10^5 1≤A≤B≤C≤105， 0 ≤ a ≤ A 0 \leq a \leq A 0≤a≤A， 0 ≤ b ≤ B 0 \leq b \leq B 0≤b≤B， 0 ≤ c ≤ C 0 \leq c \leq C 0≤c≤C。

记忆化搜索 BFS

s=a+b+c
除了初始状态，只少有一个瓶子空或满。
一，不失一般性，假定第一个瓶子空。令第二个瓶子装有x升橙汁，则第三个瓶子有s-x升橙汁。 x ∈ [ 0 , s ] x\in[0,s] x∈[0,s]，有s种可能得状态。
二，不失一般性，加到第一个瓶子满。令第二个瓶子装有x升橙汁，则第三个瓶子有s-x-a升橙汁。 x ∈ [ 0 , s − a ] x\in[0,s-a] x∈[0,s−a]。有s-a种状态。
结论：状态数不超过6s 。直接记忆化搜索。每种状态需要判断6种状态，故时间复杂度：O(s）.
为了避免编码，直接用有序集合，这样时间复杂度:O(nlogn）。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include<array>

#include <bitset>
using namespace std;

template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
	in >> pr.first >> pr.second;
	return in;
}

template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t);
	return in;
}

template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
	return in;
}

template<class T = int>
vector<T> Read() {
	int n;
	cin >> n;
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
	vector<T> ret;
	T tmp;
	while (cin >> tmp) {
		ret.emplace_back(tmp);
		if ('\n' == cin.get()) { break; }
	}
	return ret;
}

template<class T = int>
vector<T> Read(int n) {
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}

template<int N = 1'000'000>
class COutBuff
{
public:
	COutBuff() {
		m_p = puffer;
	}
	template<class T>
	void write(T x) {
		int num[28], sp = 0;
		if (x < 0)
			*m_p++ = '-', x = -x;

		if (!x)
			*m_p++ = 48;

		while (x)
			num[++sp] = x % 10, x /= 10;

		while (sp)
			*m_p++ = num[sp--] + 48;
		AuotToFile();
	}
	void writestr(const char* sz) {
		strcpy(m_p, sz);
		m_p += strlen(sz);
		AuotToFile();
	}
	inline void write(char ch)
	{
		*m_p++ = ch;
		AuotToFile();
	}
	inline void ToFile() {
		fwrite(puffer, 1, m_p - puffer, stdout);
		m_p = puffer;
	}
	~COutBuff() {
		ToFile();
	}
private:
	inline void AuotToFile() {
		if (m_p - puffer > N - 100) {
			ToFile();
		}
	}
	char  puffer[N], * m_p;
};

template<int N = 1'000'000>
class CInBuff
{
public:
	inline CInBuff() {}
	inline CInBuff<N>& operator>>(char& ch) {
		FileToBuf();
		while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车
		ch = *S++;
		return *this;
	}
	inline CInBuff<N>& operator>>(int& val) {
		FileToBuf();
		int x(0), f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行		
		return *this;
	}
	inline CInBuff& operator>>(long long& val) {
		FileToBuf();
		long long x(0); int f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行
		return *this;
	}
	template<class T1, class T2>
	inline CInBuff& operator>>(pair<T1, T2>& val) {
		*this >> val.first >> val.second;
		return *this;
	}
	template<class T1, class T2, class T3>
	inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val);
		return *this;
	}
	template<class T1, class T2, class T3, class T4>
	inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
		return *this;
	}
	template<class T = int>
	inline CInBuff& operator>>(vector<T>& val) {
		int n;
		*this >> n;
		val.resize(n);
		for (int i = 0; i < n; i++) {
			*this >> val[i];
		}
		return *this;
	}
	template<class T = int>
	vector<T> Read(int n) {
		vector<T> ret(n);
		for (int i = 0; i < n; i++) {
			*this >> ret[i];
		}
		return ret;
	}
	template<class T = int>
	vector<T> Read() {
		vector<T> ret;
		*this >> ret;
		return ret;
	}
private:
	inline void FileToBuf() {
		const int canRead = m_iWritePos - (S - buffer);
		if (canRead >= 100) { return; }
		if (m_bFinish) { return; }
		for (int i = 0; i < canRead; i++)
		{
			buffer[i] = S[i];//memcpy出错			
		}
		m_iWritePos = canRead;
		buffer[m_iWritePos] = 0;
		S = buffer;
		int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);
		if (readCnt <= 0) { m_bFinish = true; return; }
		m_iWritePos += readCnt;
		buffer[m_iWritePos] = 0;
		S = buffer;
	}
	int m_iWritePos = 0; bool m_bFinish = false;
	char buffer[N + 10], * S = buffer;
};


class Solution {
public:
	vector<int> Ans(const int A, const int B, const int C, const int a, const int b, const int c) {
		vector<int> vDis(C + 1, -1);
		auto ChangeDis = [&](int i, int iDis) {
			if (i > C) { return; }
			if (-1 == vDis[i]) { vDis[i] = iDis; }
		};
		queue<tuple<int, int, int, int>> abcn;
		set<tuple<int, int, int>> has;
		auto Add = [&](int a, int b, int c, int iDis) {
			auto abc = make_tuple(a, b, c);
			if (has.count(abc)) { return; }
			has.emplace(a, b, c);
			abcn.emplace(a, b, c, iDis);
			ChangeDis(a, iDis); ChangeDis(b, iDis); ChangeDis(c, iDis);
		};
		auto Do = [&](int& a, int& b, int B) {
			const int iNew = min(B - b, a);
			b += iNew;
			a -= iNew;
		};
		Add(a, b, c, 0);
		while (abcn.size()) {
			const auto [a1, b1, c1, dis] = abcn.front(); abcn.pop();
			auto a = a1, b = b1, c = c1;
			Do(a, b, B);
			Add(a, b, c, dis + 1);
			a = a1, b = b1, c = c1;
			Do(b, a, A);
			Add(a, b, c, dis + 1);
			a = a1, b = b1, c = c1;
			Do(c, b, B);
			Add(a, b, c, dis + 1);
			a = a1, b = b1, c = c1;
			Do(b, c, C);
			Add(a, b, c, dis + 1);
			a = a1, b = b1, c = c1;
			Do(a, c, C);
			Add(a, b, c, dis + 1);
			a = a1, b = b1, c = c1;
			Do(c, a, A);
			Add(a, b, c, dis + 1);
		}
		return vDis;
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG	
	//ios::sync_with_stdio(0); cin.tie(nullptr);
	//CInBuff<> in; COutBuff<10'000'000> ob;
	int A, B, C, a, b, c;
	cin >> A >> B >> C >> a >> b >> c;
#ifdef _DEBUG		
	//printf("N=%d", N);
	//Out(c, ",c=");
	//Out(km, ",km=");
	//Out(B, "B=");
	//Out(que, "que=");
	//Out(B, "B=");
#endif // DEBUG	
	auto res = Solution().Ans(A,B,C,a,b,c);
	for (const auto& i : res)
	{
		cout << i << " ";
	}
	return 0;
}

单元测试

	TEST_METHOD(TestMethod1)
		{			
			auto res = Solution().Ans(2,7,9,1,3,6);
			AssertEx({ 1, 0, 1 ,0 ,1, 1, 0, 1, 2, 1 }, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。