Chinaunix首页 | 论坛 | 博客
  • 博客访问: 474242
  • 博文数量: 117
  • 博客积分: 3195
  • 博客等级: 中校
  • 技术积分: 1156
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-04 01:44
文章分类

全部博文(117)

文章存档

2012年(5)

2011年(5)

2010年(46)

2009年(61)

我的朋友

分类: C/C++

2010-06-02 00:41:36

好久没写解题报告了, 刚刚做了个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;
}


阅读(1626) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~