非常可乐【广搜，模拟】

非常可乐

 HDU - 1495 

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

方法：通过广搜搜索每一个过程，及时记录当前状态即可。

AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
int v,a,b;
bool vis[120][120][120];
struct node
{
	int a,b,c;
	int step;
};
int t;
bool judge(int a,int b,int c)
{
	if((a==t&&b==t)||(a==t&&c==t)||(b==t&&c==t))
		return true;
	else
		return false;
}
int bfs()
{
	node st;
	st.a=v;
	st.b=0;
	st.c=0;
	st.step=0;
	vis[v][0][0]=true;
	queue<node> q;
	while(!q.empty())
		q.pop();
	q.push(st);
	while(!q.empty())
	{
		//printf("%d\n",t);
		node front=q.front();
		q.pop();
		for(int i=1;i<=6;i++)
		{
			node tail;
			switch(i) 
			{
				case 1:
				{
					if(front.a>0&&front.b<a)
					{
						int k1=front.a-(a-front.b),k2;
						if(k1<0)
						{
							k1=0;
							k2=front.a+front.b;
						}
						else
						{
							k1=front.a-(a-front.b);
							k2=a;
						}
						if(vis[k1][k2][front.c]==false)
						{
							tail.a=k1;
							tail.b=k2;
							tail.c=front.c;
							tail.step=front.step+1;
							vis[tail.a][tail.b][tail.c]=true;
							if(judge(tail.a,tail.b,tail.c))
								return tail.step;
							//printf("%d %d %d\n",tail.a,tail.b,tail.c);
							q.push(tail);
						}
					}
					break;
				}
				case 2:
				{
					if(front.a>0&&front.c<b)
					{
						int k1=front.a-(b-front.c),k2;
						if(k1<0)
						{
							k1=0;
							k2=front.a+front.c;
						}
						else
						{
							k1=front.a-(b-front.c);
							k2=b;
						}
						if(vis[k1][front.b][k2]==false)
						{
							tail.a=k1;
							tail.b=front.b;
							tail.c=k2;
							tail.step=front.step+1;
							vis[tail.a][tail.b][tail.c]=true;
							if(judge(tail.a,tail.b,tail.c))
								return tail.step;
							//printf("%d %d %d\n",tail.a,tail.b,tail.c);
							q.push(tail);
						}
					}
					break;
				}
				case 3:
				{
					if(front.b>0&&front.a<v)
					{
						int k2=front.b-(v-front.a),k1;
						if(k2<0)
						{
							k1=front.a+front.b;
							k2=0;
						}
						else
						{
							k2=front.b-(v-front.a);
							k1=v;
						}
						if(vis[k1][k2][front.c]==false)
						{
							tail.a=k1;
							tail.b=k2;
							tail.c=front.c;
							tail.step=front.step+1;
							vis[tail.a][tail.b][tail.c]=true;
							if(judge(tail.a,tail.b,tail.c))
								return tail.step;
							//printf("%d %d %d\n",tail.a,tail.b,tail.c);
							q.push(tail);
						}
					}
					break;
				}
				case 4:
				{
					if(front.b>0&&front.c<b)
					{
						int k1=front.b-(b-front.c),k2;
						if(k1<0)
						{
							k1=0;
							k2=front.b+front.c;
						}
						else
						{
							k1=front.b-(b-front.c);
							k2=b;
						}
						if(vis[front.a][k1][k2]==false)
						{
							tail.a=front.a;
							tail.b=k1;
							tail.c=k2;
							tail.step=front.step+1;
							vis[tail.a][tail.b][tail.c]=true;
							if(judge(tail.a,tail.b,tail.c))
								return tail.step;
							//printf("%d %d %d\n",tail.a,tail.b,tail.c);
							q.push(tail);
						}
					}
					break;
				}
				case 5:
				{
					if(front.c>0&&front.a<v)
					{
						int k1=front.c-(v-front.a),k2;
						if(k1<0)
						{
							k1=0;
							k2=front.a+front.c;
						}
						else
						{
							k1=front.c-(v-front.a);
							k2=v;
						}
						if(vis[k2][front.b][k1]==false)
						{
							tail.a=k2;
							tail.b=front.b;
							tail.c=k1;
							tail.step=front.step+1;
							vis[tail.a][tail.b][tail.c]=true;
							if(judge(tail.a,tail.b,tail.c))
								return tail.step;
							//printf("%d %d %d\n",tail.a,tail.b,tail.c);
							q.push(tail);
						}
					}
					break;
				}
				case 6:
				{
					if(front.c>0&&front.b<a)
					{
						int k1=front.c-(a-front.b),k2;
						if(k1<0)
						{
							k1=0;
							k2=front.c+front.b;
						}
						else
						{
							k1=front.c-(a-front.b);
							k2=a;
						}
						if(vis[front.a][k2][k1]==false)
						{
							tail.a=front.a;
							tail.b=k2;
							tail.c=k1;
							tail.step=front.step+1;
							vis[tail.a][tail.b][tail.c]=true;
							if(judge(tail.a,tail.b,tail.c))
								return tail.step;
							//printf("%d %d %d\n",tail.a,tail.b,tail.c);
							q.push(tail);
						}
					}
					break;
				}
			}
		}
	}
	return -1;
}
int main() 
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    while(scanf("%d %d %d",&v,&a,&b)!=EOF&&a+b+v)
    {
    	memset(vis,false,sizeof(vis));
    	if(v%2==0)
    	{
    		t=v/2;
	    	int nape=bfs();
    		if(nape==-1)
    			printf("NO\n");
    		else
    			printf("%d\n",nape);
    	}
    	else
    		printf("NO\n");
    }
    return 0;
}