倒水問題（廣度優先搜尋）

問題描述：

有兩個無刻度标志的水壺，分别可裝x升和y升 （ x,y 為整數且均不大于100）的水。設另有一水缸，可用來向水壺灌水或接從水壺中倒出的水， 兩水壺間，水也可以互相傾倒。已知x升壺為空壺， y升壺為空壺。問如何通過倒水或灌水操作， 用最少步數能在x或y升的壺中量出 z（z ≤ 100）升的水來。

這道題就是廣度優先搜尋，需要注意的就是判斷是否重複。

分析題目所有情況：

                 X向Y倒水，1.X倒空了。

                                     2.X還有剩餘。

                 Y向X倒水， 3.Y倒空了。

                                     4.Y還有剩餘。

                 X向水缸倒水，5.X空了。

                 Y向水缸倒水，6.Y空了。

                 水缸向X灌水，7.X滿水。

                 水缸向Y倒水，8.Y滿水。

一共有上述8種可能情況。

定義一個結構體，存儲X壺的水量，Y壺的水量，目前的操作次數。

struct state{

int x,y,step;

}f;

這道題在網上看到有用帶結構體的隊列解決的，覺得挺好的。

#include <bits/stdc++.h>
using namespace std;
int x,y,z;
struct state{
int x,y,step;
}f;
queue<state> q;
bool vis[105][105];
int BFS()
{
    q.push(f);
    vis[f.x][f.y]=1;//已通路過
    while(q.size())//隊列中還有元素
    {
        f=q.front();
        q.pop();//隊友出隊
        if(f.x==z||f.y==z)
            return f.step;
        if(f.x<x&&vis[x][f.y]==0)//x倒滿
        {
            q.push((state){x,f.y,f.step+1});
            vis[x][f.y]=1;
        }
        if(f.x&&vis[0][f.y]==0)//x倒空
            {
                q.push((state){0,f.y,f.step+1});
                vis[0][f.y]=1;
            }
            if(f.y<y&&vis[f.x][y]==0)//y倒滿
            {
                q.push((state){f.x,y,f.step+1});
                vis[f.x][y]=1;
            }
            if(f.y&&vis[f.x][0]==0)//y倒空
            {
              q.push((state){f.x,0,f.step+1});
              vis[f.x][0]=1;
            }
            if(f.x>=y-f.y&&vis[f.x-(y-f.y)][y]==0)//x倒給y且x中還有剩餘，此時y已裝滿
               {
                   q.push((state){f.x-(y-f.y),y,f.step+1});
                   vis[f.x-(y-f.y)][y]=1;
               }
               if(f.x<y-f.y&&vis[0][f.x+f.y]==0)//x倒給y且x倒空
                {
                    q.push((state){0,f.x+f.y,f.step+1});
                    vis[0][f.x+f.y]=1;
                }
                if(f.y>=x-f.x&&vis[x][f.y-(x-f.x)]==0)//y倒給x且y中還有剩餘
                {
                    q.push((state){x,f.y-(x-f.x),f.step+1});
                    vis[x][f.y-(x-f.x)]=1;
                }
                if(f.y<x-f.x&&vis[f.x+f.y][0]==0)//y倒給x且y倒空
                    {
                        q.push((state){f.x+f.y,0,f.step+1});
                        vis[f.x+f.y][0]=1;
                    }
    }
    return -1;
}
int main()
{
    scanf("%d%d%d",&x,&y,&z);
    int ans=BFS();
    if(ans!=-1)
        printf("%d",ans);
    else
        printf("impossible");
    return 0;
}