自动搬运

查看原文

来自洛谷，原作者为

	Kater_kcl **

搬运于2025-08-24 21:25:01，当前版本为作者最后更新于2019-09-14 00:43:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

update:修正了代码中的一处错误，感谢指正

这道题被我们用来团队考试了，这是我唯一一道ac的题，写个题解纪念一下。

首先拿道题，我就想到了广搜，因为最短路径的题一般都是广搜，且这道题的状态在可接受的范围之内，事实证明我也是对的，思路很简单：设置两个状态为a，b表示当前状态a杯和b杯的水量，每次从队列中读到一个状态之后，将这个状态执行题目中所给的六种操作，并将执行了六种操作之后的状态压入队列，记录答案并且继续搜索。

说完了整体思路，接下来就是本题的难点（易错点）了，首先第一条，如何解决掉操作5和操作6 （可能不是很难，但是我在考场上搞了半天没搞对）,首先读题干，题干告诉我们从B向A倒水会有两种情况：
1、直到A满
2、直到B没水
那么目标就很明确了，若是从B向A倒水，比较B的水量和A杯空着的体积做比较，若大于，则A=A满，B-=A的剩余体积，否则则是A+=B,B=0。
反过来倒一样。
然后就是记录解的问题，我这里使用的是vector存解，每次将状态压进队列的时候顺带将这个状态所经历的步骤也压进去，同时vector的大小便是这个状态的步数，这里看不懂的可以直接去看代码。
接下来该思考如何剪枝了，首先我们不难发现我们在搜索中会遇到很多重复的状态，但是根据广搜的性质，我们后搜到的状态一定没有之前的搜索更优，所以我们将以搜到的情况进行标记，防止出现重复的无意义搜索。
然后就是一些细枝末节的剪枝，比如当杯子已经是空的就不要empty了，已经满的就不要fill了，这都很好理解。
ac代码注释版奉上。

#include <iostream>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int ca,cb,n;//ca和cb分别表示两个杯子的最大容量,n表示目标值。
bool rem[1005][1005];
struct node
{
    int x,y;//x和y代表着a杯和b杯当前的水量
    vector  <int> ans;
};
void bfs(int x,int y){
    memset(rem,0,sizeof(rem));//不要忘了重置标记数组！！！！
    queue  <node> q;//搜索队列
    node ppp;
    ppp.x=x;
    ppp.y=y;
    q.push(ppp);
    while(1){
        node temp;
        temp=q.front();//从队头取出一个搜索状态
        q.pop();
        ///////////////////////////////////////
        if(temp.y==n){//终止条件
            cout<<temp.ans.size()<<" ";//输出步数
            for(int i=0;i<temp.ans.size();i++){
                cout<<temp.ans[i]<<" ";//输出解
            }
            cout<<endl;
            break;
        }
        ///////////////////////////////////////
        if(temp.x!=ca){//处理方式1
            node kater=temp;
            kater.x=ca;//这里由于我ca太菜不会构造函数，所以牺牲了美观性QAQ，别打我。
            kater.ans.push_back(1);//将新构筑出来的状态的操作后面加上个“1”。后面同理。
            if(!rem[kater.x][kater.y]){//如果之前被搜索过就不把他放到队列里
                q.push(kater);
                rem[kater.x][kater.y]=1;//记忆化，防止重搜
            }
        }
        ///////////////////////////////////////
        if(temp.y!=cb){//处理方式2
            node kater=temp;
            kater.y=cb;
            kater.ans.push_back(2);
            if(!rem[kater.x][kater.y]){
                q.push(kater);
                rem[kater.x][kater.y]=1;
            }
        }
        ///////////////////////////////////////
        if(temp.x!=0){//处理方式3
            node kater=temp;
            kater.x=0;
            kater.ans.push_back(3);
            if(!rem[kater.x][kater.y]){
                q.push(kater);
                rem[kater.x][kater.y]=1;
            }
        }
        ///////////////////////////////////////
        if(temp.y!=0){//处理方式4
            node kater=temp;
            kater.y=0;
            kater.ans.push_back(4);
            if(!rem[kater.x][kater.y]){
                q.push(kater);
                rem[kater.x][kater.y]=1;
            }
        }
        ///////////////////////////////////////
        if(temp.y!=0&&temp.x!=ca){//处理方式5
            node kater=temp;
            if(kater.y>ca-kater.x){
                kater.y-=ca-kater.x;
                kater.x=ca;
            }
            else{
                kater.x+=kater.y;
                kater.y=0;
            }//模拟倒水,注意这里的顺序不能反。
            kater.ans.push_back(5);
            if(!rem[kater.x][kater.y]){
                q.push(kater);
                rem[kater.x][kater.y]=1;
            }
        }
        ///////////////////////////////////////
        if(temp.x!=0&&temp.y!=cb){//处理方式6
            node kater=temp;
            if(kater.x>cb-kater.y){
                kater.x-=cb-kater.y;
                kater.y=cb;
            }
            else{
                kater.y+=kater.x;
                kater.x=0;
            }
            kater.ans.push_back(6);
            if(!rem[kater.x][kater.y]){
                q.push(kater);
                rem[kater.x][kater.y]=1;
            }
        }
    }
}
int main(){
    //    freopen("test.in","r",stdin);
    int T;
    cin>>T;
    while(T--){
        cin>>ca>>cb>>n;
        bfs(0,0);
    }
    return 0;
}

求过QAQ，审核员大大最帅了。