题意：
从一个素数变到另一个素数，要求每次只能动一位上的数字，并且要求中间值也必须是素数
要点：
简单的BFS水题，只要将每个节点的变动方向写清楚就行了。
| 15306522 | Accepted | 272K | 16MS | 1625B | 2016-03-24 09:38:53 |
#include#include #include #include using namespace std;int prim[10000],vis[10000];struct node{ int x; int num;};void prim_number()//打一个素数表{ for (int i = 1000; i < 10000; i++) { prim[i] = 1; for (int j = 2; j*j <= i; j++) { if (i%j == 0) { prim[i] = 0; break; } } }}void bfs(int x,int y){ int i,val,yy; queue que; node u,v; u.x = x; u.num = 0; vis[x] = 1; que.push(u); while (!que.empty()) { u = que.front(); que.pop(); int xx = u.x; if (xx == y) { printf("%d\n", u.num); return; } for (i = 1; i <= 9; i++)//千位 { val = xx % 1000; yy = i * 1000 + val; v.x = yy; v.num = u.num + 1; if (!vis[yy] && yy != xx&&prim[yy]) { vis[yy] = 1; que.push(v); } } for (i = 0; i <= 9; i++)//百位 { int qian = xx / 1000; val = xx % 100; yy = qian * 1000 + i * 100 + val; v.x = yy; v.num = u.num + 1; if (!vis[yy] && yy != xx&&prim[yy]) { vis[yy] = 1; que.push(v); } } for (i = 0; i <= 9; i++)//十位 { val = xx / 100; int ge = xx % 10; yy = val * 100 + i * 10 + ge; v.x = yy; v.num = u.num + 1; if (!vis[yy] && yy != xx&&prim[yy]) { vis[yy] = 1; que.push(v); } } for (i = 1; i <= 9; i += 2)//个位，不能为偶数 { val = xx / 10; yy = val * 10 + i; v.x = yy; v.num = u.num + 1; if (!vis[yy] && yy != xx&&prim[yy]) { vis[yy] = 1; que.push(v); } } } printf("Impossible\n");}int main(){ int t,x,y; scanf("%d", &t); prim_number(); while (t--) { memset(vis, 0, sizeof(vis)); scanf("%d%d", &x, &y); bfs(x, y); } return 0;}