算法学习-分酒问题（BFS）[通俗易懂]

算法学习–分酒问题（BFS）[通俗易懂]

全栈程序员-用户IM • 2022年10月19日下午10:46 • 未分类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

有4个红酒瓶子，它们的容量分别是：9升, 7升, 4升, 2升
开始的状态是 [9,0,0,0]，也就是说：第一个瓶子满着，其它的都空着。

允许把酒从一个瓶子倒入另一个瓶子，但只能把一个瓶子倒满或把一个瓶子倒空，不能有中间状态。
这样的一次倒酒动作称为1次操作。

假设瓶子的容量和初始状态不变，对于给定的目标状态，至少需要多少次操作才能实现？
本题就是要求你编程实现最小操作次数的计算。

输入：最终状态（空格分隔）
输出：最小操作次数（如无法实现，则输出-1）

例如：
输入：
9 0 0 0
应该输出：
0

输入：
6 0 0 3
应该输出：
-1

输入：
7 2 0 0
应该输出：
2

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std;

//状态类
class state { 
   
public:
	string str;//目前状态
	int step;//从原始状态到目前状态需要的步骤数
	state(string s, int st) :str(s), step(st) { 
   }
};

char glass[4] = { 
    '9','7','4','2' };//四个杯子的容量 

int bfs(string target) { 
   
	set<string> s;
	queue<state> q;
	q.push(state("9000", 0));//初始状态加入队列
	s.insert("9000");
	while (!q.empty()) { 
   
		state tmp = q.front();//取出第一个元素 
		q.pop();//弹出第一个元素 
		if (tmp.str == target) { 
   
			return tmp.step;
		}
		int k = tmp.step;
		//尝试从第i个杯子倒到第j个杯子 
		for (int i = 0; i < 4; i++) { 
   
			for (int j = 0; j < 4; j++) { 
   
				if (i == j)continue;//不能自己倒给自己 
				//1.把自己倒完（目标杯子现有量+要倒入的量<=目标杯子容量）主要看别的杯子能否装的下
				if (tmp.str[i] + tmp.str[j] - '0' <= glass[j]) { 
   
					string temp = tmp.str;
					temp[j] += temp[i] - '0';
					temp[i] = '0';
					if (s.find(temp) == s.end()) { 
   //如果这个状态之前没有出现过，就加入到集合中
						s.insert(temp);
						q.push(state(temp, k + 1));
					}
				}
				//2.把别的杯子装满 主要看自己能不能装满别的杯子
				if (tmp.str[i] + tmp.str[j] - '0' >= glass[j]) { 
   
					string temp = tmp.str;
					int a = glass[j] - '0';
					int b = temp[j] - '0';
					temp[i] -= a - b;
					temp[j] = glass[j];
					if (s.find(temp) == s.end()) { 
   
						s.insert(temp);
						q.push(state(temp, k + 1));
					}
				}
			}
		}
	}
	return -1;
}

int main() { 
   
	int n1, n2, n3, n4;
	cin >> n1 >> n2 >> n3 >> n4;
	string str = to_string(n1) + to_string(n2) + to_string(n3) + to_string(n4);
	cout << bfs(str) << endl;
	return 0;
}