待学习。。
// Study.cpp: 定义控制台应用程序的入口点。//#include "stdafx.h"#include#include #include #include #include using namespace std;/*将4杯子倒水问题改为一个足够大的杯子倒向4个杯子*/bitset<17043521> Hash;/*（大小为64*64^4+64*64^3+64*64^2+64*64^1+64*64^0）记录每次操作后的ABCD杯子的当前容量是否已经存在过*/const int MAX_STEP = 100000;int WQ[MAX_STEP][6];/*记录每步操作后0和ABCD的当前容量，最后一个记录操作次数*/int Goal[5];/*0和ABCD杯子最终状态*/int Cap[5]; /*0和ABCD杯子的最大容量*/int goalval;int head = 0;int tail = 0;void movw(int numfrom, int numto, int other1, int other2, int other3)/*numfrom倒入numto*/{ int total = WQ[head][numfrom] + WQ[head][numto];/*numfrom和numto的总量*/ WQ[tail][other1] = WQ[head][other1]; WQ[tail][other2] = WQ[head][other2]; WQ[tail][other3] = WQ[head][other3]; WQ[tail][5] = WQ[head][5] + 1; if (total>Cap[numto])/*总量和被倒入杯子的容量大小；大于numfrom就有剩余的，否则全部倒入numto*/ { WQ[tail][numfrom] = total - Cap[numto]; WQ[tail][numto] = Cap[numto]; } else { WQ[tail][numfrom] = 0; WQ[tail][numto] = total; } int hashval = WQ[tail][1] * 262144 + WQ[tail][2] * 4096 + WQ[tail][3] * 64 + WQ[tail][4];/*把ABCD杯子需要的状态抽象为一个值*/ if (hashval == goalval) throw WQ[head][5] + 1;/*判断是否为最终状态*/ if (!Hash[hashval])/*该次操作之后的状态之前未存在过并记录*/ { Hash[hashval] = true; if (++tail == MAX_STEP) tail = 0;/*超出最大操作数*/ }}int main(){ Hash.reset(); scanf_s("%d %d %d %d", &Cap[1], &Cap[2], &Cap[3], &Cap[4]); scanf_s("%d %d %d %d", &Goal[1], &Goal[2], &Goal[3], &Goal[4]); head = 0; tail = 0; goalval = Goal[1] * 262144 + Goal[2] * 4096 + Goal[3] * 64 + Goal[4];/*把ABCD杯子需要的状态抽象为一个值*/ /*处理全部杯子中最后容量都为0的情况*/ if (Goal[1] == 0 && Goal[2] == 0 && Goal[3] == 0 && Goal[4] == 0) { printf("0"); return 0; } Cap[0] = 6400;/*0杯子为足够大的杯子，0杯子的容量*/ WQ[tail][0] = 6400;/*0杯子的当前容量*/ /*初始化ABCD杯子当前值为0*/ WQ[tail][1] = 0; WQ[tail][2] = 0; WQ[tail][3] = 0; WQ[tail][4] = 0; WQ[tail][5] = 0; ++tail; try { /*尝试每一种操作*/ while (head != tail) { /*A导入B，外层if判断A中当前容量不为零，内层判断B的最大容量不为0*/ if (WQ[head][0]) { if (Cap[1]) movw(0, 1, 2, 3, 4); if (Cap[2]) movw(0, 2, 1, 3, 4); if (Cap[3]) movw(0, 3, 1, 2, 4); if (Cap[4]) movw(0, 4, 1, 2, 3); } if (WQ[head][1]) { if (Cap[0]) movw(1, 0, 2, 3, 4); if (Cap[2]) movw(1, 2, 0, 3, 4); if (Cap[3]) movw(1, 3, 0, 2, 4); if (Cap[4]) movw(1, 4, 0, 2, 3); } if (WQ[head][2]) { if (Cap[0]) movw(2, 0, 1, 3, 4); if (Cap[1]) movw(2, 1, 0, 3, 4); if (Cap[3]) movw(2, 3, 0, 1, 4); if (Cap[4]) movw(2, 4, 0, 1, 3); } if (WQ[head][3]) { if (Cap[0]) movw(3, 0, 1, 2, 4); if (Cap[1]) movw(3, 1, 0, 2, 4); if (Cap[2]) movw(3, 2, 0, 1, 4); if (Cap[4]) movw(3, 4, 0, 1, 2); } if (WQ[head][4]) { if (Cap[0]) movw(4, 0, 1, 2, 3); if (Cap[1]) movw(4, 1, 0, 2, 3); if (Cap[2]) movw(4, 2, 0, 1, 3); if (Cap[3]) movw(4, 3, 0, 1, 2); } if (++head == MAX_STEP) { head = 0; } } printf("-1"); } catch (int step) { printf("%d\n", step); }}
看了上面代码，自己给思路改进了一下，代码如下：
类似于图的广度优先遍历，每一种情况都一个个入队列，然后判断是否和预期的状态相等，相等时候停止循环，输出并返回。
// Study.cpp: 定义控制台应用程序的入口点。//#include "stdafx.h"#include#include #include #include #include #include #include using namespace std;//存储每一种状态bool m[64][64][64][64];//int Step=0;const int MaxStep = 10000;vector cap(4), goal(4);class state {public: state(int ra=0,int rb=0, int rc = 0, int rd = 0,int s = 0):a(ra),b(rb),c(rc),d(rd),step(s){} int a, b, c, d; int step;};queue Queue({ 0,0,0,0 });//Queue.push({ 0,0,0,0 });//对序号k进行操作，装满，或者导入其他容器void water_solution(int t[5],int k){ int tmp = t[k]; int tmp2; if (t[k] != cap[k] ) { t[k] = cap[k]; if(!m[t[0]][t[1]][t[2]][t[3]]) { Queue.push({ t[0],t[1],t[2],t[3], t[4] + 1 }); m[t[0]][t[1]][t[2]][t[3]] = 1; } t[k] = tmp; } //有剩余的水，可倒给其他杯子 if (t[k] != 0) { for (int i = 0; i < 4; i++) { //对自己倒水，可以全部倒走 if (k == i) { t[k] = 0; if (!m[t[0]][t[1]][t[2]][t[3]]) { Queue.push({ t[0],t[1],t[2],t[3], t[4] + 1 }); m[t[0]][t[1]][t[2]][t[3]] = 1; } t[k] = tmp; continue; } //倒给别人，1：倒不完 if (t[k] + t[i] >= cap[i]) { tmp2 = t[i]; t[i] = cap[i]; t[k] = t[k] - (cap[i] - tmp2); if (!m[t[0]][t[1]][t[2]][t[3]]) { Queue.push({ t[0],t[1],t[2],t[3], t[4] + 1 }); m[t[0]][t[1]][t[2]][t[3]] = 1; } t[k] = tmp; t[i] = tmp2; } else { tmp2 = t[i]; t[i] += t[k]; t[k] = 0; if (!m[t[0]][t[1]][t[2]][t[3]]) { Queue.push({ t[0],t[1],t[2],t[3], t[4] + 1 }); m[t[0]][t[1]][t[2]][t[3]] = 1; } t[k] = tmp; t[i] = tmp2; } } }}int main(){ for (int i = 0; i < 4; i++) cin >> cap[i]; for (int i = 0; i < 4; i++) cin >> goal[i]; int t[5]; state current{0,0,0,0}; int k = 0; while (!Queue.empty()) { current = Queue.front(); t[0] = current.a; t[1] = current.b; t[2] = current.c; t[3] = current.d; t[4] = current.step; Queue.pop(); if (t[0] == goal[0] && t[1] == goal[1] && t[2] == goal[2] && t[3] == goal[3]) { cout << t[4]; system("pause"); return 0; } for(int i=0;i<4;i++) water_solution(t, i); } cout << -1; system("pause"); return 0;}