题意：从一个四位素数变到另一个四位素数，每次只能改到一个位的数字，且改动后仍是一个四位素数，问最少需要几步。
题目链接：http://poj.org/problem?id=3126
——>>直接广搜。
#include <cstdio>
#include <cstring>
#include <queue>using namespace std;const int maxn = 9999 + 10;
int MAP[maxn], a, b, p[maxn], cnt;
bool vis[maxn];int translate(int x, int i, int j) //把x的第i位变为j
{int k, buf[4], ret = 0;for(k = 0; k < 4; k++){buf[k] = x % 10;x /= 10;}buf[i] = j;for(k = 3; k >= 0; k--) ret = ret * 10 + buf[k];return ret;
}bool bs(int* A, int x, int y, int v) //二分搜索
{int m;while(x < y){m = x + (y - x) / 2;if(A[m] == v) return 1;else if(A[m] > v) y = m;else x = m + 1;}return 0;
}void get_prime() //快速筛素数
{memset(vis, 0, sizeof(vis));cnt = 0;for(int i = 2; i <= 9999; i++) if(!vis[i]){p[cnt++] = i;for(int j = i; j <= 9999; j = j + i) vis[j] = 1;}
}void bfs()
{if(a == b) return;int temp, i, j;queue<int> qu;qu.push(a);while(!qu.empty()){temp = qu.front();qu.pop();for(i = 0; i < 4; i++)for(j = 0; j < 10; j++){if(j == 0 && (i == 0 || i == 3)) continue;int tmp = translate(temp, i, j);if(tmp % 2 == 0 || MAP[tmp] != -1) continue;if(bs(p, 168, cnt, tmp)){MAP[tmp] = MAP[temp] + 1;if(tmp == b) return;qu.push(tmp);}}}
}int main()
{int T;get_prime();scanf("%d", &T);while(T--){scanf("%d%d", &a, &b);memset(MAP, -1, sizeof(MAP));MAP[a] = 0;bfs();printf("%d\n", MAP[b]);}return 0;
}