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 阅读(1039) 评论(0)  编辑 收藏 引用


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