water

#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;

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;
}