题目大意
在1000到10000的范围内，输入两个数，a,b。 b>a,现在要让你把a变成b。改变a四位数中的任何一位之后如果它为素数，就以他为基准继续变，直到它变成B（以素数为台阶）。
思路
BFS思想，逐一由千位变到个位，每一位由1变到9，没变一次，比对这个数是不是素数，如果是就将它保存到队列中，循环里每次处理的都是上一个数，这才是广搜的核心。再使用一个一维数组，用变化后的素数表示下标，用它对应的值来表示所要进行的步数。
先将1000到10000的所有素数都求出来保存到一个一维数组中(下标对应值为1),下标不是素数值为0.
代码
# include <stdio.h>
# include <queue>
# include <math.h>
# include <cstring>
# include <string.h>
using namespace std;
int num[10005];
void Prim(int a, int b)
{
int c;
for(int i = a; i<=b; i++)
{
int s = sqrt(i+0.5);
c = 0;
for(int j = 2; j<=s; j++)//j<=s,不要把=号忘记了
{
if(i%j == 0)
{
c = 1;
}
}
if(c == 0)
{
num[i] = 1;
}
}
}
int ban(int i, int s)
{
int c;
char a[6] = {0};
sprintf(a, "%d", s);
a[i] = '0';
sscanf(a, "%d", &c);
return c;
}
int BFS(int a, int b)
{
queue<int> Q;
Q.push(a);
//num[a] = 1;
int array[10000] = {0};
array[a] = 1;
while(Q.size())
{
int s = Q.front();
Q.pop();
if(s == b)
return array[s];
int n = 1000;
for(int i = 0; i<4; i++)//将该数字的每一位先逐一变成0，再逐一加上1000，100，10，1的倍数，再通过比较素数数组，看它是不是素数
{
int q = ban(i, s); //核心
for(int j = 0; j<=9; j++)
{
int h = q+n*j;
if(num[h] == 1 && array[h] == 0)
{
array[h] = array[s] + 1;
Q.push(h);
}
}
n/=10;
}
}
}
int main(void)
{
int m;
Prim(1000, 10000);
scanf("%d",&m);
while(m--)
{
int a, b;
scanf("%d%d",&a,&b);
int ans = BFS(a, b);
printf("%d\n",ans-1);
}
return 0;
}