Voldemort's blog

Voldemort's blog

我好菜啊

题解 SP1841 【PPATH - Prime Path】

posted on 2020-09-26 11:37:52 | under 题解 |

Description

有 $t$ 组询问,每次询问都给定两个四位素数 $n$, $m$。每次能改变 $n$ 中的一个数字,且每次改变后的 $n$ 也必须是素数。(首位不能改成0)
求最少经过多少次改变能使 $n$ 变成 $m$,如果无法变成则输出Impossible

Solution

这道题目明显考虑到了搜索,这道题目 dfsbfs 应该都可做,但是能用 bfs 就用 bfs,故本蒟蒻就用了 bfs

1. 队列内含元素的定义:

明显这道题我们需要两个元素,一个计算从 $n$ 变到当前数字所需的步数 $step$ ,还有一个就是我们现在的数字 $num$。所以队列就定义完了。

struct node {
    int step,num;
    node() {}
    node(int _num,int _step) {
        step = _step; num = _num;
    }
};

queue<node> q;

2. 修改&转移:

最简单的方法就是枚举你的修改位和你这一位要修改的数字,不妨设为 $i$ 和 $j$。 首先你得把这个数字拆开成数组的形式(你不拆应该也可以做,但我没试过),进行修改后再把新数算出来。如果这个新数符合条件且没有出现过就把它放入队列。代码如下:

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. 筛素数

没有人不会吧……

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

实在写不出来再看,其实大部分都在前面实现过了。

#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();
    }
}

最后向大家推荐一道双倍经验,大家可以爆切此题后去写一下那道题。