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

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}