题解 SP1841 【PPATH - Prime Path】
TRZ_2007
2020-09-26 11:37:52
# Description
有 $t$ 组询问，每次询问都给定两个**四位素数** $n$，$m$。每次能改变 $n$ 中的一个数字，且每次改变后的 $n$ 也必须是素数。**(首位不能改成0)**。
求最少经过多少次改变能使 $n$ 变成 $m$，如果无法变成则输出``Impossible``。
# Solution
这道题目明显考虑到了搜索，这道题目 ``dfs`` 和 ``bfs`` 应该都可做，但是能用 ``bfs`` 就用 ``bfs``，故本蒟蒻就用了 ``bfs``。
## 1. 队列内含元素的定义：
明显这道题我们需要两个元素，一个计算从 $n$ 变到当前数字所需的步数 $step$ ，还有一个就是我们现在的数字 $num$。所以队列就定义完了。
```cpp11
struct node {
int step,num;
node() {}
node(int _num,int _step) {
step = _step; num = _num;
}
};
queue<node> q;
```
## 2. 修改&转移：
最简单的方法就是枚举你的修改位和你这一位要修改的数字，不妨设为 $i$ 和 $j$。 首先你得把这个数字拆开成数组的形式（你不拆应该也可以做，但我没试过），进行修改后再把新数算出来。如果这个新数符合条件且没有出现过就把它放入队列。代码如下：
```cpp11
while(!q.empty()) {
node u = q.front(); q.pop();
turndata(u.num); //把之前的数拆成数组的形式
for(int i = 1;i <= 4;i++) { //枚举修改位
for(int j = 0;j <= 9;j++) { //枚举要修改的数字
if(j == 0 && i == 1) continue; //注意第一位不能改成0
int k = s[i]; //由于这个数我们要多次使用，所以先存起来
s[i] = j; //修改
int nw = combine(); //合并成新数
if(!prime[nw] && !book[nw]) { //是素数且没有出现过
book[nw] = 1;
q.push(node(nw,u.step + 1)); //加入队列
}
// printf("%d %d\n",nw,u.step + 1);
if(nw == b) { //如果达到目标状态
printf("%d\n",u.step + 1); //输出结果
return 0;
}
s[i] = k; //回溯
}
}
}
```
## 3. 筛素数
~~没有人不会吧~~……
```cpp11
void getprime() {
prime[1] = 1;
for(int i = 2;i < N;i++) {
if(!prime[i]) {
for(int j = i * 2;j < N;j += i) prime[j] = 1;
}
}
}
```
# Code
实在写不出来再看，其实大部分都在前面实现过了。
```cpp11
#include <bits/stdc++.h>
using namespace std;
const int N = 10009;
struct node {
int step,num;
node() {}
node(int _num,int _step) {
step = _step; num = _num;
}
};
int a,b,q;
int book[N],s[N];
int prime[N];
void getprime() {
prime[1] = 1;
for(int i = 2;i < N;i++) {
if(!prime[i]) {
for(int j = i * 2;j < N;j += i) prime[j] = 1;
}
}
}
void turndata(int x) {
s[1] = x / 1000 % 10;
s[2] = x / 100 % 10;
s[3] = x / 10 % 10;
s[4] = x % 10;
}
int combine() {
return s[1] * 1000 + s[2] * 100 + s[3] * 10 + s[4];
}
void _file() {
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
}
void solve() {
// _file();
queue<node> q;
memset(book,0,sizeof(book));
scanf("%d %d",&a,&b);
if(a == b) {
puts("0");
return;
}
book[a] = 1; q.push(node(a,0));
while(!q.empty()) {
node u = q.front(); q.pop();
turndata(u.num);
for(int i = 1;i <= 4;i++) {
for(int j = 0;j <= 9;j++) {
if(j == 0 && i == 1) continue;
int k = s[i];
s[i] = j;
int nw = combine();
if(!prime[nw] && !book[nw]) {
book[nw] = 1;
q.push(node(nw,u.step + 1));
}
// printf("%d %d\n",nw,u.step + 1);
if(nw == b) {
printf("%d\n",u.step + 1);
return;
}
s[i] = k;
}
}
}
puts("Impossible");
}
int main() {
getprime();
scanf("%d",&q);
while(q--) {
solve();
}
}
```
最后向大家推荐一道[双倍经验](https://www.luogu.com.cn/problem/UVA12101)，大家可以爆切此题后去写一下那道题。