问题描述:
农民约翰有三个容量分别是A,B,C 升的桶,A,B,C 分别是三个从1 到20 的整数,最初,A 和B 桶都是空的,而C 桶是装满牛奶的.有时,约翰把牛奶从一个桶倒到另一个桶中,直到被灌桶装满或原桶空了.当然每一次灌注都是完全的.由于节约,牛奶不会有丢失.
写一个程序去帮助约翰找出当A 桶是空的时候,C 桶中牛奶所剩量的所有可能性.(从小到大输出)
输入格式:
单独一行包括三个整数 A B C
输出格式:
只有一行,当A是空的时候,C桶牛奶所剩量的所有可能性。
输入样例:
8 9 10
输出样例:
1 2 8 9 10

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

int i, j, va, vb, vc;
int flag[21][21][21];
int ans[21];

void try(int a, int b, int c)
{
    if (flag[a][b][c]) return;
    flag[a][b][c] = 1;
    if (a==0)
    {
        ans[0] += 1;
        ans[ans[0]] = c;
    }
    if (a>0)
    {
        if (b<vb)
        {
            if (a+b>vb)
                try(a-(vb-b), vb, c);
            else
                try(0, a+b, c);
        }
        if (c<vc)
        {
            if (a+c>vc)
                try(a-(vc-c), b, vc);
            else 
                try(0, b, a+c);
        }
    }

    if (b>0)
    {
        if (a<va)
        {
            if (a+b>va)
                try(va, b-(va-a), c);
            else
                try(a+b, 0, c);
        }
        if (c<vc)
        {
            if (b+c>vc)
                try(a, b-(vc-c), vc);
            else 
                try(a, 0, b+c);
        }
    }
    if (c>0)
    {
        if (b<vb)
        {
            if (c+b>vb)
                try(a, vb, c-(vb-b));
            else
                try(a, c+b, 0);
        }
        if (a<va)
        {
            if (a+c>va)
                try(va, b, c-(va-a));
            else 
                try(a+c, b, 0);
        }
    }
}

int main()
{
    int t;
    scanf("%d %d %d", &va, &vb, &vc);
    memset(flag, 0, sizeof(flag));
    memset(ans, 0, sizeof(ans));
    try(0, 0, vc);

    for (i=ans[0]-1; i>=1; i--)
        for (j=1; j<=i; j++)
            if (ans[j]>ans[j+1])
            {
                t = ans[j];
                ans[j] = ans[j+1];
                ans[j+1] = t;
            }

    for (i=1; i<=ans[0]; i++)
        printf("%d ", ans[i]);
}