uva10603倒水问题宽度优先遍历！ - c++编程基础

利用bfs解题，以三个杯子中现有水量作为一个“状态”，从一个状态不断扩展新的状态加入排队数组，这样既可保证找到目标水量时是经过了最少次数的倒水操作。

扩展新的状态节点是个稍微难一点的地方，先计算出i给j能倒得水量amount，等于i所剩水与j所差水的最小值。然后当amount！=0时进行倒水操作。vis是判重数组，只需要二维既可，因为三个杯子的水总量是不变的，两个杯子的水量相同时就表明是同一个状态。

难度不大，细心既可。

转载请注明出处，谢谢

http://blog.csdn.net/monkeyduck

#include  
#include  
  
using namespace std;  
  
int vol[3],d,n,front,rear;  
bool flag,vis[201][201];  
struct Node  
{  
    int water[3],s;  
};  
Node result,state[40001];  
void bfs()  
{  
    int i,j;  
    front=rear=0;  
    Node init,tnode;  
    init.water[0]=0;init.water[1]=0;init.water[2]=vol[2];init.s=0;  
    vis[0][0]=1;  
    state[rear++]=init;  
    while(front




>n;  
    while(n--)  
    {  
        cin>>vol[0]>>vol[1]>>vol[2]>>d;  
        flag=0;  
        memset(vis,0,sizeof(vis));  
        bfs();  
        if (flag)  
            cout<=0;i--)  
            {  
                for (int j=0;j<=rear;j++)  
                {  
                    Node nn=state[j];  
                    if (nn.water[0]==i||nn.water[1]==i||nn.water[2]==i)  
                    {  
                        cout<