本文主要是介绍POJ 3126 *** Prime Path，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意:给两个1000-9999内的素数A,B，每次改变A的一个位上的数字，得到后的数字必须为素数。问最少需要多少步才能得到B。
想法:对于A而言每次改变一个数字，那么用bfs遍历对A而言所有可能的状态同时判断是否为素数就可以了。
代码如下：
#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<cstring>
#include<sstream>
#include<set>
#include<string>
#include<iterator>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;int prime[10000];
int flag[10000];
int base[4] = { 1,10,100,1000 };int main(void) {//获得素数memset(prime, 1, sizeof(prime));for (int i = 2; i < 10000; ++i) {if (prime[i])for (int k = 2; k < 10010 / i; ++k)prime[i * k] = 0;}int n, ori, tar;cin >> n;while (n--) {cin >> ori >> tar;//如果ori==tar，直接输出结果if (ori == tar) {cout << 0 << endl;continue;}//如果ori!=tar，按以下方式处理memset(flag, 0, sizeof(flag));flag[ori] = 1;queue<int> path;path.push(ori);int now, temp, sign = 1;while (!path.empty()&&sign) {now = path.front();path.pop();int o[4];o[0] = now % 10, o[1] = now % 100 / 10;o[2] = now % 1000 / 100, o[3] = now / 1000;for (int i = 0; i < 4&&sign; ++i)for (int j = 0; j < 10&&sign; ++j) {temp = now - o[i] * base[i] + j*base[i];if (temp == tar) {flag[tar] = flag[now];sign = 0;break;}if (!flag[temp] && prime[temp] && temp>1000) {flag[temp] = flag[now] + 1;path.push(temp);}}}if (flag[tar])cout << flag[tar] << endl;else cout << "Impossible" << endl;}return 0;
}这篇关于POJ 3126 *** Prime Path的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
