大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/180090.html原文链接：https://javaforall.net
