【回炉重造】POJ-3126.Prime Path 题解_综合

【回炉重造】POJ-3126.Prime Path 题解

题目链接：POJ-3126.Prime Path

题目

在这里插入图片描述

题意

给你两个四位质数 a1，a2
把a1的其中一位变一个数，而且是变成另一个质数【所谓的“质数路”
每次操作只能变一位数
问你最少变几次能变成 a2

解题思路

广搜思路：

遍历四个位置，每个位置遍历10次替换数字
每次替换完以后判断新生成的数是不是质数
如果是质数就放入队列
如果是结果就返回路径长度

难点/坑【个人以为的：

打表：题目说最多100组数据，每次都要从2开始循环求质数很费时间，1000-9999的复杂度是9e3*1e2*1e2 ≈ 1e8 1e8 次操作已经 1s 了，所以肯定是不行的
所以需要先用普通求质数的方法，把2 ~ 100里的质数求出来，然后用2 ~ 100的质数求1000 ~ 10000里的质数
求n是否是质数，只需要用2到根号n除n就行了，小于根号n的整数已经足够判断n是否是质数了
总而言之这样就可以把1e3 ~ 1e4里面的质数都快速的找出来了，方便之后判断使用
标记：每一个走过的数，都要标记起来，因为变了第二位，再变第一位可能还会再变第二位，为了避免重复走数，所以要标记走过的数，否则时间超限
位置标记：这个很缩短时间，就是如果上一次变换是把 1033 变成了 1733 ，那么在变换1733的时候就不需要百位数上的十次循环
我之前没有加这个标记，一直超时

代码【注释很详细，请结合代码搞解题思路~

//
// _ _ ___ ____ ___ ____ _____
//| | | | / _ \ _ __ / ___/ _ \| _ \| ____|
//| |_| | | | | | '_ \ | | | | | | | | | _|
//| _ | | |_| | | | | | |__| |_| | |_| | |___
//|_| |_|___\___/|_| |_| \____\___/|____/|_____|
// |_____|
//#include <iostream>
using namespace std;
typedef int hip;
#include <set>
#include <queue>
const int maxn = int(1e4 + 9);
#include <string>
// 使用set集合容器来打表质数表
set<hip> pf;
// 记录走过的数
set<string> f;
// 为了方便更新我把数存成字符串了// 质数打表
void P() {
    // 首先存储前2~100里面的质数pf.clear();pf.insert(2);pf.insert(3);for (hip i=5;i<100;i++) {
    hip j;for (j=2; j*j<i; j++) if (i%j == 0) break;if (j*j>=i) pf.insert(i);}// 然后利用2~100的质数来得出1e3~1e4里面的质数for (hip i=1001;i<10000;i++) {
    set<hip>::iterator j;for (j=pf.begin(); j!=pf.end(); j++) if (i%(*j) == 0) break;if (j==pf.end()) pf.insert(i);}
}
// 这个函数返回一个字符串四位数的整数值【能看懂的同学应该都能看懂吧L
hip STI(string n) {
    return (n[0]-'0')*1000+(n[1]-'0')*100+(n[2]-'0')*10+(n[3]-'0');}
// 广搜
hip bfs(string s, string e) {
    // 如果两个一样就直接返回 0if (s == e) return 0;// p 是路径长度的队列// l 是记录上一次变换的位数的队列queue<hip> p, l;// q 是记录上一个符合条件的质数的队列queue<string> q;q.push(s);p.push(0);// 判断条件是 i==last 跳过，而i的值是0，1，2，3所以在此之外的数都可以做最初的数，这里用了4l.push(4);// 每一轮新的找路清空一下记录走过的数的容器并把最初的数加入集合f.clear(); f.insert(s);// 广搜的正常起手操作while (!q.empty()) {
    // 取出上个数t，上个路长pp，上个修改的位数laststring t = q.front();hip pp = p.front(), last = l.front();q.pop(); p.pop(); l.pop();// 遍历四位for (hip i=0;i<4;i++) {
    // 如果上一次修改的是这个位置，就跳过if (i == last) continue;// 遍历 0~9 十个数for (hip j=0;j<10;j++) {
    // 如果是最高位，不能是0if (i==0&&j==0) continue;// 修改一位数的值string tt = t;tt[i] = '0'+j;// 如果这个数已经走过，或者不是质数，都需要跳过if (f.find(tt) != f.end() || pf.find(STI(tt)) == pf.end()) continue;// 如果遇到重点就返回路径长度if (tt == e) return pp+1;// 如果这个数可以当作路径，就标记之后把相关数据加入队列f.insert(tt);q.push(tt);p.push(pp+1);l.push(i);}}}// 这个-1没意义，按题意来说是必定有出路的，总归写一下函数流程比较完整return -1;
}int main() {
    ios::sync_with_stdio(0); cin.tie(0);// 打表P();// 输入样例个数hip t; cin >> t;while (t--) {
    // 输入两个数，输出路径长度string a1, a2; cin >> a1 >> a2;cout << bfs(a1, a2) << endl;}return 0;
}