【USACO】milk3

倒牛奶的问题，开始看感觉跟倒水的问题很像，想直接找规律，写个类似于循环取余的代码。但后来发现不行，因为这道题有三个桶，水量也是有限制的。只好用模拟的方法把所有的情况都试一遍。

建一个state[21][21][21]的数组存储出现过的状态。对于遍历状态，对每一种状态，分别采用六种处理方法，若有新状态出现这将新状态置为1，同时标记flag++；若所有循环之后，flag == 0，就说明遍历完成了。

开始脑子抽筋了，写了个多出口的程序，显然是错的。如下：

int mothersmilk(int a, int b, int c)

{

    int aa, bb, cc;

    int flag = ;

    aa = a, bb = b, cc = c;

    pour(&aa, A, &bb, B);

    if(state[aa][bb][cc] != )

    {

        state[aa][bb][cc] = ;

        mothersmilk(aa, bb, cc); //

        flag++;

    }

    aa = a, bb = b, cc = c;

    pour(&bb, B, &aa, A);

    if(state[aa][bb][cc] != )

    {

        state[aa][bb][cc] = ;

        mothersmilk(aa, bb, cc);

    }

    aa = a, bb = b, cc = c;

    pour(&aa, A, &cc, C);

    if(state[aa][bb][cc] != )

    {

        state[aa][bb][cc] = ;

        mothersmilk(aa, bb, cc); //

    }

    aa = a, bb = b, cc = c;

    pour(&cc, C, &aa, A);

    if(state[aa][bb][cc] != )

    {

        state[aa][bb][cc] = ;

        mothersmilk(aa, bb, cc);

    }

    aa = a, bb = b, cc = c;

    pour(&bb, B, &cc, C);

    if(state[aa][bb][cc] != )

    {

        state[aa][bb][cc] = ;

        mothersmilk(aa, bb, cc); //

    }

    aa = a, bb = b, cc = c;

    pour(&cc, C, &bb, B);

    if(state[aa][bb][cc] != )

    {

        state[aa][bb][cc] = ;

        mothersmilk(aa, bb, cc); //

    }
　　return 0;

//...

}

错误的原因在于，若是第一个if语句中的mothersmilk操作完了，一定会返回0，那后面的语句都起不到作用了。

后来发现，可以直接对所有的state变量循环，用for语句，逻辑就清楚多了，提交也AC了。正确的代码：

/*

ID: 13012131

LANG: C

TASK: milk3

*/

#include <stdio.h>

#include <assert.h>

int state[][][];  //存储状态 出现过为1 未出现过为0

int A, B, C;

int pour(int *a, int fulla, int *b, int fullb) //a向b倒水

{

    if(*b == fullb || *a == ) //若a没水 或 b满 a不能向b倒水 状态不变

    {

        return ;

    }

    if(*b != fullb) //b不满

    {

        if(*a <= fullb - *b) //a倒光

        {

            *b = *b + *a;

            *a = ;

        }

        else  //b倒满

        {

            *a = *a - (fullb - *b);

            *b = fullb;

        }

    }

    return ;

}

int main()

{

    FILE *in, *out;

    in = fopen("milk3.in", "r");

    out = fopen("milk3.out", "w");

    int ans[] = {};

    int i, j ,k;

    fscanf(in, "%d %d %d", &A, &B, &C);

    for(i = ; i <= ; i++)

    {

        for(j = ; j <= ; j++)

        {

            for(k = ; k <= ; k++)

            {

                state[i][j][k] = ;

            }

        }

    }

    state[][][C] = ;

    int flag = ;

    do{

        flag = ;   //注意：flag一定要写在这里 因为在扩展过程中，需要对state的所有状态循环多次 以防止在大序号状态下扩展了小序号状态 比如 2 0 8 扩展为 0 2 8 因为0 2 8的状态已经超过了 所以还要重新遍历一遍才可以

        for(i = ; i <= A; i++)

        {

            for(j = ; j <= B; j++)

            {

                for(k = ; k <= C; k++)

                {

                    if(state[i][j][k] == )

                    {

                        int aa, bb, cc;

                        aa = i, bb = j, cc = k;

                        pour(&aa, A, &bb, B);

                        if(state[aa][bb][cc] == )

                        {

                            state[aa][bb][cc] = ;

                            flag++;

                        }

                        aa = i, bb = j, cc = k;

                        pour(&bb, B, &aa, A);

                        if(state[aa][bb][cc] == )

                        {

                            state[aa][bb][cc] = ;

                            flag++;

                        }

                        aa = i, bb = j, cc = k;

                        pour(&aa, A, &cc, C);

                        if(state[aa][bb][cc] == )

                        {

                            state[aa][bb][cc] = ;

                            flag++;

                        }

                        aa = i, bb = j, cc = k;

                        pour(&cc, C, &aa, A);

                        if(state[aa][bb][cc] == )

                        {

                            state[aa][bb][cc] = ;

                            flag++;

                        }

                        aa = i, bb = j, cc = k;

                        pour(&bb, B, &cc, C);

                        if(state[aa][bb][cc] == )

                        {

                            state[aa][bb][cc] = ;

                            flag++;

                        }

                        aa = i, bb = j, cc = k;

                        pour(&cc, C, &bb, B);

                        if(state[aa][bb][cc] == )

                        {

                            state[aa][bb][cc] = ;

                            flag++;

                        }

                        state[i][j][k]++;

                    }

                }

            }

        }

    }while(flag > );

        for(j = ; j <= ; j++)

        {

            for(k = ; k <= ; k++)

            {

                if(state[][j][k] !=  && ans[k] == )

                {

                    ans[k] = ;

                }

            }

        }

    for(i = ; i < C; i++)

    {

        if(ans[i] == )

        {

            fprintf(out, "%d ", i);

        }

    }

    fprintf(out, "%d\n", C);

    return ;

}

巴特西

【USACO】milk3

最新文章

热门文章