题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1495
题目大意:只有两个杯子,它们的容量分别是N 毫升和M 毫升 可乐的体积为S (S<101)毫升 (正好装满一瓶) ,它们三个之间可以相互倒可乐 (都是没有刻度的,且 S==N+M,101>S>0,N>0,M>0) 。如果能将可乐平分则输出倒可乐的最少的次数,如果不能输出"NO"。
解题思路:题意很坑看了半天,就是要有两个杯子里的可乐都为S/2,S为奇数肯定不能平分的,接下来就模拟倒水(有六个选择)进行BFS,然后用数组记录各杯子里水的量作为状态。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=;
int A,B,C,ans;
int vis[N][N][N]; struct node{
int a,b,c,step;
}pre,now; bool bfs(){
queue<node>q;
now.a=A;
now.b=;
now.c=;
now.step=;
vis[A][][]=;
q.push(now);
while(!q.empty()){
pre=q.front();
q.pop();
for(int i=;i<=;i++){
int a,b,c;
a=pre.a;
b=pre.b;
c=pre.c;
if(i==){
if(a>B-b){
a-=(B-b);
b=B;
}
else{
b+=a;
a=;
}
}
if(i==){
a+=b;
b=;
}
if(i==){
if(b>C-c){
b-=(C-c);
c=C;
}
else{
c+=b;
b=;
}
}
if(i==){
if(c>B-b){
c-=(B-b);
b=B;
}
else{
b+=c;
c=;
}
}
if(i==){
if(a>C-c){
a-=(C-c);
c=C;
}
else{
c+=a;
a=;
}
}
if(i==){
a+=c;
c=;
}
if(vis[a][b][c])
continue;
if(b==a&&b==A/||a==c&&a==A/){
ans=pre.step+;
return true;
}
vis[a][b][c]=;
now.a=a;
now.b=b;
now.c=c;
now.step=pre.step+;
q.push(now);
}
}
return false;
} int main(){
while(~scanf("%d%d%d",&A,&B,&C)){
memset(vis,,sizeof(vis));
ans=;
if(A==&&B==&&C==)
break;
if(A&)
puts("NO");
else if(bfs())
printf("%d\n",ans);
else
puts("NO");
}
return ;
}