问题：
假设我们有 3 个水罐，即 A、B 和 C。水罐 C 一开始总是完全装满的。此外，我们将定义一个目标状态，其中水罐 A 将包含 a 加仑，B 将包含 b 加仑，C 将包含 c 加仑，在搜索完成后。您需要使用广度优先搜索来找到从初始状态到目标状态的最小移动次数。
我的伪代码：
bool BFS(int a, int b, int c)
add new State(a, b, c) to Queue
pop from the Queue
while (queue is not empty)
if current_state equals goal_state
print the backtracked solution
return true
if current_state has already been seen
continue
mark current as having been visited
try 6 ways to pour water, pushing new states to queue
return false
我在 C++ 中的解决方案：
#include <iostream>
#include <sstream>
#include <string>
#include <regex>
#include <queue>
#include <map>
#include <new>
using namespace std;
// Struct to represent state of water in the jugs.
struct State
{
int a, b, c;
int toPour;
char from;
char to;
State *parent;
State(int _a, int _b, int _c, State *_parent) : a(_a), b(_b), c(_c), toPour(0), parent(_parent) {}
State(int _a, int _b, int _c, int _toPour, char _from, char _to, State *_parent) : a(_a), b(_b), c(_c), toPour(_toPour), from(_from), to(_to), parent(_parent) {}
// String representation of state in tuple form.
void to_string()
{
if (toPour > 0)
{
cout << "Pour " << toPour;
if (toPour == 1)
{
cout << " gallon";
} else
{
cout << " gallons";
}
cout << " from " << from << " to " << to;
}
else
{
cout << "Initial state";
}
cout << ". (" << a << ", " << b << ", " << c << ")" << endl;
}
};
void demonstrate(State state) {
if (state.parent != nullptr)
{
demonstrate(*(state.parent));
}
state.to_string();
return;
}
bool BFS(int a, int b, int c, int capacity[], int goal[])
{
map<pair<pair<int, int>, int>, int> m;
queue<State> q;
q.push(*(new State(a, b, c, nullptr)));
int toPour;
while (!q.empty())
{
if (q.front().a == goal[0] && q.front().b == goal[1] && q.front().c == goal[2])
{
demonstrate(q.front());
return true;
}
if (m[make_pair(make_pair(q.front().a, q.front().b), q.front().c)] == 1)
{
q.pop();
continue;
}
m[make_pair(make_pair(q.front().a, q.front().b), q.front().c)] = 1;
// a -> b
if (q.front().a > 0 && q.front().b < capacity[1])
{
toPour = q.front().a > (capacity[1] - q.front().b) ? (capacity[1] - q.front().b) : q.front().a;
q.push(*(new State(q.front().a - toPour, q.front().b + toPour, q.front().c, toPour, 'A', 'B', &q.front())));
}
// a -> c
if (q.front().a > 0 && q.front().c < capacity[2])
{
toPour = q.front().a > (capacity[2] - q.front().c) ? (capacity[2] - q.front().c) : q.front().a;
q.push(*(new State(q.front().a - toPour, q.front().b, q.front().c + toPour, toPour, 'A', 'C', &q.front())));
}
// b -> c
if (q.front().b > 0 && q.front().c < capacity[2])
{
toPour = q.front().b > (capacity[2] - q.front().c) ? (capacity[2] - q.front().c) : q.front().b;
q.push(*(new State(q.front().a, q.front().b - toPour, q.front().c + toPour, toPour, 'B', 'C', &q.front())));
}
// b -> a
if (q.front().b > 0 && q.front().a < capacity[0])
{
toPour = q.front().b > (capacity[0] - q.front().a) ? (capacity[0] - q.front().a) : q.front().b;
q.push(*(new State(q.front().a + toPour, q.front().b - toPour, q.front().c, toPour, 'B', 'A', &q.front())));
}
// c -> a
if (q.front().c > 0 && q.front().a < capacity[0])
{
toPour = q.front().c > (capacity[0] - q.front().a) ? (capacity[0] - q.front().a) : q.front().c;
q.push(*(new State(q.front().a + toPour, q.front().b, q.front().c - toPour, toPour, 'C', 'A', &q.front())));
}
// c -> b
if (q.front().c > 0 && q.front().b < capacity[1])
{
toPour = q.front().c > (capacity[1] - q.front().b) ? (capacity[1] - q.front().b) : q.front().c;
q.push(*(new State(q.front().a, q.front().b + toPour, q.front().c - toPour, toPour, 'C', 'B', &q.front())));
}
q.pop();
}
return false;
}
int main(int argc, char **argv)
{
if (argc != 7)
{
cout << "Usage: ./waterjugpuzzle <cap A> <cap B> <cap C> <goal A> <goal B> <goal C>" << endl;
exit(0);
}
regex digits("\\d+");
int *capacity = new int[3];
for (int i = 1; i < 4; i++)
{
if (!regex_match(argv[i], digits) || stoi(argv[i]) == 0)
{
cout << "Error: Invalid capacity '" << argv[i] << "' for jug " << (char)('A' + i - 1) << "." << endl;
exit(1);
}
capacity[i - 1] = stoi(argv[i]);
}
int *goal = new int[3];
int totalGoal = 0;
for (int i = 4; i < 7; i++)
{
if (!regex_match(argv[i], digits))
{
cout << "Error: Invalid goal '" << argv[i] << "' for jug " << (char)('A' + i - 4) << "." << endl;
exit(1);
}
goal[i - 4] = stoi(argv[i]);
totalGoal += stoi(argv[i]);
}
for (int i = 0; i < 3; i++)
{
if (goal[i] > capacity[i])
{
cout << "Error: Goal cannot exceed capacity of jug " << (char)('A' + i) << "." << endl;
exit(2);
}
}
if (totalGoal != capacity[2])
{
cout << "Error: Total gallons in goal state must be equal to the capacity of jug C." << endl;
exit(3);
}
if (!BFS(0, 0, capacity[2], capacity, goal))
{
cout << "No solution." << endl;
}
return 0;
}
用法： ./waterjugpuzzle <capacity A> <capacity B> <capacity C> <goal A> <goal B> <goal C>
示例：
./waterjugpuzzle 1 3 4 0 2 2
Initial state. (0, 0, 4)
Pour 3 gallons from C to B. (0, 3, 1)
Pour 1 gallon from B to A. (1, 2, 1)
Pour 1 gallon from A to C. (0, 2, 2)
错误：此解决方案在 MacOS 上完美运行，但在 Ubuntu 上，当我尝试一些输入（如8 17 20 0 10 10or 4 7 10 0 5 5）时，程序Segmentation fault (core dumped)在找到解决方案并开始打印后返回。