M - 非常可乐 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

#include<cstdio>
#include<queue>
#include<string.h>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int a[101][101][101];//标记到达某种状态需要倒的次数
struct k{
    int x,y,z;
};
int main()
{
    int s,n,m;
    while(scanf("%d%d%d",&s,&n,&m)!=EOF){
        int cnt=-1;
        if(n==0&&s==0&&m==0)break;
        if(n<m){
            int t=n;n=m;m=t;
        }
        memset(a,-1,sizeof(a));
        a[s][0][0]=0;
        queue<k>q;
        k p;
        p.x=s;p.y=0,p.z=0;
        q.push(p);
        if(s%2==0)
        while(q.size()){
            k b=q.front();
            q.pop();
            if(b.x==b.y&&b.z==0){cnt=a[b.x][b.y][b.z];break;}
            k c;
            int d=a[b.x][b.y][b.z];
            if(b.y!=0){//先判向瓶子里倒水的情况，因为不可能溢出，所以一定是杯子倒干
            c.x=b.y+b.x;c.y=0;c.z=b.z;
            if(a[c.x][0][c.z]==-1){
            q.push(c); a[c.x][0][c.z]=d+1;
            }
            }
            if(b.z!=0){
            c.x=b.z+b.x;c.y=b.y;c.z=0;
            if(a[c.x][c.y][c.z]==-1){
                q.push(c);a[c.x][c.y][c.z]=d+1;
            }
            }
            if(b.y<n){//接着判断向一个杯子倒的情况，如果不能倒满，就将倒的杯子或瓶子倒空，否责将该杯子倒满
                if(b.z+b.y>n){
                    c.x=b.x;c.y=n;c.z=b.z+b.y-n;
                    if(a[c.x][c.y][c.z]==-1){
                        q.push(c);a[c.x][c.y][c.z]=d+1;
                    }
                }
                else{
                    c.x=b.x;c.y=b.y+b.z;c.z=0;
                    if(a[c.x][c.y][c.z]==-1){
                        q.push(c);a[c.x][c.y][c.z]=d+1;
                    }
                }
                if(b.x+b.y>n){
                    c.x=b.x+b.y-n;c.y=n;c.z=b.z;
                    if(a[c.x][c.y][c.z]==-1){
                        q.push(c);a[c.x][c.y][c.z]=d+1;
                    }
                }
                else{
                    c.x=0;c.y=b.y+b.x;c.z=b.z;
                    if(a[c.x][c.y][c.z]==-1){
                        q.push(c);a[c.x][c.y][c.z]=d+1;
                    }
                }
            }
            if(b.z<m){
                if(b.y+b.z>m){
                    c.x=b.x;c.y=b.y+b.z-m;c.z=m;
                    if(a[c.x][c.y][c.z]==-1){
                        q.push(c);a[c.x][c.y][c.z]=d+1;
                    }
                }
                else{
                    c.x=b.x;c.y=0;c.z=b.y+b.z;
                    if(a[c.x][c.y][c.z]==-1){
                        q.push(c);a[c.x][c.y][c.z]=d+1;
                    }
                }
                if(b.x+b.z>m){
                    c.x=b.x+b.z-m;c.y=b.y;c.z=m;
                    if(a[c.x][c.y][c.z]==-1){
                        q.push(c);a[c.x][c.y][c.z]=d+1;
                    }
                }
                else{
                    c.x=0;c.y=b.y;c.z=b.x+b.z;
                    if(a[c.x][c.y][c.z]==-1){
                        q.push(c);a[c.x][c.y][c.z]=d+1;
                    }
                }
            }
        }
        if(cnt==-1)printf("NO\n");
        else printf("%d\n",cnt);
    }
    return 0;
}