简单bfs,处理的时候，用的Map没过，看来这个题得好好考虑考虑时间复杂度了
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
int visit[10010];
int visit2 [10010];
int prim(int x){
for(int j = 2;j*j <= x;j++)
if(x % j == 0)return 0;
return 1;
}
int pow(int a,int b){
int ans = 1;
for(int i = 1;i <= b;i++){
ans *= a;
}
return ans;
}
int main(){
memset(visit,0,sizeof(visit));
for(int i = 1000;i<=9999;i++){
if(prim(i))
visit[i] = 1;
}
int t;
scanf("%d",&t);
while(t--){
int ans;
int flag = 0;
int m,n;
memcpy(visit2,visit,sizeof(visit));//将后面的复制到前面
queue<int>q;
queue<int>q1;
scanf("%d%d",&m,&n);
q.push(m);
q1.push(0);
visit2[m] = 0;
while(! q.empty()){
int _x = q.front();
q.pop();
// printf("_x = %d",_x);
int _ceng =q1.front();
q1.pop();
if(_x == n){
flag = 1;
ans = _ceng;
break;
}
else{
int _nx;
//从第一位开始处理，逐个枚举结果，每一位有10种结果，一共有四位需要处理
for(int i = 0;i<4;i++)
for(int j = 0; j<=9; j++){
if(i == 0){
_nx = _x/10 * 10 + j;
if(visit2 [_nx]){
//printf("_nx = %d ",_nx);
q.push(_nx);
q1.push(_ceng +1);
visit2[_nx] = 0;
}
}
else {
_nx = _x / pow(10,i+1) * pow(10,i+1) + j * pow(10,i) + _x % pow(10,i);
if(visit2 [_nx]){
// printf("(!0)_nx = %d ",_nx);
q.push(_nx);
q1.push(_ceng +1);
visit2[_nx] = 0;
}
}
}
}
}
if(flag)printf("%d\n",ans);
else puts("Impossible");
}
} map超时代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
bool num[10001],used[10001];
int s,e;
void Prim()
{
memset(num,true,sizeof(num));
for(int i=2;i*i<10001;i++)
{
if(num[i])
{
for(int j=i+i;j<10000;j+=i)
num[j]=false;
}
}
memset(num,false,1000);
}
struct Point{
int x,step;
};
int d[4]={1,10,100,1000};
int BFS(int x)
{
queue<Point> que;
Point tp,ans;
int tx;
ans.x=x,ans.step=0;
used[x]=false,que.push(ans);
while(!que.empty())
{
tp=que.front();
que.pop();
for(int i=0;i<4;i++)
for(int j=0;j<=9;j++)
if(i==3&&j==0)continue;
else
{
if(j!=(tp.x/d[i]%10))
{
tx=((tp.x/d[i]/10)*10+j)*d[i]+tp.x%d[i];
if(used[tx])
{
used[tx]=false,ans.x=tx,ans.step=tp.step+1,que.push(ans);
if(ans.x==e)return ans.step;
}
}
}
}
return -1;
}
int main()
{
int T;
cin>>T;
Prim();
while(T--)
{
cin>>s>>e;
memcpy(used,num,10000);
if(s==e)cout<<"0"<<endl;
int x = BFS(s);
if(x == -1)puts("Impossible") ;
else cout<<BFS(s)<<endl;
}
} 时间复杂度分析：
待续
