POJ 3126 Prime Path (BFS)
程序员文章站
2023-12-24 12:03:57
...
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);
}
}