算法竞赛入门经典例题7-8 倒水问题（Fill,Uva 1060

心路历程：
首先不要被题目吓倒了，我刚开始思考的时候，想着倒水还不是想倒多少倒多少，可能性无穷无尽，怎么算？
仔细审题后发现，其实这里能不能倒水，倒多少水，倒水后的状态怎样，都是唯一确定的。
我们可以使用计算机将其所有的可能性都列举出来，从中找到符合题意的状态。

这里使用广度优先的方式列举，即先考虑当前状态可能形成的所有状态，再依据某种顺序从所有可能顺序中选择状态进行广度优先的尝试。注意使用标志量去重。

具体实现：
使用Nodes结构体数组存储每种状态（每个杯子中装了多少水，当前情况下已经取出水量的大小）
因为确定了第一个和第二个杯子的水量，第三个杯子的水量也就确定，所以可使用二维数组vis[][]做标记数组。
倒水细节见代码。
由于题目要求最小取水量，我们不应该直接按照队列先进先出的顺序选择状态，而应该优先选择取水量低的状态。
优先队列可参考此博客：https://www.mmuaa.com/post/6439c2495c41c6e6.html
写完代码才发现题目要求在目标水量未达到的情况下取最近的水量，可以简单将目标水量与相近的状态水量做一个差，更新保存最小值的状态即可。
代码：

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
struct Node{
    int v[3] = {0};
    int minwater = 0;
    //重载 '<'
    friend bool operator < (Node a, Node b){
        return a.minwater > b.minwater;
    }
}Nodes[50000],temp,temp2;

int vis[201][201] = {0};
int vol_base[3];
int vabc[3],d,water;


void Init(){
    memset(vis, 0, sizeof(vis));
}
priority_queue<Node> qq;


int bfs(){
    while(!qq.empty()){
         //将自己倒光或者将对方倒满
        temp = qq.top(); qq.pop();//从队列中取出一种状态。
        //三个容器，每个都有可能是倒水的，每个也都有可能是接水的，所以用一个二重循环模拟，下面倒水的杯子用dao表示，接水的杯子用jie表示
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++){
                if(i==j)
                    continue;
                int dao = temp.v[i];
                int jie = temp.v[j];
                // cout<<dao<<' '<<jie<<' '<<i<<' '<<j<<' '<<endl;
                if(dao!=0 && jie!=vabc[j]){//当倒水杯中有水 且 接水杯未满时 可以倒水
                    //给temp2赋初值
                    temp2.minwater=temp.minwater;
                    temp2.v[0]=temp.v[0];
                    temp2.v[1]=temp.v[1];
                    temp2.v[2]=temp.v[2];
                    
                    //倒水有两种情况
                    //全倒光：接水杯剩余容量 >= 倒水杯中的水量
                    if(vabc[j]-jie >= dao){
                        temp2.v[i] = 0;//新状态的倒水杯水量为0
                        temp2.v[j] = jie+dao;//接水杯的水量 为原来水量+倒水杯倒出的水量
                        temp2.minwater = temp.minwater + dao;
                        if(!vis[temp2.v[0]][temp2.v[1]]){
                            qq.push(temp2);
                            vis[temp2.v[0]][temp2.v[1]] = 1;
                        }
                    }
                    else{//倒一部分：接水杯剩余容量 < 倒水杯中的水量
                        temp2.v[i] = dao - (vabc[j]-jie);
                        temp2.v[j] = vabc[j];
                        temp2.minwater = temp.minwater + vabc[j]-jie;
                        if(!vis[temp2.v[0]][temp2.v[1]]){
                            qq.push(temp2);
                            vis[temp2.v[0]][temp2.v[1]] = 1;
                        }
                    }
                }
                for(int i=0;i<3;i++)
                        if(temp2.v[i] == d){
                            cout<<temp2.minwater<<endl;
                            return 0;
                        }
            }
    }
}


int main(){
    Init();
    cin>>vabc[0]>>vabc[1]>>vabc[2]>>d;
    Nodes[0].v[2] = vabc[2];
    qq.push(Nodes[0]);
    vis[0][0] = 1;
    bfs();
    getchar();
    getchar();
    return 0;
}