The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

POJ 3414-Pots BFS （代码好长啊 ，建议大家不要看了）

有史以来写的最烂的一个程序，居然写到5000B，勉强16MS AC.
题意就是有名的倒水游戏，给你2个一定容量的容器，然后要求你配出一定两的溶液并输出每一步的决策；
此题的算法当然是BFS啦，不过貌似有人告诉我说数论里有更好的方法，我感觉也是这样，我写的代码实在是有点冗长。。。
    algorithm=搜索+回溯。   有这几个字就足够了；
值得一提的是，本题中不能将一个结点反复入队，而避免的方法不是更改flag标志，而是判断这个结点是否有前件。
我总结下这类题的规律：
一是BFS代码一般都很长；
二是要回溯的题目不能让你个元素二次入队。因为这样会修改已经设定好的元素的前件，到时候就无法回溯了。
代码还是贴上来吧，不值得学习，仅供参考；
#include <iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct node2
{
    int flag;
    int prex;
    int prey;

};

struct node
{
    int x;
    int y;
};



node line[10000000];
node record[100000];
node2 data[201][201];



int main ()
{

    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    int front=1;
    int rear=1;
    line[1].x=0;
    line[1].y=0;

    while(front<=rear)
    {

        if(line[front].x==c||line[front].y==c)
            break;


        if(data[line[front].x][line[front].y].flag==0)
        {
            data[line[front].x][line[front].y].flag=1;
            if(line[front].x!=a&&data[a][line[front].y].flag==0&&data[a][line[front].y].prex==0&&data[a][line[front].y].prey==0)
            {

                rear++;
                line[rear].x=a;
                line[rear].y=line[front].y;
                data[line[rear].x][line[rear].y].prex=line[front].x;
                data[line[rear].x][line[rear].y].prey=line[front].y;

            }
            if(line[front].y!=b&&data[line[front].x][b].flag==0&&data[line[front].x][b].prex==0&&data[line[front].x][b].prey==0)
            {

                rear++;
                line[rear].x=line[front].x;
                line[rear].y=b;
                data[line[rear].x][line[rear].y].prex=line[front].x;
                data[line[rear].x][line[rear].y].prey=line[front].y;
            }
            if(line[front].x!=0&&data[0][line[front].y].flag==0&&data[0][line[front].y].prex==0&&data[0][line[front].y].prey==0)
            {

                rear++;
                line[rear].x=0;
                line[rear].y=line[front].y;
                data[line[rear].x][line[rear].y].prex=line[front].x;
                data[line[rear].x][line[rear].y].prey=line[front].y;

            }
            if(line[front].y!=0&&data[line[front].x][0].flag==0&&data[line[front].x][0].prex==0&&data[line[front].x][0].prey==0)
            {

                rear++;
                line[rear].x=line[front].x;
                line[rear].y=0;
                data[line[rear].x][line[rear].y].prex=line[front].x;
                data[line[rear].x][line[rear].y].prey=line[front].y;
            }
            if(line[front].x!=0&&line[front].y!=b)
            {


                if(line[front].x+line[front].y>b&&data[line[front].x-b+line[front].y][b].flag==0&&data[line[front].x-b+line[front].y][b].prex==0&&data[line[front].x-b+line[front].y][b].prey==0)
                {
                    rear++;
                    int temp;
                    temp=b-line[front].y;

                    line[rear].x=line[front].x-temp;
                    line[rear].y=b;
                    data[line[rear].x][line[rear].y].prex=line[front].x;
                    data[line[rear].x][line[rear].y].prey=line[front].y;

                }
                else if(data[0][line[front].x+line[front].y].flag==0&&data[0][line[front].x+line[front].y].prex==0&&data[0][line[front].x+line[front].y].prey==0)
                {
                    rear++;
                    int temp;
                    line[rear].x=0;
                    line[rear].y=line[front].x+line[front].y;
                    data[line[rear].x][line[rear].y].prex=line[front].x;
                    data[line[rear].x][line[rear].y].prey=line[front].y;

                }
            }

                ////////////////////////////////////////////////////////////////////////////
            if(line[front].y!=0&&line[front].x!=a)
            {
    
                
                if(line[front].x+line[front].y>a&&data[a][line[front].y-a+line[front].x].flag==0&&data[a][line[front].y-a+line[front].x].prex==0&&data[a][line[front].y-a+line[front].x].prey==0)
                {
                    int temp;
                    rear++;
                    temp=a-line[front].x;
                    line[rear].y=line[front].y-temp;
                    line[rear].x=a;
                    data[line[rear].x][line[rear].y].prex=line[front].x;
                    data[line[rear].x][line[rear].y].prey=line[front].y;

                }
                else if(data[line[front].x+line[front].y][0].flag==0&&data[line[front].x+line[front].y][0].prex==0&&data[line[front].x+line[front].y][0].prey==0)
                {
                    int temp;
                    rear++;
                    line[rear].y=0;
                    line[rear].x=line[front].x+line[front].y;
                    data[line[rear].x][line[rear].y].prex=line[front].x;
                    data[line[rear].x][line[rear].y].prey=line[front].y;
                }
            }


        }
        front++;
    }

    if(front>rear)
    {
        printf("impossible\n");
        return 0;
    }
    int pos=1;
    int markx=line[front].x;
    int marky=line[front].y;
    int tempx;
    int tempy;
    while(1)
    {
        if(markx==0&&marky==0)
        {
            break;
        }
        record[pos].x=markx;
        record[pos].y=marky;
        int tempx=markx;
        int tempy=marky;
        markx=data[tempx][tempy].prex;
        marky=data[tempx][tempy].prey;
        pos++;
    }
    record[pos].x=0;
    record[pos].y=0;
    printf("%d\n",pos-1);

    int i;
    for(i=pos;i>=2;i--)
    {
        if(record[i].x==0&&record[i-1].x==a&&record[i].y==record[i-1].y)
            printf("FILL(1)\n");
        else if(record[i].y==0&&record[i-1].y==b&&record[i].x==record[i-1].x)
                printf("FILL(2)\n");
        else if(record[i].x!=0&&record[i-1].x==0&&record[i].y==record[i-1].y)
            printf("DROP(1)\n");
        else if(record[i].y!=0&&record[i-1].y==0&&record[i].x==record[i-1].x)
            printf("DROP(2)\n");
        else if(record[i].x>record[i-1].x)
            printf("POUR(1,2)\n");
        else if(record[i].x<record[i-1].x)
            printf("POUR(2,1)\n");
    }
    return 0;
}
    








posted on 2009-03-01 01:10 abilitytao 阅读(1042) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理