uva10603倒水问题宽度优先遍历！

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

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

难度不大，细心既可。

转载请注明出处，谢谢

http://blog.csdn.net/monkeyduck

#include<iostream>  
#include<cstring>  
  
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<rear)  
    {  
        tnode=state[front++];  
        if (tnode.water[0]==d||tnode.water[1]==d||tnode.water[2]==d)  
        {  
            flag=1;  
            result=tnode;  
            break;  
        }  
        for (i=0;i<3;i++)  
        {  
            for (j=0;j<3;j++)  
            {  
                if (i!=j)  
                {  
                    int amount=tnode.water[i]<vol[j]-tnode.water[j]?tnode.water[i]:vol[j]-tnode.water[j];  
                    if (amount!=0)  
                    {  
                        Node nNode;  
                        for (int k=0;k<3;k++)  
                            nNode.water[k]=tnode.water[k];  
                        nNode.water[i]=nNode.water[i]-amount;  
                        nNode.water[j]=nNode.water[j]+amount;  
                        nNode.s=tnode.s+amount;  
                        if (!vis[nNode.water[0]][nNode.water[1]])  
                        {  
                            vis[nNode.water[0]][nNode.water[1]]=1;  
                            state[rear++]=nNode;  
                        }  
                    }  
                }  
            }  
        }  
    }  
}  
int main()  
{  
    cin>>n;  
    while(n--)  
    {  
        cin>>vol[0]>>vol[1]>>vol[2]>>d;  
        flag=0;  
        memset(vis,0,sizeof(vis));  
        bfs();  
        if (flag)  
            cout<<result.s<<" "<<d<<endl;  
        else  
        {  
            for (int i=d-1;i>=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<<nn.s<<" "<<i<<endl;  
                        flag=1;  
                        break;  
                    }  
                }  
                if (flag) break;  
            }  
        }  
    }  
    return 0;  
}

补充：软件开发 , C++ ,