题目链接： http://acm.nyist.net/JudgeOnline/problem.php?pid=21
思想： 看了一下搜索就来写了这题（BFS 找出最短路径 所以用此来进行搜索） 这题在加上栈的操作就能找到最后的路径（就是总共需要倒几次水）；
操作：
首先：将水杯初始化（A 0 0）进栈 当前倒水0次
然后进行搜索，取出栈顶，判断是否是目标结果，不是则把这个状态进行转移（就是进行这个状态进行在一次倒水操作，）
直到找到目标状态或是不能得到目标状态为止
这题感觉就是那个到倒水的时候处理不好处理 我是直接一步一步倒的
例如 A B C 三个水杯
首先进行A向 BC倒
再进行B 向 AC倒
最后是 C 向 AB倒
代码：
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio> using namespace std; typedef struct numb
{
int ta,tb,tc;
int t;
numb()
{
ta = 0,tb = 0,tc = 0,t = 0;
}
}numb; int x,y,z;//初始状态
int x1,y1,z1;//目标状态
int tmp[101][101][101];//标记是否已经倒过 vector<numb>v;//使用vector 来模拟栈操作
vector<numb>::iterator p; void judge(numb ans,int t)//判断是否能入栈
{
if(tmp[ans.ta][ans.tb][ans.tc] == 0)
{
// cout<<"stack = "<<ans.ta<<" "<<ans.tb<<" "<<ans.tc<<endl;
tmp[ans.ta][ans.tb][ans.tc] = 1;
ans.t = t;
v.push_back(ans);
}
}
void water(int xx,int yy,int zz,int t)//倒水处理
{
numb ans;
int kk = 0;
if(xx > 0)//从x想yz倒水
{
if(yy < y)//到在y中
{
kk = y-yy;
if(kk >= xx)
{
ans.ta = 0; ans.tb = yy + xx; ans.tc = zz;
judge(ans,t);
}
else
{
ans.ta = xx - kk; ans.tb = yy + kk; ans.tc = zz;
judge(ans,t);
}
} if(zz < z)//到在z中
{
kk = z - zz;
if(kk >= xx)
{
ans.ta = 0; ans.tb = yy; ans.tc = zz + xx;
judge(ans,t);
}
else
{
ans.ta = xx - kk; ans.tb = yy; ans.tc = zz + kk;
judge(ans,t);
}
}
} if(yy > 0)
{
if(xx < x)
{
kk = x - xx;
if(kk >= yy)
{
ans.ta = xx + yy; ans.tb = 0; ans.tc = zz;
judge(ans,t);
}
else
{
ans.ta = xx + kk; ans.tb = yy - kk; ans.tc = zz;
judge(ans,t);
}
} if(zz < z)
{
kk = z - zz;
if(kk >= yy)
{
ans.ta = xx; ans.tb = 0; ans.tc = zz + yy;
judge(ans,t);
}
else
{
ans.ta = xx; ans.tb = yy - kk; ans.tc = zz + kk;
judge(ans,t);
}
}
} if(zz > 0)
{
if(xx < x)
{
kk = x - xx;
if(kk >= zz)
{
ans.ta = xx + zz; ans.tb = yy; ans.tc = 0;
judge(ans,t);
}
else
{
ans.ta = xx + kk; ans.tb = yy; ans.tc = zz - kk;
judge(ans,t);
}
} if(yy < y)
{
kk = y - yy;
if(kk >= zz)
{
ans.ta = xx; ans.tb = yy+zz; ans.tc = 0;
judge(ans,t);
}
else
{
ans.ta = xx; ans.tb = yy+kk; ans.tc = zz - kk;
judge(ans,t);
}
}
}
}
int BFS()//搜索
{
numb ans;
while(v.empty() != true)
{
ans = v[0];
p = v.begin();
v.erase(p);
//cout<<"ans = "<<ans.ta<<" "<<ans.tb<<" "<<ans.tc<<" "<<ans.t<<endl;
if(ans.ta == x1 && ans.tb == y1 && ans.tc == z1)
return ans.t;
else
water(ans.ta,ans.tb,ans.tc,++ans.t);
}
return -1;
}
int main()
{
int T;
cin>>T;
while(T--)
{
memset(tmp,0,sizeof(tmp));
cin>>x>>y>>z;
cin>>x1>>y1>>z1;
tmp[x][0][0] = 1;
numb ans;
ans.ta = x; ans.tb = 0; ans.tc = 0; ans.t = 0;
v.push_back(ans);
//water(100,0,0,0);
cout<<BFS()<<endl;
v.clear();
}
return 0;
}
---恢复内容结束---