本文主要是介绍poj3126 - Prime Path（BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=3126
题意：给定两个素数n和m，要求把n变成m，每次变换时只能变一个数字，即变换后的数与变换前的数只有一个数字不同，并且要保证变换后的四位数也是素数。求最小的变换次数；如果不能完成变换，输出Impossible。
思路：广搜枚举每一位数字加入队列（个位1-9的奇数，十位，百位0-9,的数字，千位1-9的数字），能得到答案就一定是最少的次数，否则就输出Impossible。
AC代码：
#include <iostream>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn = 1e5+7;
int vis[maxn], n, m, t;
struct node
{int x, step;
}now, tmp, nex;
int is_prime(int x)
{for(int i = 2; i <= sqrt(x); i++)if(x % i == 0) return 0;return 1;
}
queue <node> Q;
void bfs()
{while(!Q.empty()){tmp = Q.front();int x = tmp.x; Q.pop();if(x == m) {printf("%d\n",tmp.step); return; }for(int i = 1; i < 10; i += 2){int y = x / 10 * 10 + i;if(x != y && !vis[y] && is_prime(y)){nex.x = y; nex.step = tmp.step + 1;Q.push(nex); vis[y] = 1;}}for(int i = 0; i < 10; i++){int y = x / 100 * 100 + i * 10 + x % 10;if(x != y &&!vis[y] && is_prime(y)){nex.x = y; nex.step = tmp.step + 1;Q.push(nex); vis[y] = 1;}}for(int i = 0; i < 10; i++){int y = x / 1000 * 1000 + i * 100 + x % 100;if(x != y &&!vis[y] && is_prime(y)){nex.x = y; nex.step = tmp.step + 1;Q.push(nex); vis[y] = 1;}}for(int i = 1; i < 10; i++){int y = i * 1000 + x % 1000;if(x != y &&!vis[y] && is_prime(y)){nex.x = y; nex.step = tmp.step + 1;Q.push(nex); vis[y] = 1;}}}puts("Impossible");return;
}
int main()
{scanf("%d",&t);while(t--){while(!Q.empty()) Q.pop();memset(vis, 0, sizeof(vis));scanf("%d%d",&n,&m); vis[n] = 1;now.x = n, now.step = 0;Q.push(now); bfs();}
}
这篇关于poj3126 - Prime Path（BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
