C - 非常可乐 HDU - 1495

2-Day1-C
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是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，听题解也没听太懂，照着大佬的代码直接打的
链接在这

https://blog.csdn.net/a1097304791/article/details/82884034?ops_request_misc=&request_id=&biz_id=102&utm_term=C%20-%20%E9%9D%9E%E5%B8%B8%E5%8F%AF%E4%B9%90%20HDU%20-%201495%20&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-82884034.pc_search_ecpm_flag&spm=1018.2226.3001.4187

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int maxn = 105;
int vis[maxn][maxn][maxn]; 
int v[3], ans;
struct Node{
    int v[3]; 
    int steps;
};
Node nextB, curB;
queue<Node> q;
void pour(int from, int to)
{

    int tmp = nextB.v[from]+nextB.v[to];
    if(tmp >= v[to]) nextB.v[to] = v[to];
    else nextB.v[to] = tmp;
    nextB.v[from] = tmp-nextB.v[to];
}
void Bfs()
{
    if(v[0] % 2 != 0) return;

    Node t;
    t.v[0] = v[0], t.v[1] = 0, t.v[2] = 0, t.steps = 0;
    q.push(t);
    vis[1][0][0] = 1;
    while(!q.empty()){
        curB = q.front();
        q.pop();

        if((curB.v[0]==curB.v[1]&&curB.v[0]!=0&&curB.v[2]==0)||(curB.v[0]==curB.v[2]&&curB.v[0]!=0&&curB.v[1]==0)||(curB.v[1]==curB.v[2]&&curB.v[1]!=0&&curB.v[0]==0)){
            ans = curB.steps;
            return;
        }

        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                if(i!=j){ 
                    nextB = curB;
                    pour(i, j); 
                    if(!vis[nextB.v[0]][nextB.v[1]][nextB.v[2]]){
                        nextB.steps++;
                        vis[nextB.v[0]][nextB.v[1]][nextB.v[2]]=1;
                        q.push(nextB);
                    }
                }
    }
}
int main()
{
    while(scanf("%d%d%d",&v[0],&v[1],&v[2])==3 && (v[0]!=0||v[1]!=0||v[2]!=0)){
        while(!q.empty()) q.pop();
        memset(vis,0,sizeof(vis));
        ans = 1<<30;
        Bfs();
        if(ans < (1<<30)) printf("%d\n",ans);
        else printf("NO\n");
    }
    return 0;
}