2019年上交机试第二题

给出三个杯子的容量ABC ， 其中刚开始时C杯是满的，AB是空的。
现在在保证不会有漏水的情况下进行如下操作：
将一个杯子x的水倒到另一个杯子y中，如果x空了或者y满了就停止（满足其中一个条件才停下）
现问C中水量有多少种可能性（A,B,C为非负整数）
60% case A,B,C<=100
100% case A,B,C<=4000
Sample Input
0 5 5
Sample Output
2

Sample Input
2 2 4
Sample Output
3

手动测试了几个例子都没问题,核心就是BFS

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

//BFS

struct cups {
    int water[3];
};

const int MAXN = 4000 + 10;

bool visitab[MAXN][MAXN];
bool visitc[MAXN];

int main() {
    int v[3];
    scanf("%d%d%d", &v[0], &v[1], &v[2]);
    queue<cups> myqueue;
    cups head = {{0, 0, v[2]}};        //含数组的结构体初始化
    myqueue.push(head);
    for (int i = 0; i <= v[2]; ++i) {
        visitc[i] = false;
        for (int j = 0; j <= v[2]; ++j) {
            visitab[i][j] = false;
        }
    }
    visitab[0][0] = true;
    visitc[v[2]] = true;
    int c = 1;
    while (!myqueue.empty()) {
        cups head = myqueue.front();
        myqueue.pop();
        for (int i = 0; i < 3; ++i) {       //i往j里倒水
            for (int j = 0; j < 3; ++j) {
                cups current = head;
                if (v[i] == 0 || v[j] == 0 || i == j) {       //两个杯中有一个没体积,或者是同一个杯子
                    continue;
                }
                if (current.water[i] == 0 || current.water[j] == v[j]) {    //i空或者j满都不行
                    continue;
                } else {
                    if (current.water[i] >= v[j] - current.water[j]) {
                        current.water[i] -= v[j] - current.water[j];
                        current.water[j] = v[j];
                    } else {
                        current.water[j] += current.water[i];
                        current.water[i] = 0;
                    }
                }
                if (!visitc[current.water[2]]) {
                    c++;
                    visitc[current.water[2]] = true;
                }
                if (!visitab[current.water[0]][current.water[1]]) {        //如果当前情况没出现过，入队
                    myqueue.push(current);
                    visitab[current.water[0]][current.water[1]] = true;
                }
            }
        }
    }
    printf("%d\n", c);
    return 0;
}