欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 3126 Prime Path (BFS)

程序员文章站 2023-12-24 12:03:57
...

POJ 3126 Prime Path (BFS)POJ 3126 Prime Path (BFS)

【题目链接】http://poj.org/problem?id=3126

【题目大意】

给你两个四位数的素数,通过改变其中的一个数,每次只允许改变一位数,而且改变之后的数也必须是素数,问最少通过改变几次变成后一个四位的素数。如果不能改变成后面的四位素数则输出Impossible

【题解】

不罚时,每次改变四位中的一位入队;
可以先处理出四位素数,节省时间。

#include <queue>
#include <cstdio>
#include <locale>
#include <cstring>
#include <algorithm>
#define clr(a) memset(a,0,sizeof(a))
using namespace std;
const int N=1e4;
queue<int> q;
int T,a,b,ans=0,np[N],tot=0,p[N],stp[N],vis[N],num[5],pw[5]={0,1000,100,10,1};
inline int sieve(){//线筛模板
	np[0]=np[1]=1;
	for(int i=2;i<N;i++){
		if(!np[i]) p[++tot]=i;
		for(int j=1;j<=tot&&i*p[j]<N;j++)
			{np[i*p[j]]=1;if(i%p[j]==0) break;}
	}
}inline int search(int x,int d){//改变每一位
	for(int i=(d==1)?1:0;i<=9;i++){
		if(i==num[d]) continue;
		int tar=0;
		for(int j=1;j<=4;j++)
			tar+=(j==d?i:num[j])*pw[j];
		if(!np[tar]&&!vis[tar])
			vis[tar]=1,stp[tar]=stp[x]+1,q.push(tar);		
	}
}inline void bfs(int x){
	clr(stp),clr(vis);
	while(q.size()) q.pop();
	q.push(x);
	while(q.size()){
		x=q.front();q.pop();
		if(x==b) return ;
		num[1]=x/1000;
		num[2]=x%1000/100;
		num[3]=x%100/10;
		num[4]=x%10;
		for(int i=1;i<=4;i++) search(x,i);//枚举
	}
}inline int rd(){//卡常必备
  	int x=0,f=1;
        char c=0;
 	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
  	while(isdigit(c))x=(x<<3)+(x<<1)+(c-'0'),c=getchar();
  	return x*f;
}inline void write(int x){
  	static int st[35];int tp=0;
  	do{st[tp++]=x%10,x/=10;}while(x);
  	while(tp) putchar(st[--tp]+48);
}int main(){//简洁明了![在这里插入图片描述](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12101/d9bfb4a01c72c898ca022d9edfc9640a3b406b36.png)
	sieve(),T=rd();
	while(T--){
		a=rd(),b=rd();
		bfs(a);
		write(stp[b]),putchar(10);
	}
}
相关标签: 简单搜索

上一篇:

下一篇: