思路
由于最多有100组样例,所以直接先初始化判断出1000-9999之间的数字是否是素数。然后再对每个题目所给的四位数进行BFS搜索,依次对每个数位进行枚举,使用0-9的每一个数字对每一个数位进行替换,注意千位上的数字不能为0。然后检验当前数字是否为素数和是否在当前这组样例中使用过,使用过或者不是素数则continue,否则加入队列中继续循环,直到找出和y一样的数字为止。由于当前代码判断的都是修改后的数字是否等于y,所以需要特判x=y的情况。
代码
#include <iostream>
#include<algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int x, y;
// 初始化判断是否是素数,记录是否被使用
bool isprime[N], vis[N];
void init() {
for (int i = 1000; i <= 9999; i++) {
isprime[i] = true;
for (int j = 2; j <= i / j; j++) {
if (i % j == 0) {
isprime[i] = false;
break;
}
}
}
}
void bfs(int x) {
queue<pair<int, int> > q;
q.push({x, 0});
vis[x] = true;
while (!q.empty()) {
pair<int, int> xx = q.front();
q.pop();
int mod = 1;
for (int i = 1; i <= 4; i++) {
mod *= 10;
// 计算出余数,依次枚举当前位的可以取的值
int record = xx.first % mod;
for (int j = 0; j <= 9; j++) {
if (i == 4 && j == 0)
continue;
int dx = xx.first - record + j * mod / 10 + record % (mod / 10);
if (isprime[dx] == true && vis[dx] == false) {
if (dx == y) {
cout << xx.second + 1 << endl;
return;
}
vis[dx] = true;
q.push({dx, xx.second + 1});
}
}
}
}
return;
}
int main() {
init();
int t;
cin >> t;
while (t--) {
memset(vis, 0, sizeof vis);
cin >> x >> y;
if (x == y)
cout << 0 << endl;
else
bfs(x);
}
return 0;
}
标签:Prime,数字,int,3126,vis,素数,POJ,include
From: https://www.cnblogs.com/againss/p/18292163