计蒜客 无脑博士的试管们 【dfs】

题目链接：https://nanti.jisuanke.com/t/31

题目大意：

无脑博士有三个容量分别是A,B,C 升的试管，A,B,C 分别是三个从 1 到20 的整数，最初，A 和 B 试管都是空的，而 C 试管是装满硫酸铜溶液的。有时，无脑博士把硫酸铜溶液从一个试管倒到另一个试管中，直到被灌试管装满或原试管空了。当然每一次灌注都是完全的。由于无脑博士天天这么折腾，早已熟练，溶液在倒的过程中不会有丢失。

写一个程序去帮助无脑博士找出当 A 试管是空的时候，C 试管中硫酸铜溶液所剩量的所有可能性。

输入格式

输入包括一行，为空格分隔开的三个数，分别为整数 A,B,C。

输出格式

输出包括一行，升序地列出当 A 试管是空的时候，C 试管溶液所剩量的所有可能性。

样例输入

2 5 10

样例输出

5 6 7 8 9 10

#include <iostream>
using namespace std;

int f[21][21][21];
int A, B, C;

void dfs(int x, int y, int z)
{
    if (x + z > A)     //C向A倒
    {
        if (f[A][y][x + z - A] == 0)
        {
            f[A][y][x + z - A] = 1;
            dfs(A, y, x + z - A);
        }
    }
    else
    {
        if (f[x + z][y][0] == 0)
        {
            f[x + z][y][0] = 1;
            dfs(x + z, y, 0);
        }
    }
    if (y + z>B)   //C向B倒
    {
        if (f[x][B][y + z - B] == 0)
        {
            f[x][B][y + z - B] = 1;
            dfs(x, B, y + z - B);
        }
    }
    else
    {
        if (f[x][y + z][0] == 0)
        {
            f[x][y + z][0] = 1;
            dfs(x, y + z, 0);
        }
    }
    if (x + y >B)   //A向B倒
    {
        if (f[x + y - B][B][z] == 0)
        {
            f[x + y - B][B][z] = 1;
            dfs(x + y - B, B, z);
        }
    }
    else
    {
        if (f[0][x + y][z] == 0)
        {
            f[0][x + y][z] = 1;
            dfs(0, x + y, z);
        }
    }
    if (x + z > C)  //A向C倒
    {
        if (f[x + z - C][y][C] == 0)
        {
            f[x + z - C][y][C] = 1;
            dfs(x + z - C, y, C);
        }
    }
    else
    {
        if (f[0][y][x + z] == 0)
        {
            f[0][y][x + z] = 1;
            dfs(0, y, x + z);
        }
    }
    if (x + y > A)  //B向A倒
    {
        if (f[A][x + y - A][z] == 0)
        {
            f[A][x + y - A][z] = 1;
            dfs(A, x + y - A, z);
        }
    }
    else
    {
        if (f[x + y][0][z] == 0)
        {
            f[x + y][0][z] = 1;
            dfs(x + y, 0, z);
        }
    }
    if (y + z > C)   //B向C倒
    {
        if (f[x][y + z - C][C] == 0)
        {
            f[x][y + z - C][C] = 1;
            dfs(x, y + z - C, C);
        }
    }
    else
    {
        if (f[x][0][y + z] == 0)
        {
            f[x][0][y + z] = 1;
            dfs(x, 0, y + z);
        }
    }

}

int main()
{
    int i, j, k;
    void dfs(int x, int y, int z);
    cin >> A >> B >> C;
    for (i = 0; i < A + 1; i++)
        for (j = 0; j < B + 1; j++)
            for (k = 0; k < C + 1; k++)
                f[i][j][k] = 0;
    f[0][0][C] = 1;
    dfs(0, 0, C);
    for (k = 0; k < C + 1; k++)
        for (j = 0; j < B + 1; j++)
            if (f[0][j][k] > 0)
            {
                cout << k;
                if (k != C) cout << ' ';
            }
    return 0;
}

2018-05-14