POJ 3126 Prime Path（BFS算法）

思路：宽度优先搜索（BFS算法）

#include<iostream>

#include<stdio.h>

#include<cmath>

#include<cstring>

using namespace std;

int a,b;

struct node{

	int num;

	int step;

};

node que[10000];//默认初始化为0

int visit[10000];//默认初始化为0

int prime(int d){

    if(d<=1) return 0;

    for(int i=2;i<=sqrt(double(d));i++)

        if(d%i==0) return 0;

    return 1;

}

void bfs(){

    int i;

    int p1,p2;

    p1=0;

    que[p1].num=a;

    que[p1].step=0;

    visit[a]=1;

    p2=1;

	if(a==b){//考虑 a , b 相等的时候

		printf("%d\n",0);

		return ;

	}

    while(p1<p2){

        node x=que[p1];

        p1++;

        int unit=x.num%10;//取出个位

        int decade=(x.num/10)%10;//取出十位

        for(i=1;i<=9;i=i+2){  //枚举个位,保证为奇数（偶数必定不是素数）

            int y=(x.num/10)*10+i;

			if(y==b) {  //如果找到了，直接退出

				printf("%d\n",x.step+1);

				return ;

			}

            if(visit[y]==0 &&prime(y)) {

                visit[y]=true;

                que[p2].num=y;

                que[p2].step=x.step+1;

                p2++;

            }

        }

		for(i=0;i<=9;i++){  //枚举十位

            int y=(x.num/100)*100+i*10+unit;

			if(y==b) { //如果找到了，直接退出

				printf("%d\n",x.step+1);

				return ;

			}

            if(visit[y]==0 &&prime(y)) {

                visit[y]=true;

                que[p2].num=y;

                que[p2].step=x.step+1;

                p2++;

            }

        }

        for(i=0;i<=9;i++){  //枚举百位

            int y=(x.num/1000)*1000+i*100+decade*10+unit;

			if(y==b)	{ //如果找到了，直接退出

				printf("%d\n",x.step+1);

				return ;

			}

            if(visit[y]==0 &&prime(y)){

                visit[y]=true;

                que[p2].num=y;

                que[p2].step=x.step+1;

                p2++;

            }

        }

        for(i=1;i<=9;i++)  {//枚举千位，保证千位不为0

            int y=i*1000+x.num%1000;

			if(y==b)	{ //如果找到了，直接退出

				printf("%d\n",x.step+1);

				return ;

			}

            if(visit[y]==0 &&prime(y))  {

                visit[y]=true;

                que[p2].num=y;

                que[p2].step=x.step+1;

                p2++;

            }

        }

    }

    printf("Impossible\n");

    return;

}

int main(){

	int n;

	scanf("%d",&n);

	while(n--)	{

		memset(visit,0,sizeof(visit));//不要忘记初始化

		scanf("%d%d",&a,&b);

		bfs();

	}

	return 0;

}

下面代码优化了一下判断素数的代码

int prime(int d){

	if(d==2) return 1;//特殊情况，偶数2是素数

    if( d<=1 || d%2==0 ) return 0;//排除d<=1时以及d为偶数时

	for(int i=3;i<=sqrt(double(d));i=i+2)

		if(d%i==0) return 0;

	return 1;

}

巴特西

POJ 3126 Prime Path（BFS算法）

最新文章

热门文章