M - 非常可乐

https://vjudge.net/contest/65959#problem/M

题目大意

三个杯子，S, A, B分别代表它们的容量，S=A+B， 先给S这个杯子倒满水，A,B不倒水， 要求是利用三个杯子平分S里边的水，问如果可以求倒水的次数（三个杯子可以互相倒水）

解题思路

还是用BFS来做，三个杯子有6种倒法，难点就在于，如何倒水，以及最后判断是否平分，看了一个大神的做法，他是用数组的下标0，1，2来表示三个杯子，用它的值来表示杯子里的水量，这样只操作下标就可以操作杯子，具体看代码。

代码

# include <stdio.h>
# include <queue>
# include <string.h>

using namespace std;

#define max 105
struct node
{
    int cpu[3];//用数组方便对容器进行操作 
    int step;
};
int full[3];//设置容器的容量 
int dir[6][2] = {{0,1}, {0,2}, {1,0}, {1,2}, {2,0}, {2,1}};

int v[max][max][max] = {0};//标记数组，判断是否重复 

void turn(int &a, int &b, int fullb)//将a的水倒入b 
{
    if( a+b < fullb)
    {
        b += a;
        a = 0;
    }
    else
    {
        a -= (fullb - b);
        b = fullb;
    }
}
int PAN(node s)//因为三个杯子互相倒，任意两个杯子都有可能存放一半的水 
{
    if(s.cpu[0] + s.cpu[1] == full[0] && s.cpu[0] == s.cpu[1])
    return 1;
    if(s.cpu[0] + s.cpu[2] == full[0] && s.cpu[0] == s.cpu[2])
    return 1;
    if(s.cpu[1] + s.cpu[2] == full[0] && s.cpu[1] == s.cpu[2])
    return 1;   
    return 0;   
}

int BFS(node s)
{
    queue<node>Q;
    Q.push(s);
    node q;
    while(Q.size())
    {
        s = Q.front();
        Q.pop();

        if(PAN(s))
          return s.step;

        for(int i = 0; i<6; i++)
        {
            q = s;
            turn(q.cpu[dir[i][0]], q.cpu[dir[i][1]], full[dir[i][1]]);
            if(v[ q.cpu[0] ][q.cpu[1]][q.cpu[2]] == 0)
            {
                q.step+=1;
            v[ q.cpu[0] ][q.cpu[1]][q.cpu[2]] = 1;
                Q.push(q);
            }
        }
    }
    return -1;

}


int main(void)
{
    node s;
    while(scanf("%d%d%d",&full[0], &full[1], &full[2]), full[0] + full[1]+full[2])
    {
        s.cpu[0] = full[0];
        s.step = s.cpu[1] = s.cpu[2] = 0;
        memset(v, 0, sizeof(v));

        int ans = BFS(s);
        if(ans == -1)
        printf("NO\n");
        else
        printf("%d\n",ans);
    }


    return 0;
}