首页 > 代码库 > 【USACO】milk3

【USACO】milk3

2024-07-04 02:50:07   225人阅读

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

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

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

int mothersmilk(int a, int b, int c)
{
    int aa, bb, cc;
    int flag = 0;

    aa = a, bb = b, cc = c;
    pour(&aa, A, &bb, B);
    if(state[aa][bb][cc] != 1)
    {
        state[aa][bb][cc] = 1;
        mothersmilk(aa, bb, cc); //
        flag++;
    }

    aa = a, bb = b, cc = c;
    pour(&bb, B, &aa, A);
    if(state[aa][bb][cc] != 1)
    {
        state[aa][bb][cc] = 1;
        mothersmilk(aa, bb, cc);
    }

    aa = a, bb = b, cc = c;
    pour(&aa, A, &cc, C);
    if(state[aa][bb][cc] != 1)
    {
        state[aa][bb][cc] = 1;
        mothersmilk(aa, bb, cc); //
    }

    aa = a, bb = b, cc = c;
    pour(&cc, C, &aa, A);
    if(state[aa][bb][cc] != 1)
    {
        state[aa][bb][cc] = 1;
        mothersmilk(aa, bb, cc);
    }

    aa = a, bb = b, cc = c;
    pour(&bb, B, &cc, C);
    if(state[aa][bb][cc] != 1)
    {
        state[aa][bb][cc] = 1;
        mothersmilk(aa, bb, cc); //
    }

    aa = a, bb = b, cc = c;
    pour(&cc, C, &bb, B);
    if(state[aa][bb][cc] != 1)
    {
        state[aa][bb][cc] = 1;
        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[21][21][21];  //存储状态 出现过为1 未出现过为0
int A, B, C;

int pour(int *a, int fulla, int *b, int fullb) //a向b倒水
{
    if(*b == fullb || *a == 0) //若a没水 或 b满 a不能向b倒水 状态不变
    {
        return 1;
    }
    if(*b != fullb) //b不满
    {
        if(*a <= fullb - *b) //a倒光
        {
            *b = *b + *a;
            *a = 0;
        }
        else  //b倒满
        {
            *a = *a - (fullb - *b);
            *b = fullb;
        }
    }
    return 0;
}


int main()
{
    FILE *in, *out;
    in = fopen("milk3.in", "r");
    out = fopen("milk3.out", "w");
    int ans[21] = {0};
    int i, j ,k;
    
    fscanf(in, "%d %d %d", &A, &B, &C);

    for(i = 0; i <= 20; i++)
    {
        for(j = 0; j <= 20; j++)
        {
            for(k = 0; k <= 20; k++)
            {
                state[i][j][k] = 0;
            }
        }
    }
    state[0][0][C] = 1;

    int flag = 0;
    do{
        flag = 0;   //注意：flag一定要写在这里 因为在扩展过程中，需要对state的所有状态循环多次 以防止在大序号状态下扩展了小序号状态 比如 2 0 8 扩展为 0 2 8 因为0 2 8的状态已经超过了 所以还要重新遍历一遍才可以
        for(i = 0; i <= A; i++)
        {
            for(j = 0; j <= B; j++)
            {
                for(k = 0; k <= C; k++)
                {
                    if(state[i][j][k] == 1)
                    {
                        int aa, bb, cc;
                        aa = i, bb = j, cc = k;
                        pour(&aa, A, &bb, B);
                        if(state[aa][bb][cc] == 0)
                        {
                            state[aa][bb][cc] = 1;
                            flag++;
                        }

                        aa = i, bb = j, cc = k;
                        pour(&bb, B, &aa, A);
                        if(state[aa][bb][cc] == 0)
                        {
                            state[aa][bb][cc] = 1;
                            flag++;
                        }

                        aa = i, bb = j, cc = k;
                        pour(&aa, A, &cc, C);
                        if(state[aa][bb][cc] == 0)
                        {
                            state[aa][bb][cc] = 1;
                            flag++;
                        }

                        aa = i, bb = j, cc = k;
                        pour(&cc, C, &aa, A);
                        if(state[aa][bb][cc] == 0)
                        {
                            state[aa][bb][cc] = 1;
                            flag++;
                        }

                        aa = i, bb = j, cc = k;
                        pour(&bb, B, &cc, C);
                        if(state[aa][bb][cc] == 0)
                        {
                            state[aa][bb][cc] = 1;
                            flag++;
                        }

                        aa = i, bb = j, cc = k;
                        pour(&cc, C, &bb, B);
                        if(state[aa][bb][cc] == 0)
                        {
                            state[aa][bb][cc] = 1;
                            flag++;
                        }
                        state[i][j][k]++;
                    }
                    
                }
            }
        }
    }while(flag > 0);



        for(j = 0; j <= 20; j++)
        {
            for(k = 0; k <= 20; k++)
            {
                if(state[0][j][k] != 0 && ans[k] == 0)
                {
                    ans[k] = 1;
                }
            }
        }

    for(i = 0; i < C; i++)
    {
        if(ans[i] == 1)
        {
            fprintf(out, "%d ", i);
        }
    }
    fprintf(out, "%d\n", C);

    return 0;
}

 


联系
我们