poj3414 Pots[bfs]

时间：2010-06-02 来源：chhaya

http://acm.pku.edu.cn/JudgeOnline/problem?id=3414 好久没写解题报告了，刚刚做了个bfs，不管水不水，写个吧。
题意：有两个容器，容量分别是A，B，对它们有三个操作：充满，倒空，从容器1倒到容器2或者反过来倒，问至少要多少步骤，让其中一个里面液体的体积达到C，并输出那些步骤。
分析：这个嘛。。。。就是简单的BFS。没话说。代码被我写脑残了，这么多，自己也看得晕死。我发现我都不懂怎么写解题报告了。。。

#include <stdio.h>

struct str
{
    int ab[2]; //两个容器分别剩多少
    int op; //操作
    int parm; //对哪个容器的操作
    int pre; //前一步操作
}queue[101];

int mark[101][101];
int ans[101][2];
int ab[2], c;
struct str cur, tmp;
void print()
{
    int i=0;
    while(tmp.pre > 0)
    {
        ans[i][0] = tmp.op;
        ans[i++][1] = tmp.parm;
        tmp = queue[tmp.pre];
    }
    ans[i][0] = tmp.op;
    ans[i++][1] = tmp.parm;
    printf("%d\n", i);
    for(i--; i>=0; i--)
    {
        switch(ans[i][0])
        {
        case 1:
            printf("FILL(%d)\n", ans[i][1]);
            break;
        case 2:
            printf("DROP(%d)\n", ans[i][1]);
            break;
        case 3:
            printf("POUR(%d,%d)\n", ans[i][1], (ans[i][1]+1) % 3 == 0 ? 1 : 2);
            break;
        }
    }
}

int main()
{
    int rear, front, index=0, tmpp;

    scanf("%d%d%d", &ab[0], &ab[1], &c);
    if(c == 0)
    {
        printf("0\n");
        return 0;
    }
    front = rear = 0;
    queue[front].ab[0] = 0;
    queue[front].ab[1] = 0;
    queue[front].pre = 0;
    front++;
    mark[0][0] = 1;
    while(rear < front)
    {
        cur = queue[rear++];

        //fill(1)
        tmp = cur;
        tmp.ab[0] = ab[0];
        if(tmp.ab[0] == c)
        {
            tmp.op = 1;
            tmp.parm = 1;
            tmp.pre = rear-1;
            print();
            return 0;
        }
        else if(mark[tmp.ab[0]][tmp.ab[1]] == 0)
        {
            tmp.op = 1;
            tmp.parm = 1;
            tmp.pre = rear-1;
            queue[front++] = tmp;
            mark[tmp.ab[0]][tmp.ab[1]] = 1;
        }

        //fill(2)
        tmp = cur;
        tmp.ab[1] = ab[1];

        if(tmp.ab[1] == c)
        {
            tmp.op = 1;
            tmp.parm = 2;
            tmp.pre = rear-1;
            print();
            return 0;
        }
        else if(mark[tmp.ab[0]][tmp.ab[1]] == 0)
        {

            tmp.op = 1;
            tmp.parm = 2;
            tmp.pre = rear-1;
            queue[front++] = tmp;
            mark[tmp.ab[0]][tmp.ab[1]] = 1;
        }

        //drop(1)
        tmp = cur;
        tmp.ab[0] = 0;
        if(mark[tmp.ab[0]][tmp.ab[1]] == 0)
        {
            tmp.pre = rear-1;
            tmp.parm = 1;
            tmp.op = 2;
            queue[front++] = tmp;
            mark[tmp.ab[0]][tmp.ab[1]] = 1;
        }
        //drop(2)
        tmp = cur;
        tmp.ab[1] = 0;
        if(mark[tmp.ab[0]][tmp.ab[1]] == 0)
        {
            tmp.pre = rear-1;
            tmp.parm = 2;
            tmp.op = 2;
            queue[front++] = tmp;
            mark[tmp.ab[0]][tmp.ab[1]] = 1;
        }
        //pour(2, 1);
        tmp = cur;
        if(tmp.ab[0] + tmp.ab[1] >= ab[0])
        {
            tmpp = tmp.ab[0];
            tmp.ab[0] = ab[0];
            tmp.ab[1] = tmpp+tmp.ab[1]-ab[0];
        }
        else
        {
            tmp.ab[0] += tmp.ab[1];
            tmp.ab[1] = 0;
        }
        if(tmp.ab[0] == c || tmp.ab[1] == c)
        {
            tmp.op = 3;
            tmp.parm = 2;
            tmp.pre = rear-1;
            print();
            return 0;
        }
        else if(mark[tmp.ab[0]][tmp.ab[1]] == 0)
        {
            tmp.op = 3;
            tmp.parm = 2;
            tmp.pre = rear-1;
            queue[front++] = tmp;
            mark[tmp.ab[0]][tmp.ab[1]] = 1;
        }

    //    pour(1, 2);
        tmp = cur;
        if(tmp.ab[0] + tmp.ab[1] >= ab[1])
        {
            tmpp = tmp.ab[1];
            tmp.ab[1] = ab[1];
            tmp.ab[0] = tmp.ab[0]+tmpp-ab[1];
        }
        else
        {
            tmp.ab[1] += tmp.ab[0];
            tmp.ab[0] = 0;
        }
        if(tmp.ab[0] == c || tmp.ab[1] == c)
        {
            tmp.op = 3;
            tmp.parm = 1;
            tmp.pre = rear-1;
            print();
            return 0;
        }
        else if(mark[tmp.ab[0]][tmp.ab[1]] == 0)
        {
            tmp.op = 3;
            tmp.parm = 1;
            tmp.pre = rear-1;
            queue[front++] = tmp;
            mark[tmp.ab[0]][tmp.ab[1]] = 1;
        }
    }
    printf("impossible\n");
    return 0;
}