题解 P1432 【倒水问题】

· · 题解

（竟然发这题题解的人那么少，那么我就来水一发题解）

解题思路：

宽搜BFS一看就是要以最少的次数到达题目的要求，想到最少就想到了宽搜 BFS，还是比较裸的BFS，相对比较简单。

本人的BFS：通过普通的队列来进行搜索，建立一个vis数组来储存这种情况是否出现过，然后向6个方向拓展（fill A，fill B, empty A, empty B ,pour A B,pour B A），遇到新的点就放入队尾。然后将队首的点出队进行搜索，当搜索到的点符合题目要求就返回答案。

接下来贴代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,a,b,c,l,r;//a,b,c就是题中的变量，l为队首指针，r为队尾指针。
int ai[10000],bi[10000],ans[10000],f[10000][10000];//ai,bi分别为A，B中的水，f数组储存到达当前情况进行的操作，ans为当前情况进行的操作总数。
bool vis[2000][2000];//vis用来是否搜索过。
void bfs(int x,int y) {
    if(y==c) { //当B中的水与需要的C相等时开始输出
        cout<<ans[l]<<" ";
        for(int i=1; i<=ans[l]; i++) { //输出进行的操作
            cout<<f[l][i]<<" ";
        }
        cout<<endl;//成功
        return;
    }
    for(int i=1; i<=6; i++) { //对6个方向进行拓展
        if((i==1)&&(x!=a)&&(!vis[a][y])) { //当搜索过了或者A本来就是满的，fill A为无效的
            ++r;//队尾指针+1。
            ai[r]=a;//进行 fill A 操作后入队
            bi[r]=y;
            vis[a][y]=true;//标记
            ans[r]=ans[l]+1;
            for(int j=1; j<=ans[l]; j++)f[r][j]=f[l][j];
            f[r][ans[r]]=i;//将之前的操作赋值给新的状况
        }
        if((i==2)&&(y!=b)&&(!vis[x][b])) { //同上
            ++r;
            ai[r]=x;//同上
            bi[r]=b;
            vis[x][b]=true;
            ans[r]=ans[l]+1;
            for(int j=1; j<=ans[l]; j++)f[r][j]=f[l][j];
            f[r][ans[r]]=i;//同上
        }
        if((i==3)&&(x!=0)&&(!vis[0][y])) { //同上，当A本为空或已搜索都是无效操作
            ++r;
            ai[r]=0;//同上
            bi[r]=y;
            ans[r]=ans[l]+1;
            vis[x][b]=true;
            for(int j=1; j<=ans[l]; j++)f[r][j]=f[l][j];
            f[r][ans[r]]=i;//同上
        }
        if((i==4)&&(y!=0)&&(!vis[x][0])) { //同上
            ++r;
            ai[r]=x;
            bi[r]=0;
            ans[r]=ans[l]+1;
            vis[x][b]=true;
            for(int j=1; j<=ans[l]; j++)f[r][j]=f[l][j];
            f[r][ans[r]]=i;
        }
        if((i==5)&&(x!=a)&&(y!=0)&&(!vis[x+y][0])) {
            ++r;//当A为满或B为空，都是无效操作。
            vis[x+y][0]=true;//直接用x+y代替的比用直接用x，y做下标好，可以省代码，而且如A为6，B为4或A为9，b为1可以看做操作后是同一种情况。
            if(x+y<=a) { //如果A装不满的情况
                ai[r]=x+y;
                bi[r]=0;
            } else { //如果A装满了的情况
                ai[r]=a;
                bi[r]=x+y-a;
            }
            ans[r]=ans[l]+1;
            for(int j=1; j<=ans[l]; j++)f[r][j]=f[l][j];
            f[r][ans[r]]=i;
        }
        if((i==6)&&(x!=0)&&(y!=b)&&(!vis[0][x+y])) {
            ++r;//同上
            vis[0][x+y]=true;
            if(x+y<=b) {
                ai[r]=0;
                bi[r]=x+y;
            } else { //同上
                ai[r]=x+y-b;
                bi[r]=b;
            }
            ans[r]=ans[l]+1;
            for(int j=1; j<=ans[l]; j++)f[r][j]=f[l][j];
            f[r][ans[r]]=i;
        }
    }
    ++l;//队首指针+1，队首出队
    if(l<=r)bfs(ai[l],bi[l]);
    else return;
    return;//对它进行拓展，如果l>r,即没有未搜索过的点则说明这种情况无解
}
int main() {
    cin>>n;
    while(n--) {
        cin>>a>>b>>c;
        l=0;
        r=0;//初始化
        memset(vis,false,2000*2000);//也是初始化
        bfs(0,0);//从两个壶都没有水开始搜索
    }
    return 0;
}