洛谷P1215 [USACO1.4]母亲的牛奶 Mother's Milk

P1215 [USACO1.4]母亲的牛奶 Mother's Milk

217通过
348提交
题目提供者该用户不存在
标签USACO
难度普及/提高-

提交讨论题解

最新讨论

暂时没有讨论

题目描述

农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数，最初，A和B桶都是空的，而C桶是装满牛奶的。有时，农民把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。

写一个程序去帮助农民找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。

输入输出格式

输入格式：

单独的一行包括三个整数A,B和C。

输出格式：

只有一行，升序地列出当A桶是空的时候，C桶牛奶所剩量的所有可能性。

输入输出样例

输入样例#1：

[输入1]

8 9 10

[输入2]

2 5 10

输出样例#1：

[输出1]

1 2 8 9 10

[输出2]

5 6 7 8 9 10

说明

题目翻译来自NOCOW。

USACO Training Section 1.4

分析：题目只给出了三个杯子，那么只有六种操作完全可以枚举出来嘛！其实也就是个暴力，注意记录一下已经到达的状态就好了.

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int A, B, C;
int vis[21][21][21],vis2[21],ans[21],sizee;

void dfs(int a, int b, int c)
{
    if (vis[a][b][c])
        return;
    vis[a][b][c] = 1;
    if (!a && !vis2[c])
    {
        ans[++sizee] = c;
        vis2[c] = 1;
    }
    if (a > 0 && b < B)
    {
        int temp = min(B - b, a);
        dfs(a - temp, b + temp, c);
    }
    if (a > 0 && c < C)
    {
        int temp = min(C - c, a);
        dfs(a - temp, b, c + temp);
    }
    if (b > 0 && a < A)
    {
        int temp = min(A - a, b);
        dfs(a + temp, b - temp, c);
    }
    if (b > 0 && c < C)
    {
        int temp = min(C - c, b);
        dfs(a, b - temp, c + temp);
    }
    if (c > 0 && a < A)
    {
        int temp = min(A - a, c);
        dfs(a + temp, b, c - temp);
    }
    if (c > 0 && b < B)
    {
        int temp = min(B - b, c);
        dfs(a, b + temp, c - temp);
    }
}

int main()
{
    scanf("%d%d%d", &A, &B, &C);
    dfs(0, 0, C);
    sort(ans + 1, ans + 1 + sizee);
    for (int i = 1; i <= sizee; i++)
        printf("%d ", ans[i]);

    return 0;
}