题目 http://acm.hdu.edu.cn/showproblem.php?pid=1495
刚开始那做这个题 怎么也想不出为什么可以用bfs
我认为做这个题目 你想到有6种情况哦 假设s 是瓶子 n，m 是有容量的杯子, s可以倒入n中 ，s也可以倒入m中
n可以倒入s中 n 也可以倒入m中 m也是一样的哦 所以就有六种情况哦。。。
下面看具体ac 代码 里面有注解哦
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct node{
int x,y,num; ///x表示n瓶子现在装有多少可乐 y表示m瓶子
///num表示瓶子剩余多少可乐哦。。
int step; ///一共走了多少步
};
int s,n,m,mark[101][101][101]; ///mark标记是否以前已经有过这样的状态
void bfs()
{
queue<node> Q;
node p,t;
memset(mark,0,sizeof(mark)); ///初始化
p.x=0;
p.y=0;
p.num=s;
p.step=0;
Q.push(p);
mark[p.num][p.x][p.y]=1; ///标记
int s1=s/2;
while(!Q.empty())
{
t=Q.front();
Q.pop();
///什么时候说明已经好了
if((t.num==s1&&t.x==s1)||(t.y==s1&&t.num==s1)||(t.x==s1&&t.y==s1))
{
cout<<t.step<<endl;
return ;
}
if(t.num!=0) ///假设瓶子s里面还有水哦
{
if(t.num>n-t.x) ///将瓶子中剩下的水放进瓶子n中
{
p.num=t.num+t.x-n;
p.x=n;
p.y=t.y;
p.step=t.step+1;
}
else
{
p.num=0;
p.x=t.num+t.x;
p.y=t.y;
p.step=t.step+1;
}
if(!mark[p.num][p.x][p.y])
{
mark[p.num][p.x][p.y]=1;
Q.push(p);
}
if(t.num>m-t.y) ///同理将可乐倒入m瓶子中
{
p.num=t.num-(m-t.y);
p.x=t.x;
p.y=m;
p.step=t.step+1;
}
else {
p.num=0;
p.x=t.x;
p.y=t.num+t.y;
p.step=t.step+1;
}
if(!mark[p.num][p.x][p.y])
{
mark[p.num][p.x][p.y]=1;
Q.push(p);
}
}
if(t.x!=0)///假设杯子n还有水
{
if(t.x>m-t.y) ///倒入m杯子
{
p.num=t.num;
p.x=t.x-(m-t.y);
p.y=m;
p.step=t.step+1;
}
else{
p.num=t.num;
p.x=0;
p.y=t.x+t.y;
p.step=t.step+1;
}
if(!mark[p.num][p.x][p.y])
{
mark[p.num][p.x][p.y]=1;
Q.push(p);
}
if(t.x>s-t.num) ///倒入s杯子
{
p.num=s;
p.x=t.x-(s-t.num);
p.y=t.y;
p.step=t.step+1;
}
else{
p.num=t.num+t.x;
p.x=0;
p.y=t.y;
p.step=t.step+1;
}
if(!mark[p.num][p.x][p.y])
{
Q.push(p);
mark[p.num][p.x][p.y]=1;
}
}
if(t.y!=0) ///同理哦
{
if(t.y>n-t.x)
{
p.num=t.num;
p.x=n;
p.y=t.y-(n-t.x);
p.step=t.step+1;
}
else {
p.num=t.num;
p.x=t.y+t.x;
p.y=0;
p.step=t.step+1;
}
if(!mark[p.num][p.x][p.y])
{
Q.push(p);
mark[p.num][p.x][p.y]=1;
}
if(t.y>(s-t.num))
{
p.num=s;
p.x=t.x;
p.y=t.y-(s-t.num);
p.step=t.step+1;
}
else{
p.num=t.y+t.num;
p.x=t.x;
p.y=0;
p.step=t.step+1;
}
if(!mark[p.num][p.x][p.y])
{
Q.push(p);
mark[p.num][p.x][p.y]=1;
}
}
}
cout<<"NO"<<endl;
return ;
}
int main()
{
while(cin>>s>>n>>m,s+n+m)
{
if(s%2==1) ///如果是奇数就不可以分哦 没有0.5哦
{
cout<<"NO"<<endl;
continue;
}
bfs();
}
return 0;
}