题意:给你2个素数,a,b,问你a经过多少次变换才能变成b.
一次变换只能改变a的一个位,并且改变后的a必须是素数。
思路:简单bfs。注意每次改变的a。
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <queue> #include <set> #include <vector> #include <stack> #include <map> #include <iomanip> #define PI acos(-1.0) #define Max 2005 #define inf 1<<28 using namespace std; bool flag[10005]; void prime()//素数表 { flag[0]=1; flag[1]=1; for(int i=2; i<=10000; i++) { if(!flag[i]) { for(int j=2*i; j<=10000; j+=i) flag[j]=1; } } } struct kdq { int num,step; } q[10000];//模拟队列 int jinzhi[4]= {1,10,100,1000}; bool visit[10005]; int bfs(int a,int b) { kdq aa; aa.num=a; aa.step=0; int num=0,cnt=0; q[num]=aa; num++; visit[aa.num]=1; kdq temp; while(num>cnt) { kdq temp=q[cnt]; cnt++; if(temp.num==b) { return temp.step; } for(int i=0; i<4; i++) { int kkk=temp.num;//构造去掉i+1位上数字的kkk if(i==0) kkk=kkk-kkk%10; if(i==1) kkk=kkk-kkk%100+kkk%10; if(i==2) kkk=kkk-kkk%1000+kkk%100; else if(i==3) kkk=kkk%1000; int j; if(i==3)//万位不能为0 j=1; else j=0; for(; j<=9; j++) { int kkkk=kkk+jinzhi[i]*j;//构造改变后的数 if(!flag[kkkk]&&!visit[kkkk]) { kdq aaa; aaa.num=kkkk; aaa.step=temp.step+1; q[num]=aaa; num++; visit[kkkk]=1; } } } } } int main() { int i,j,k,l,n,m; int a,b; cin>>n; prime(); for(i=0; i<n; i++) { memset(q,0,sizeof(q)); memset(visit,0,sizeof(visit)); scanf("%d%d",&a,&b); cout<<bfs(a,b)<<endl; } return 0; }
A完之后才发现自己连impossible的情况都没判断。。。给这水数据跪了。。