The Fourth Dimension Space

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

統計

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

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

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

搜索

閱讀排行榜

評論排行榜

POJ 3126-Prime Path 廣度優先搜索BFS

不知道數論里面是不是有相關的公式，總之這道題我做的有點暴力，呵呵，一個BFS搞定；
要說具體的算法的話，就是【】【】【】【】這四個數位按從左到右的順序每次改變一個位置上的數字，如果這個數字是質數，就把它放入隊列，并記錄下到達這個數字所要經歷的步數即可，然后循環搜索，搜到跳出。。。
有點遺憾的是，這道題我寫的有點長，如果你有更好的想法，不妨告訴我哦謝謝啦O(∩_∩)O~

#include <iostream>

#include <algorithm>

#include<cstdio>

using namespace std;

bool prim[10000];

struct node

{

int n;

int step;

}line[100001];

int visited[10000];

int main()

{

int n,m;

int i,j;

for(i=2;i<=10000;i++)

{

if(prim[i]==true)

continue;

for(j=2;j<=10000;j++)

{

if(i*j>10000)

break;

prim[i*j]=true;

}

/////////////////////////////////////////////////////////////////////////////////////////

int testcase;

int front;

int rear;

scanf("%d",&testcase);

for(j=1;j<=testcase;j++)

{

memset(visited,false,sizeof(visited));

for(i=1;i<=10000;i++)

{

line[i].n=0;

line[i].step=0;

}

front=1;

rear=1;

scanf("%d%d",&n,&m);

line[1].n=n;

line[1].step=0;

while(front<=rear)

{

if(line[front].n==m)

break;

if(visited[line[front].n]==0)

{

visited[line[front].n]=1;

int k;

for(k=1;;k++)

{

if(line[front].n-k*1000>=1000)

{

if (prim[line[front].n-k*1000]==0&&visited[line[front].n-k*1000]==false)

{

rear++;

line[rear].n=line[front].n-k*1000;

line[rear].step=line[front].step+1;

}

else

break;

}

for(k=1;;k++)

{

if(line[front].n+k*1000<10000)

{

if(prim[line[front].n+k*1000]==0&&visited[line[front].n+k*1000]==false)

{

rear++;

line[rear].n=line[front].n+k*1000;

line[rear].step=line[front].step+1;

}

else

break;

}

for(k=1;;k++)

{

if(line[front].n%1000-k*100>=0)

{

if(prim[line[front].n-k*100]==0&&visited[line[front].n-k*100]==false)

{

rear++;

line[rear].n=line[front].n-k*100;

line[rear].step=line[front].step+1;

}

else

break;

}

for(k=1;;k++)

{

if(line[front].n%1000+k*100<1000)

{

if(prim[line[front].n+k*100]==0&&visited[line[front].n+k*100]==false)

{

rear++;

line[rear].n=line[front].n+k*100;

line[rear].step=line[front].step+1;

}

else

break;

}

for(k=1;;k++)

{

if(line[front].n%100-k*10>=0)

{

if(prim[line[front].n-k*10]==0&&visited[line[front].n-k*10]==false)

{

rear++;

line[rear].n=line[front].n-k*10;

line[rear].step=line[front].step+1;

}

else

break;

}

for(k=1;;k++)

{

if(line[front].n%100+k*10<100)

{

if(prim[line[front].n+k*10]==0&&visited[line[front].n+k*10]==false)

{

rear++;

line[rear].n=line[front].n+k*10;

line[rear].step=line[front].step+1;

}

else

break;

}

for(k=1;;k++)

{

if(line[front].n%10-k*1>=0)

{

if(prim[line[front].n-k*1]==0&&visited[line[front].n-k*1]==false)

{

rear++;

line[rear].n=line[front].n-k*1;

line[rear].step=line[front].step+1;

}

else

break;

}

for(k=1;;k++)

{

if(line[front].n%10+k*1<10)

{

if(prim[line[front].n+k*1]==0&&visited[line[front].n+k*1]==false)

{

rear++;

line[rear].n=line[front].n+k*1;

line[rear].step=line[front].step+1;

}

else

break;

}

front++;

}

if(front>rear)

printf("Impossible\n");

else

printf("%d\n",line[front].step);

}

system("pause");

return 0;

}

posted on 2009-02-27 22:31 abilitytao 閱讀(1326) 評論(0) 編輯收藏引用

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




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 3126-Prime Path 廣度優先搜索BFS