Prime Path - POJ 3126

题意：

给你二个素数n和m，每次可以变换一位数字，变换完还是素数，问最少要几次才可以把n变成m。
记一个学到的判断素数的新方法：费马小定理: 如果p是一个质数，而整数a不是p的倍数，则有$a^{(p?1)}\equiv 1(modp)$,但是代码上还不太会用，有空去找找模板学一下。

思路：

广搜， 每个数都把个十百千位能变换的所有情况都放进队列，同时开一个$map$来记录得到每个数变换的次数，初始化为-1，那么这个$map$也可以实现记录一个数有没有进过队列，防止重复操作。对于符合要求的数$d[t]=d[t]+1$，然后把这个数放进队列。手动把个十百千位所有的数都存下来，剪一个小枝，个位不能是偶数，千位（首位） 不能是0。

代码

#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<cstring>
using namespace std;
int n, m;int ge[10] = {
    1, 3, 5, 7, 9};
int shi[10] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int bai[10] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int qian[10] = {
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10};bool isprime(int x)
{
    for (int i = 2; i <= sqrt(x); i ++ ){
    if (x % i == 0) return false;}return true;
}
int flag[10000];
void bfs()
{
    memset(flag, -1, sizeof flag);queue<int> q;q.push(n);flag[n] = 0;while (!q.empty()){
    int t = q.front();q.pop();if (t == m) break;//个位修改 for (int i = 0; i < 5; i ++ ){
    int xx = t / 10 * 10 + ge[i];if (flag[xx] == -1 && isprime(xx)){
    flag[xx] = flag[t] + 1;q.push(xx);}}//十位修改 for (int i = 0; i <= 9; i ++ ){
    int xx = t / 100 * 10 + shi[i];xx = xx * 10 + t % 10;if (flag[xx] == -1 && isprime(xx)){
    flag[xx] = flag[t] + 1;q.push(xx);}}//百位修改 for (int i = 0; i <= 9; i ++ ){
    int xx = t / 1000 * 10 + bai[i];xx = xx * 100 + t % 100;if (flag[xx] == -1 && isprime(xx)){
    flag[xx] = flag[t] + 1;q.push(xx);}}//千位修改 for (int i = 0; i <= 8; i ++ ){
    int xx = t / 10000 * 10 + qian[i];xx = xx * 1000 + t % 1000;if (flag[xx] == -1 && isprime(xx)){
    flag[xx] = flag[t] + 1;q.push(xx);}}}
}int main()
{
    int t; cin >> t;while (t -- ){
    cin >> n >> m;if (n == m){
    cout << 0 << endl;continue;}bfs();cout << flag[m] << endl;}return 0;
}