3个桶均分8升水 c++

题目

3个桶，分别为8L，5L，3L。初始状态8L的桶里满水，另外2个桶空。过程中只能将一个桶向另一个桶，倒满或者倒空水，求所有将8L水均分为4L+4L的方案，并展示倒水过程。

思路

• 搜索用的BFS（DFS应该也可）
• 简单的用vector<int>{a, b, c} 来表示3个桶中水的多少，即状态；
• 用一个unordered_map< vector<int>, vector<vector<int>> > 来记录每个状态的所有前驱状态，即value[0] 可以一次倒水操作至 key, value[1] 可以倒水操作至 key …
• 最后用DFS找每一种方案的路径

细节

• 避免无限搜索下去，BFS时，如果状态已经是key，则说明这个状态加入过队列了，不用重复加入
• vector<int> 作为 unordered_map 的 key， 需要自定义哈希函数
• DFS找每一种方案路径时，也要避免5, 3, 0 --> 3, 5, 0 --> ... --> 5, 3, 0 --> 无限循环下去
• 看网上说是16种方案，不知道自己练习的代码对不对…搓搓手.jpg

代码

#include<bits/stdc++.h>
using namespace std;
// 8L, 5L, 3L水桶，将8L升水均分为4,4，求所有方案//定义unordered_map的哈希函数
auto myhash = [](const vector<int>& v) { return v[0] + 100 + v[1] * 10 + v[2];
};unordered_map<vector<int>, vector<vector<int>>, decltype(myhash)> ump(0, myhash); //记录每一种状态的所有前驱状态
int cnt = 0;  //方案数，据说16种^.^// 利用bfs搜索所有状态
void bfs() { queue < vector<int>> q;q.push(vector<int>{8, 0, 0});ump[{8, 0, 0}] = {};  //8,0,0 要先写成key，不然会重复bfs8,0,0一次vector<int> cur, empty, nxt;int dir[6][2] = { {0, 1}, {1, 0}, {0, 2}, {2, 0}, {1, 2}, {2, 1} };  //6种倒水方向while (q.size()) {cur = q.front();q.pop();if (cur == vector<int>({ 4, 4, 0 })) continue;vector<int> empty = { 8 - cur[0], 5 - cur[1], 3 - cur[2]};for (int i = 0; i < 6; ++i) {int x = dir[i][0], y = dir[i][1];  //倒出和倒入的杯子序号int litre = min(cur[x], empty[y]);if (litre == 0) continue;  //有杯子空或满，不能再倒水nxt = cur;nxt[x] = cur[x] - litre;nxt[y] = cur[y] + litre;if (ump.count(nxt)) ump[nxt].emplace_back(cur);  //nxt状态之前已经作为key，只加入前驱else {ump[nxt] = { cur };  //nxt没有作为key，加入ump，且继续bfsq.push(nxt);}}}
}// dfs找每个方案的倒水过程
void dfs(const vector<int>& cur, vector<vector<int>>& track) {// 需要判断cur是否在track中出现过，否则会有5,3,0 -> 3,5,0 -> 5,3,0无限循环下去for (int i = 0; i < track.size(); ++i) {if (track[i] == cur)return;}track.emplace_back(cur);if (cur == vector<int>{8, 0, 0}) { //输出printf("方案 %d \n", ++cnt);for (int i = track.size() - 1; i >= 0; --i) {printf("%d, %d, %d %s", track[i][0], track[i][1], track[i][2], i == 0? "" : "--> ");}puts("");track.pop_back();return;}for (auto& p : ump[cur]) {dfs(p, track);}track.pop_back();  
}int main() {bfs();vector<int> finalstatus = { 4, 4, 0 };vector<vector<int>> track;dfs(finalstatus, track);return 0;
}

结果