【P1432 倒水问题】题解
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，审核员大大最帅了。