非常可乐（HDU 1495）

非常可乐（HDU 1495）

Problem Description
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是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

Sample Output
NO
3

题意：

给你三个杯子，来看是否可以通过这三个杯子互相装满的操作实现第一个被子内的水的平分。

思路:

水杯间的操作共有六种：

由通过这六种操作来进行状态转移的思考，就不难得出利用BFS的算法的思路了。

代码：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;int s,a,b,ans;
int vis[110][110];struct cup{int s,a,b,step;
}st,ed;
queue<cup> q;void bfs(){st.s=s;q.push(st);while(!q.empty()){cup temp=q.front();						//由缓存操作以不改变原先状态if((temp.a==s/2&&temp.s==s/2)||(temp.b==s/2&&temp.s==s/2)||(temp.a==s/2&&temp.b==s/2)) {ans=temp.step;return;}													//出口if(temp.s!=0&&temp.a!=a){if(temp.s>=(a-temp.a)){int c=a-temp.a;ed.s=temp.s-c;ed.a=a;}else{ed.a=temp.a+temp.s;ed.s=0;}ed.b=temp.b;ed.step=temp.step+1;if(!vis[ed.a][ed.b]){vis[ed.a][ed.b]=1;q.push(ed);}}if(temp.s!=0&&temp.b!=b){if(temp.s>=(b-temp.b)){int c=b-temp.b;ed.s=temp.s-c;ed.b=b;}else{ed.b=temp.b+temp.s;ed.s=0;}ed.a=temp.a;ed.step=temp.step+1;if(!vis[ed.a][ed.b]){vis[ed.a][ed.b]=1;q.push(ed);}}if(temp.a!=0&&temp.s!=s){if(temp.a>=(s-temp.s)){int c=s-temp.s;ed.a=temp.a-c;ed.s=s;}else{ed.s=temp.a+temp.s;ed.a=0;}ed.b=temp.b;ed.step=temp.step+1;if(!vis[ed.a][ed.b]){vis[ed.a][ed.b]=1;q.push(ed);}}if(temp.a!=0&&temp.b!=b){if(temp.a>=(b-temp.b)){int c=b-temp.b;ed.a=temp.a-c;ed.b=b;}else{ed.b=temp.a+temp.b;ed.a=0;}ed.s=temp.s;ed.step=temp.step+1;if(!vis[ed.a][ed.b]){vis[ed.a][ed.b]=1;q.push(ed);}}if(temp.b!=0&&temp.a!=a){if(temp.b>=(a-temp.a)){int c=a-temp.a;ed.b=temp.b-c;ed.a=a;}else{ed.a=temp.a+temp.b;ed.b=0;}ed.s=temp.s;ed.step=temp.step+1;if(!vis[ed.a][ed.b]){vis[ed.a][ed.b]=1;q.push(ed);}}if(temp.b!=0&&temp.s!=s){if(temp.b>=(s-temp.s)){int c=s-temp.s;ed.b=temp.b-c;ed.s=s;}else{ed.s=temp.b+temp.s;ed.b=0;}ed.a=temp.a;ed.step=temp.step+1;if(!vis[ed.a][ed.b]){vis[ed.a][ed.b]=1;q.push(ed);}}q.pop();}cout<<"NO"<<endl;
}int main(){while(cin>>s>>a>>b&&(s+a+b)){if(s%2) {cout<<"NO"<<endl;continue;}if(a<b){int swap=a;a=b;b=swap;}while(!q.empty()) q.pop();memset(vis,0,sizeof(vis));ans=0;bfs();if(ans) cout << ans<<endl;}	
}