非常可乐
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11034 Accepted Submission(s): 4458
Problem Description
大
家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这
一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S
（S<101）毫升 (正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0)
。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这
一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S
（S<101）毫升 (正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0)
。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
Input
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。
Output
如果能平分的话请输出最少要倒的次数，否则输出"NO"。
Sample Input
7 4 3
4 1 3
0 0 0
4 1 3
0 0 0
Sample Output
NO
3
3
Author
seeyou
题解:奇数的除外,总共六种倒法,a->b a->c b->a b->c c->a c->b.三种状态,仔细一点模拟就可以做出来了。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <stdlib.h>
using namespace std; struct Node{
int x,y,z,step;
};
int a,b,c;
bool vis[][][];
int bfs(){
memset(vis,false,sizeof(vis));
queue<Node> q;
Node s;
s.x = a,s.y = ,s.z = ,s.step = ;
vis[a][][]=true;
q.push(s);
while(!q.empty()){
Node now = q.front();
q.pop();
if(now.x==a/&&now.y==a/||now.x==a/&&now.z==a/||now.y==a/&&now.z==a/){
return now.step;
}
Node next;
if(now.x!=){ /// a -> b
if(now.x>b-now.y){ ///还可以倒满b
next.x =now.x-(b-now.y);
next.y = b;
next.z = now.z;
}else{
next.x = ;
next.y =now.x+now.y;
next.z = now.z;
}
next.step=now.step+;
if(!vis[next.x][next.y][next.z]){
vis[next.x][next.y][next.z] = true;
q.push(next);
}
}
if(now.x!=){ ///a->c
if(now.x>c-now.z){
next.x = now.x - (c-now.z);
next.y = now.y;
next.z = c;
}else{
next.x = ;
next.y = now.y;
next.z =now.z+now.x;
}
next.step=now.step+;
if(!vis[next.x][next.y][next.z]){
vis[next.x][next.y][next.z] = true;
q.push(next);
}
}
if(now.y!=){ ///b->a
if(now.y>a-now.x){
next.x = a;
next.y = now.y - (a-now.x);
next.z = now.z;
}else{
next.x = now.x+now.y;
next.y = ;
next.z =now.z;
}
next.step=now.step+;
if(!vis[next.x][next.y][next.z]){
vis[next.x][next.y][next.z] = true;
q.push(next);
}
}
if(now.y!=){ ///b->c
if(now.y>c-now.z){
next.x = now.x;
next.y = now.y - (c-now.z);
next.z = c;
}else{
next.x = now.x;
next.y = ;
next.z =now.z+now.y;
}
next.step=now.step+;
if(!vis[next.x][next.y][next.z]){
vis[next.x][next.y][next.z] = true;
q.push(next);
}
}
if(now.z!=){ ///c->a
if(now.z>a-now.x){
next.x = a;
next.y = now.y;
next.z = now.z - (a-now.x);
}else{
next.x = now.x+now.z;
next.y = now.y;
next.z = ;
}
next.step=now.step+;
if(!vis[next.x][next.y][next.z]){
vis[next.x][next.y][next.z] = true;
q.push(next);
}
}
if(now.z!=){ ///c->b
if(now.z>b-now.y){
next.x = now.x;
next.y = b;
next.z = now.z - (b-now.y);
}else{
next.x = now.x;
next.y = now.y+now.z;
next.z = ;
}
next.step=now.step+;
if(!vis[next.x][next.y][next.z]){
vis[next.x][next.y][next.z] = true;
q.push(next);
}
}
}
return -;
}
int main(){
while(scanf("%d%d%d",&a,&b,&c)!=EOF,a+b+c){
if(a%==){
printf("NO\n");
continue;
}
int ans = bfs();
if(ans==-){
printf("NO\n");
}else{
printf("%d\n",ans);
}
}
}