题目大意:
素数路径
估计看数据就明白这道题什么意思了......给两个素数,都是四位数的素数,并且没有前导0,现在需要经过一种变换把一个素数转换成另一个,当然这种转换是有规则的,规则就是每次只能改变这个四位数的其中一位数字,当然改变后的数字也得是素数,问最少的改变次数是多少......
貌似还是广搜..............................................................................................不过做起来应该会麻烦点,要求素数,不过可以搞一个素数表这样判断起来更方便
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
using namespace std; #define maxn 10000 int p[maxn];//标记4位数的素数 int Prime(int n)
{
int i, k=sqrt(n); for(i=; i<=k; i++)
if(n % i == )
return ; return ;
}
int Turn(int n, int k)//把n的第k位转换成0
{
char s[]={}; sprintf(s, "%d", n);
s[k] = '';
sscanf(s, "%d", &n); return n;
}
int BFS(int s, int e)
{
int i, j, k, q;
int v[maxn]={};
queue<int> Q; Q.push(s);
v[s] = ; while(Q.size())
{
s = Q.front();Q.pop(); if(s == e)
return v[s]-; int t = ; for(i=; i<; i++)
{
q = Turn(s, i); for(k=; k<; k++)
{
j = q+k*t; if(p[j] == && v[j] == )
{
Q.push(j);
v[j] = v[s] + ;
}
} t /= ;
}
} return -;
} int main()
{
int i, s, e, T; for(i=; i<maxn; i++)
p[i] = Prime(i); scanf("%d", &T); while(T--)
{
scanf("%d%d", &s, &e); int ans = BFS(s, e); if(ans == -)
printf("Impossible\n");
else
printf("%d\n", ans);
} return ;
}