专栏首页用户6093955的专栏Prime Path(POJ - 3126)【BFS+筛素数】

Prime Path(POJ - 3126)【BFS+筛素数】

Prime Path(POJ - 3126)

题目链接

算法

BFS+筛素数打表

1.题目主要就是给定你两个四位数的质数a,b,让你计算从a变到b共最小需要多少步。要求每次只能变1位,并且变1位后仍然为质数。

2.四位数的范围是1000~9999,之间共有1000多个质数。由于已经知道位数为4位,所以可以通过BFS来寻找最小步数。每次需要分别变换个位、十位、百位、千位,并且把符合要求的数放到队列中,同时需标记这个数已经遍历过一次,避免重复遍历,直到找到目标数。

C++代码

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e4;
int primes[N], cnt;
bool st[N];
bool vis[N];
int t, a, b;
struct Number{
    int data;
    int steps;
};
void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j]*i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
void bfs()
{
    queue<Number> que;
    que.push({a, 0});
    vis[a] = true;
    while(que.size())
    {
        Number cur = que.front();
        que.pop();
        if(cur.data == b)
        {
            cout << cur.steps << endl;
            return ;
        }
        Number tmp;
        /*遍历可能的个位*/
        for(int i = 0; i <= 9; i++)
        {
            tmp.data = cur.data / 10 * 10 + i;
            if(vis[tmp.data] || st[tmp.data]) continue;
            tmp.steps = cur.steps + 1;
            que.push(tmp);
            vis[tmp.data] = true;
        }
        /*遍历可能的十位*/
        for(int i = 0; i <= 9; i++)
        {
            tmp.data = cur.data / 100 * 100 + i * 10 + cur.data % 10;
            if(vis[tmp.data] || st[tmp.data]) continue;
            tmp.steps = cur.steps + 1;
            que.push(tmp);
            vis[tmp.data] = true;
        }
        /*遍历可能的百位*/
        for(int i = 0; i <= 9; i++)
        {
            tmp.data = cur.data % 100 + i * 100 + cur.data / 1000 * 1000;
            if(vis[tmp.data] || st[tmp.data]) continue;
            tmp.steps = cur.steps + 1;
            que.push(tmp);
            vis[tmp.data] = true;
        }
        /*遍历可能的千位*/
        for(int i = 1; i <= 9; i++)
        {
            tmp.data = cur.data % 1000 + i * 1000;
            if(vis[tmp.data] || st[tmp.data]) continue;
            tmp.steps = cur.steps + 1;
            que.push(tmp);
            vis[tmp.data] = true;
        }
    }

}
int main()
{
    get_primes(9999);
    cin >> t;
    while(t--)
    {
        memset(vis, 0, sizeof vis);
        cin >> a >> b;
        bfs();
    }
}

代码中使用的线性筛素数模板来源

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 汉诺塔问题

    _DIY
  • Sequential Nim(CodeForces - 1382B)【博弈】

    1.这道题乍一看以为用Nim博弈直接套用就可以了,结果通过题意发现并不是。题目中要求取石子时只能从下标最小的那一堆开始取,也就是说一堆一堆的取,不能跳着取。

    _DIY
  • POJ-2299 Ultra-QuickSort(用树状数组求逆序对数)

    _DIY
  • 【学习】Spss 聚类分析案例—某移动公司客户细分模型

    聚类分析在各行各业应用十分常见,而顾客细分是其最常见的分析需求,顾客细分总是和聚类分析挂在一起。 顾客细分,关键问题是找出顾客的特征,一般可从顾客自然特征和消费...

    小莹莹
  • C++常见面试题

    1. 声明一个 circle 类,有数据成员 Radius(半径,float型),成员函数 GetArea() 计算圆的面积,在main 函数中声明一个cirl...

    越陌度阡
  • 远控免杀专题(5)-Veil免杀(VT免杀率23/71)

    1、远控免杀专题(1)-基础篇:https://mp.weixin.qq.com/s/3LZ_cj2gDC1bQATxqBfweg

    徐焱
  • seo常用工具汇总

    https://tongji.baidu.com/web/welcome/login

    ianzhi
  • 绕过 CSP 从而产生 UXSS 漏洞

    当通过 tarnish 扫描大量 Chrome 扩展程序时,我发现了两款流行的 Chrome 扩展程序 Video Downloader for Chrome ...

    信安之路
  • 记一次出乎意料的semaphore超时导致crash分析过程(转)

    DBA应该对InnoDB: Semaphore wait has lasted > 600 seconds. We intentionally crash th...

    [3306 Pai ] 社区
  • 基于 kubernetes 构建 Docker 集群管理详解

    Kubernetes 是Google开源的容器集群管理系统,基于Docker构建一个容器的调度服务,提供资源调度、均衡容灾、服务注册、动态扩缩容等功能套件,目前...

    刘天斯

扫码关注云+社区

领取腾讯云代金券