一个企业做网站的目的/域名备案查询
题目链接:https://cn.vjudge.net/contest/309172#problem/Y
Sample Input
3
1033 8179
1373 8017
1033 1033
Sample Output
6
7
0
解析:所给的数字都是四位数，从第一个数变成第二个数，最少需要几次。变换规则：一次只能改变其中的一位数，且改变后的数字为素数，如1033到8179的变换规则：1033 ->1733-> 3733>3739 ->3779 >8779 ->8179,总共变换了6次，且变换过程中，每一位都是素数。
分析
1.素数打表是少不了的。
void solve(){for(int i=2;i<10001;i++){if(a[i]==0){for(int j=2*i;j<10001;j+=i)a[j]=1;}}
}
素数打表的原理:
i=2时，j=4,6,8,10…
i=3时，j=9,12,15…
i=4时，j=16,20,24…
i=5时，j=25,30,35…
将j全部标记，没标记的就是素数。
2.接着就是广搜，因为是四位数，所以for循环从1001到10000就行，要注意的是i为i+2,（偶数就不用考虑了）
代码：
1.用队列模拟
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int book[10001],a[10001]={0};
int m,n;
struct node{int x,step;
};
void solve(){for(int i=2;i<10001;i++){if(a[i]==0){for(int j=2*i;j<10001;j+=i)a[j]=1;}}
}
int main(){int T,flag;scanf("%d",&T);int a1,a2,b1,b2,c1,c2,d1,d2;solve();while(T--){flag=0;memset(book,0,sizeof(book));scanf("%d%d",&m,&n);if(m==n){printf("0\n");continue;}queue<node>q;node u,v;u.x=m,u.step=0;book[m]=1;q.push(u);while(!q.empty()){u=q.front();q.pop();a1=u.x/1000,b1=u.x/100%10,c1=u.x/10%10,d1=u.x%10;for(int i=1001;i<10000;i=i+2){if(book[i]==0&&a[i]==0)//是素数，并且没有出现过{a2=i/1000,b2=i/100%10,c2=i/10%10,d2=i%10;if(a1==a2&&b1==b2&&c1==c2||a1==a2&&b1==b2&&d1==d2||b1==b2&&c1==c2&&d1==d2||a1==a2&&c1==c2&&d1==d2){//更改其中的一位v.x=i,v.step=u.step+1;book[i]=1;q.push(v);if(i==n){flag=1;break;}}}}if(flag==1)break;}if(flag==1)printf("%d\n",v.step);elseprintf("Impossible.\n");}return 0;
}
2.用head和tail模拟
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int book[10005],x[10005]={0};
struct node{int x,step;
} s[10000];void solve(){for(int i=2; i<10005; i++){ //素数的判定if(x[i]==0){for(int j=2*i; j<10005; j+=i)x[j]=1;}}
}
int main(){int T,m,n,flag,head=1,tail=1;scanf("%d",&T);while(T--){solve();flag=0;scanf("%d%d",&m,&n);memset(book,0,sizeof(book));if(m==n){printf("0\n");continue;}head=tail=1;s[head].x=m,s[head].step=0,book[m]=1,tail++;int a,b,c,d,a1,b1,c1,d1;while(head<tail){a=s[head].x/1000,b=s[head].x/100%10,c=s[head].x/10%10,d=s[head].x%10;for(int i=1001; i<10000; i=i+2){if(x[i]==0&&book[i]==0){a1=i/1000,b1=i/100%10,c1=i/10%10,d1=i%10;if(a==a1&&b==b1&&c==c1||a==a1&&b==b1&&d==d1||b==b1&&c==c1&&d==d1||a==a1&&c==c1&&d==d1){s[tail].x=i;s[tail].step=s[head].step+1;book[i]=1;tail++;if(i==n){flag=1;break;}}}}if(flag==1)break;head++;}if(flag==1)printf("%d\n",s[tail-1].step);elseprintf("Impossible\n");}return 0;
}