版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Dextrad_ihacker/article/details/50963974
虽然自己会写总结，但是这篇还是附链接吧，嘻嘻。
/*************************************************************************
> File Name: poj_3126.cpp
> Author:
> Mail:
> Created Time:
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define LL long long
using namespace std;
const int N = 10000;
int n;
bool prim[10009];
int ans = 0;
bool check(int k)
{
if(k == 0 || k == 1) return 0;
if(k == 3 || k == 2) return 1;
for(int i = 2; i*i <= k; i++)
{
if(k % i == 0) return 0;
}
return 1;
}
void init()
{
for(int i = 1000; i < N; i++)
{
if(check(i)) prim[i] = 1;
else prim[i] = 0;
}
}
int bfs(int first, int last)
{
queue<int > q;
bool v[N];
int t[5];
int dis[N];
memset(dis, 0, sizeof(dis));
memset(t, 0, sizeof(t));
memset(v, 0, sizeof(v));
v[first] = 1;
q.push(first);
while(!q.empty())
{
int x = q.front();
if(x == last) return dis[x];
q.pop();
t[0] = x / 1000;
t[1] = x % 1000 / 100;
t[2] = x % 100 / 10;
t[3] = x % 10;
for(int i = 0; i <= 3; i++)
{
int k = t[i];
for(int j = 0; j <= 9; j++)
{
if(j != t[i])
{
t[i] = j;
int a = 1000*t[0]+100*t[1]+10*t[2]+t[3];
if(!v[a] && prim[a])
{
q.push(a);
dis[a] = dis[x]+1;
v[a] = 1;
}
if(a == last) return dis[a];
}
}
t[i] = k;
}
}
return -1;
}
int main()
{
init();
scanf("%d", &n);
int a, b;
for(int i = 0; i < n; i++)
{
scanf("%d%d", &a, &b);
int ans = bfs(a, b);
if(ans != -1) printf("%d\n", ans);
else printf("Impossible\n");
}
return 0;
}
1.博主的伪代码的的确确是它的代码的核心思想，这点启示我要整理思路完毕以后，可以用伪代码先行表示。
2.bool 布尔型的用法
bool型定义后只会有0和1两个数据，通常用int型判断真假时，非0为真，0为假，而用bool定义下的数组就很方便
3.先行打表的重要性
先行对素数打表，可以很方便的作为判断这个数是否是素数的条件
4.自定义函数init
自定义的init函数是对1000到10000之间的数进行判断是否是素数并且储存成0和1的函数。
5.循环的套用
伪代码中的巧妙循环。
6.步数的叠加
步数的叠加，每次进行的读进素数都会一次变成叠加数，例从1003搜索时，到d[1733]=d[1033]+1=0+1=1 然后就变成从1733搜索，到d[3733]=d[1733]+1=1+1=2
7.“怎样确定是否这个数据出现过”的巧妙思想
通过定义数组，进行0和1的赋值，然后作为if条件，进行判断。
8.memset的用法
https://blog.csdn.net/qq_38993096/article/details/87887192
摘抄部分：void *memset(void *s,int c,size_t n)
总的作用：将已开辟内存空间 s 的首 n 个字节的值设为值 c。
例如：
1.memset(dis,255,sizeof(dis));
将前sizeof（dis）字节的空间赋值为-1（255的补码是-1，计算机用补码表示数字）
2.memset(dis,0,sizeof(dis));
将前sizeof（dis）字节的空间赋值为0
3.memset(dis,-1,sizeof(dis));
将前sizeof（dis）字节的空间赋值为-1
4.memset(dis,127,sizeof(dis));
将前sizeof（dis）字节的空间赋值为2139062143
综上，要慎用memset，一般只用来清零或置为-1（-2都不行，负数除了-1都不行）
9.判断代价的条件
代价只可能是>=0，当上述循环正常运行时，则产生正确答案；当不正确运行时，return -1，即ans=-1，所以判断条件为！=-1，否则即使impossible。
原文：https://www.cnblogs.com/h-y-h/p/11914573.html