给定四个空杯子,容量分别为S1 S2 S3 S4,允许进行以下操作:
1. 将某个杯子接满水
2. 将某个杯子里的水全部倒掉
3. 将杯子A中的水倒进杯子B,直到A倒空或者B被倒满
问最少要多少步操作才能使得这四个杯子装的水分别为T1 T2 T3 T4
给定四个空杯子,容量分别为S1 S2 S3 S4,允许进行以下操作:
1. 将某个杯子接满水
2. 将某个杯子里的水全部倒掉
3. 将杯子A中的水倒进杯子B,直到A倒空或者B被倒满
问最少要多少步操作才能使得这四个杯子装的水分别为T1 T2 T3 T4
第一行四个非负整数S1 S2 S3 S4
第二行四个非负整数T1 T2 T3 T4
最少的步数,若无法完成则输出-1
0 2 3 4 0 1 2 4
6
过程如下:
(0,0,0,0)->(0,2,0,0)->(0,2,3,0)->(0,2,0,3)->(0,0,2,3)->(0,2,2,3)->(0,1,2,4)
0≤Ti≤Si<64
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<bitset> 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("%d %d %d %d", &Cap[1], &Cap[2], &Cap[3],&Cap[4]); scanf("%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); } }
倒水问题通用模板,适用于1个杯子(含有足够量的水)倒水给其余杯子
#include <bits/stdc++.h> using namespace std; struct node { int s[4];}; int mp[64][64][64][64]; queue<node>que; int main() { int i, j; int s[4], ss[4]; while (~scanf("%d%d%d%d%d%d%d%d", s, s + 1, s + 2, s + 3, ss, ss + 1, ss + 2, ss + 3)) { memset(mp, -1, sizeof(mp)); node t1; t1.s[0] = t1.s[1] = t1.s[2] = t1.s[3] = 0; que.push(t1); mp[0][0][0][0] = 0; while (!que.empty()) { if (mp[ss[0]][ss[1]][ss[2]][ss[3]] != -1) break; node temp = que.front(); node next = temp; que.pop(); for (i = 0; i < 4; i++) { if (temp.s[i] != s[i]) { next.s[i] = s[i]; if (mp[next.s[0]][next.s[1]][next.s[2]][next.s[3]] == -1) mp[next.s[0]][next.s[1]][next.s[2]][next.s[3]] = mp[temp.s[0]][temp.s[1]][temp.s[2]][temp.s[3]] + 1, que.push(next); next = temp; } } for (i = 0; i < 4; i++) { if (temp.s[i] != 0) { next.s[i] = 0; if (mp[next.s[0]][next.s[1]][next.s[2]][next.s[3]] == -1) mp[next.s[0]][next.s[1]][next.s[2]][next.s[3]] = mp[temp.s[0]][temp.s[1]][temp.s[2]][temp.s[3]] + 1, que.push(next); next = temp; } } for (i = 0; i < 4; i++) for (j = 0; j < 4; j++) { if (i == j) continue; int co = min(temp.s[i], s[j] - temp.s[j]); if (co == 0) continue; next.s[i] -= co, next.s[j] += co; if (mp[next.s[0]][next.s[1]][next.s[2]][next.s[3]] == -1) mp[next.s[0]][next.s[1]][next.s[2]][next.s[3]] = mp[temp.s[0]][temp.s[1]][temp.s[2]][temp.s[3]] + 1, que.push(next); next = temp; } } printf("%d\n", mp[ss[0]][ss[1]][ss[2]][ss[3]]); } return 0; }
#include<bits/stdc++.h> using namespace std; bool mem[64][64][64][64] = {false}; bool equal(int s[4], int T[4]){ return (s[0]==T[0])&&(s[1]==T[1])&&(s[2]==T[2])&&(s[3]==T[3]); } int bfs(int S[4], int T[4]){ queue<tuple<int,int,int,int>> q; auto x = make_tuple(0,0,0,0); q.push(x); mem[0][0][0][0] = true; int step = 0, cap[4]={0}; while(!q.empty()){ int size = q.size(); while(size--){ tie(cap[0],cap[1],cap[2],cap[3]) = q.front(); q.pop(); if(equal(cap, T)){ return step; } for(int i=0; i<3; ++i){ switch(i){ case 0: // 将某个杯子倒满 for(int j=0, tmp=0; j<4; ++j){ tmp = cap[j]; cap[j] = S[j]; x = make_tuple(cap[0], cap[1], cap[2], cap[3]); if(!mem[cap[0]][cap[1]][cap[2]][cap[3]]){ mem[cap[0]][cap[1]][cap[2]][cap[3]]=true; q.push(x); } cap[j] = tmp; } break; case 1: // 将某个杯子倒空 for(int j=0, tmp=0; j<4; ++j){ tmp = cap[j]; cap[j] = 0; x = make_tuple(cap[0], cap[1], cap[2], cap[3]); if(!mem[cap[0]][cap[1]][cap[2]][cap[3]]){ mem[cap[0]][cap[1]][cap[2]][cap[3]]=true; q.push(x); } cap[j] = tmp; } break; case 2: // 将杯子j倒向杯子z for(int j=0; j<4; ++j){ int tmp1,tmp2,need; for(int z=0; z<4; ++z){ if(j==z) continue; tmp1=cap[j], tmp2=cap[z]; need = min(cap[j], S[z]-cap[z]); cap[j] -= need; cap[z] += need; x = make_tuple(cap[0], cap[1], cap[2], cap[3]); if(!mem[cap[0]][cap[1]][cap[2]][cap[3]]){ mem[cap[0]][cap[1]][cap[2]][cap[3]]=true; q.push(x); } cap[j]=tmp1, cap[z]=tmp2; } } }//end switch } }//end inner while ++step; }//end outer while return -1; } int main(){ int S[4]={0}, T[4]={0}; cin>> S[0] >> S[1] >> S[2] >> S[3]; cin>> T[0] >> T[1] >> T[2] >> T[3]; if(S[0]==0 && S[1]==0 && S[2]==0 && S[3]==0 && !equal(S,T)){ cout<< -1 << endl; }else{ int ret = bfs(S, T); cout<< ret << endl; } return 0; }