题目链接：POJ 3126
Description
首相们对安全局长带来的消息感到非常不安，他们说他们将为了安全考虑改变首相房间门牌号上面的门牌号码。
——要不时地改变门牌号，这样可以使敌人处于迷惑之中。
——但是，我现在的门牌号是1033号，它是一个质数，我有质数强迫症。我不能忍受我的门牌号不是质数。
——我知道，所以你的新门牌号8179号也是一个质数。你只需在你办公室的门上更换掉原来的四个数字就可以。
——不，不是那么简单。假设我把第一个数字先改为8，那么在你更改下一个数字之前他将是8033，它不是素数！
——我明白了，首相，即使在几秒钟内，你也不能忍受一个非质数。
——是的！因此，你必须提出一种从1033改为8179而且中间全是质数的方案，每次只可以改变其中一个数位上的数字。
例如：
1033
1733
3733
3739
3779
8779
8179
此时，我们一共更改了6次数字，已知更改一次数字需要花费1英镑，因此我们需要花费6英镑。
你的任务就是写一个程序，对于任意的起始和终止数字，都求出最小花费。
Input
输入数据有多组，首先是一个数字n，代表之后有n组数据。
其次，在每一组输入中，都包含两个数字m和n，m代表原来的门牌号，n代表现在的门牌号。
其中，m和n都是四位数，而且不含前导0。
Output
每组输入输出一行，输出在此情况下的最小花费。若不存在从m到n的路径，则输出单词“Impossible”。
Sample Input
3
1033 8179
1373 8017
1033 1033
Sample Output
6
7
0
题意
两个4位素数，并且千位不可能是0，每次只能改变一个位上的数，并且改完之后还是素数，用这样的素数转换，问最少要几次转换得到目标素数，如果不能得到输出不能。
题解：
BFS，先打一个表把1000到10000的素数打出来，然后从起点开始改变每个位上的数，如果是素数，就入队记录这个数用了几步素数转换得来，直至把能达到的所有素数需要的最好步数得出或得出答案。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 5;
set<int>Prime;
set<int>state;
void Init() {
int flag;
for (int i(1000); i < 10000; i++) {
flag = 0;
for (int j(2); j <= int(sqrt(i*1.0)); j++)
if (i%j == 0) {
flag = 1;
break;
}
if (!flag)
Prime.insert(i);
}
}
int ans;
int f(string a) {
return (a[0] - '0') * 1000 + (a[1] - '0') * 100 + (a[2] - '0') * 10 + (a[3] - '0');
}
map<string, int>dis;
int bfs(string a, string b) {
queue<string>P;
P.push(a);
state.insert(f(a));
string temp;
while (!P.empty()) {
temp = P.front();
P.pop();
if (temp == b)
return dis[temp];
int ans = 1;
for (int i(0); i < 4; i++) {
string next = temp;
for (int j(0); j < 10; j++) {
if (i == 0 && j == 0)continue;
next[i] = j + '0';
if (state.find(f(next)) != state.end())continue;
if (Prime.find(f(next)) != Prime.end()) {
P.push(next);
dis[next] = dis[temp] + 1;
state.insert(f(next));
}
}
}
}
return -1;
}
int main() {
Init();
int T;
cin >> T;
string a, b;
for (int i(0); i < T; i++) {
state.clear();
dis.clear();
ans = 1000000;
cin >> a >> b;
cout << bfs(a, b) << endl;
}
return 0;
}