$$\color{Purple}{kuangbin题解目录}$$
描述
给定两个四位质数 $A$ 和 $B$,你需要通过最少的操作次数将 $A$ 变为 $B$。
每次操作只能改变当前数的其中一位数字,并且每次操作过后,当前数必须仍然是一个质数。
例如,将 $1033$ 变为 $8179$,最少需要进行 $6$ 次操作,具体操作为:
1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179
请计算并输出所需要的最少操作次数。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据占一行,包含两个四位质数 $A$ 和 $B$。
输出格式
每组数据输出一行答案,表示所需最少操作次数。
如果无法做到,则输出 Impossible
。
经实际测试,不存在无解情况,特此声明。
数据范围
$1 \\le T \\le 100$。
$1000 \\le A,B \\le 9999$,
保证 $A$ 和 $B$ 都是质数。
输入样例:
3
1033 8179
1373 8017
1033 1033
输出样例:
6
7
0
思路
每一个数最多$9\times 4$的变化,利用bfs找出最短路径即可.
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define MAXN 10010
using namespace std;
int t,start_,end_;
int primes[MAXN],is_prime[MAXN],cnt;//判断是否为素数
int vis[MAXN];//标记搜索是否使用过
struct node{
int num;
int step;
};
void get_primes(int n)
{//欧拉筛
for(int i=2;i<=n;i++)
{
if(vis[i]==0)
primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++)
{
is_prime[primes[j]*i]=1;
if(i%primes[j]==0)
break;
}
}
}
int bfs()
{
queue<node> q;
memset(vis,0,sizeof(vis));
q.push({start_,0});
vis[start_]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
if(temp.num==end_)
return temp.step;
int x[4]={temp.num/1000,temp.num/100%10,temp.num/10%10,temp.num%10};
//分别存储千位、百位、十位、个位
for(int i=0;i<=3;i++)
{
int tempnum=x[i];//暂存该位
for(int j=0;j<=9;j++)
{
if(tempnum!=j)
{
x[i]=j;//修改该位
int sum=1000*x[0]+100*x[1]+10*x[2]+x[3];
if(is_prime[sum]==0&&vis[sum]==0&&sum>=1000&&sum<=9999)
{
vis[sum]=1;
q.push({sum,temp.step+1});
}
}
}
x[i]=tempnum;//复原该位
}
}
return -1;
}
int main()
{
get_primes(10000);
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&start_,&end_);
printf("%d\n",bfs());
}
return 0;
}