POJ 3126 Prime Path(BFS + 素数判定)

雨点打透心脏的1/2处 2024-02-17 19:07 22阅读 0赞

题意：给定两个四位素数作为终点和起点，每次可以改变起点数的某一位，且改变后的数仍然是素数，如果变换成终点数字输出最短步数，否则输出Impossible。

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int maxn=1e4+10;
    int d[maxn];
    int n,m;
    int a[4];
    bool is_prime(int v){
    	for(int i=2;i<=sqrt(v);i++){
    		if(v%i==0)return false;
    	}
    	return true;
    }
    void bfs(){
    	memset(d,-1,sizeof(d));
    	queue<int>q;
    	q.push(n);
    	d[n]=0;
    	while(!q.empty()){
    		int u=q.front();
    		q.pop();
    		if(u==m){
    			printf("%d\n",d[u]);
    			return ;
    		}
    		int t=u;
    		for(int i=3;i>=0;i--){
    			a[i]=t%10;
    			t/=10;
    		}
    		
    		for(int i=0;i<4;i++){
    			int temp=a[i];
    			for(int j=0;j<=9;j++){
    				if(j!=a[i]){
    					if(i==0 && j==0)continue;
    					a[i]=j;
    					int v=0;
    					for(int k=0;k<4;k++)
    						v=v*10+a[k];
    						if(d[v]==-1&&is_prime(v)){
    							q.push(v);
    							d[v]=d[u]+1;
    						} 
    				}
    			}
    			a[i]=temp;   //改回来 
    		}
    	}
    	printf("Impossible\n");
    } 
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d",&n,&m);
    		bfs();
    	} 
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，22人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3126 Prime Path(BFS + 素数判定)

题意：给定两个四位素数作为终点和起点，每次可以改变起点数的某一位，且改变后的数仍然是素数，如果变换成终点数字输出最短步数，否则输出Impossible。 includ

雨点打透心脏的1/2处/ 2024年02月17日 19:07/ 0 赞/ 23 阅读

相关 POJ 2689-Prime Distance(区间素数)

Prime Distance <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

向右看齐/ 2022年08月23日 00:37/ 0 赞/ 174 阅读

相关 POJ 3126-Prime Path（BFS-素数变换一位）

Prime Path <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</

秒速五厘米/ 2022年07月12日 08:16/ 0 赞/ 80 阅读

相关 POJ 3126-Prime Path（BFS-素数变换一位）

Prime Path <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</

太过爱你忘了你带给我的痛/ 2022年07月12日 08:16/ 0 赞/ 90 阅读

相关 POJ - 3518 - Prime Gap（筛素数）

给出一个数字n，求n所在得一个区间的长度，区间是最近的两个素数为边界；那么n如果为素数的话，那么直接输出0；先打表，因为用的是前10万个素数，所以在打表的时候，记录素数

桃扇骨/ 2022年06月08日 11:20/ 0 赞/ 118 阅读

相关 Prime Path POJ - 3126 (BFS,素数距离)

The ministers of the cabinet were quite upset by the message from the Chief of Security

拼搏现实的明天。/ 2022年04月24日 02:58/ 0 赞/ 152 阅读

相关 POJ-3126-Prime Path

链接：https://vjudge.net/problem/POJ-3126 题意：给两个四位数的素数a,b。每次可以改变a的一个值使其成为一个新的四位数素数。

妖狐艹你老母/ 2022年01月10日 05:09/ 0 赞/ 90 阅读

相关 poj 3126 BFS

BFS得到的一定是最短路径。开始我还在纠结怎么才是最短的呢。其实BFS的题目有个共性（这不废话，哪一类题没有共性啊。呵呵）。以后做这种题自己慢慢总结吧。

柔情只为你懂/ 2021年12月17日 02:57/ 0 赞/ 296 阅读

相关素数判定

include<stdio.h> include<math.h> int prime(int n) { int i; f

青旅半醒/ 2021年11月02日 14:38/ 0 赞/ 331 阅读

相关 POJ3126 Prime Path

题目：给你两个四位的素数a，b。 a可以改变某一位上的数字变成c，但只有当c也是四位的素数时才能进行这种改变。请你计算a最少经过多少次上述变换才能变成b。例

电玩女神/ 2021年10月01日 01:10/ 0 赞/ 201 阅读