Prime Path（BFS）

Prime Path

题目传送门

Prime Path

题目大意

给你二个素数n和m，每次可以将一个素数变成一个与其有一个数字不一样的素数，求最小步数使n变成m，不能变成的话输出"Impossible"

思路

直接标准的BFS求即可，好像把int定成long long用就会超时？？？注意一下

AC Code

#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<queue> using namespace std; #define endl '\n' #define INF 0x3f3f3f3f // #define TDS_ACM_LOCAL const int N=1e5 +9; int A, B; typedef struct node{ int v, sum; }node; bool vis[N]; int prime[N], x; //p存数的最大质因数 int a[N], cnt; //a存四位数的素数，cnt为个数 void oulasai(int n) //欧拉筛 { vis[1]=1; for(int i=2;i<=n;i++) { if(!vis[i]){ prime[x++]=i; if(prime[x-1]>1000) a[cnt++]=prime[x-1]; } for(int j=0;j<x;j++) { if(i*prime[j]>n) break; vis[i*prime[j]]=true; if(i%prime[j]==0) break; } } } bool check(int a, int b){ int sum=0; while(a!=0){ if(a%10!=b%10) sum++; a/=10; b/=10; } if(sum==1) return true; return false; } int BFS(){ memset(vis, 0, sizeof(vis)); queue<node> q; q.push({A,0}); vis[A]=1; node now; while(!q.empty()){ now=q.front(); q.pop(); if(now.v==B) return now.sum; for(int i=cnt-1; i>=0; i--){ node next=now; if(!vis[a[i]] && check(next.v, a[i])){ vis[a[i]]=1; next.v=a[i]; next.sum++; q.push(next); } } } return -1; } void solve(){ cin>>A>>B; int t=BFS(); if(t==-1) cout<<"Impossible"<<endl; else cout<<t<<endl; return ; } signed main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); #ifdef TDS_ACM_LOCAL freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin); freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout); #endif oulasai(10000); //先用欧拉筛筛选四位数以内的素数 int T; cin>>T; while(T--) solve(); return 0; }