题目链接：Prime Path
题目大意
从一个四位素数m开始，每次只允许变动一位数字使其变成另一个四位素数。求最终把m变成n所需的最少次数。
思路
BFS。搜索的时候，最低位为0，2，4，6，8可以先排除（偶数不会是素数），最高位是0的也可以排除。这个题判断素数的次数比较少，可以不打素数表。
题解
第二次写的时候代码写的很乱。。没有第一遍干净了
#include <iostream>
#include <cstring>
#include <queue>
using namespace std; int num, m, n, ans;
int vis[];
int a[] = {,,,,,,,,,};
int digit[];
struct point
{
int val;
int step;
}p; void div(int x) //把数拆分
{
for(int i = ; i < ; i++)
{
digit[i] = x % ;
x = x/;
}
} bool isPrime(int n)
{
for(int i = ; i*i <= n; i++)
{
if(n % i == )
{
return false;
}
}
return true;
} int bfs(int m, int n)
{
queue<point> q;
p.val = m;
p.step = ;
q.push(p);
while(!q.empty())
{
point cur = q.front();
if(cur.val == n)
{
return cur.step;
}
//cout << cur.val << " ";
vis[cur.val] = ;
div(cur.val);
for(int i = ; i < ; i++)
{
if(i == digit[] || i == || i == || i == || i == ) continue;
int x = digit[]* + digit[]* + digit[]* + i;
if(vis[x] || !isPrime(x)) continue;
p.val = x;
p.step = cur.step+;
q.push(p);
}
for(int i = ; i < ; i++)
{
if(i == digit[]) continue;
int x = digit[]* + digit[]* + i* + digit[];
if(vis[x] || !isPrime(x)) continue;
p.val = x;
p.step = cur.step+;
q.push(p);
} for(int i = ; i < ; i++)
{
if(i == digit[]) continue;
int x = digit[]* + i* + digit[]* + digit[];
if(vis[x] || !isPrime(x)) continue;
p.val = x;
p.step = cur.step+;
q.push(p);
}
for(int i = ; i < ; i++)
{
if(i == digit[]) continue;
int x = i* + digit[]* + digit[]* + digit[];
if(vis[x]|| !isPrime(x)) continue;
p.val = x;
p.step = cur.step+;
q.push(p);
}
q.pop();
}
return -; //没有找到
} int main(int argc, char const *argv[])
{
#ifdef debug
freopen("test.txt","r",stdin);
#endif
cin >> num;
while(num--)
{
memset(vis, ,sizeof(vis));
cin >> m >> n;
ans = bfs(m, n);
if (ans == -)
{
cout << "Impossible" << endl;
continue;
}
cout << ans << endl;
}
}