The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統(tǒng)計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

POJ 3414-Pots BFS （代碼好長啊，建議大家不要看了）

有史以來寫的最爛的一個程序，居然寫到5000B，勉強16MS AC.
題意就是有名的倒水游戲，給你2個一定容量的容器，然后要求你配出一定兩的溶液并輸出每一步的決策；
此題的算法當然是BFS啦，不過貌似有人告訴我說數(shù)論里有更好的方法，我感覺也是這樣，我寫的代碼實在是有點冗長。。。
algorithm=搜索+回溯。有這幾個字就足夠了；
值得一提的是，本題中不能將一個結點反復入隊，而避免的方法不是更改flag標志，而是判斷這個結點是否有前件。
我總結下這類題的規(guī)律：
一是BFS代碼一般都很長；
二是要回溯的題目不能讓你個元素二次入隊。因為這樣會修改已經(jīng)設定好的元素的前件，到時候就無法回溯了。
代碼還是貼上來吧，不值得學習，僅供參考；

#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 閱讀(1052) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統(tǒng)計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 3414-Pots BFS （代碼好長啊，建議大家不要看了）

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統(tǒng)計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 3414-Pots BFS （代碼好長啊 ，建議大家不要看了）

POJ 3414-Pots BFS （代碼好長啊，建議大家不要看了）