poj 3126 Prime Path (广搜)

http://poj.org/problem?id=3126

题意:从一个素数,挨个数位的变换,在此过程中保证每次变换的数位都是素数,最后变到所给的另一个素数最少步多少

分析:广搜,依次换一位数字,判断该数字是否是素数,若是进队列,其中需要注意的是,换千位数字的时候可能会出现

        0的情况,导致所给数字不是4位数

#include<stdio.h>
#include<queue>
#include<string.h>
#include<math.h>
using namespace std;
const int MAXN=20000;
int vis_prime[MAXN];
int vis[MAXN];
int step[MAXN];

void init()
{
    memset(vis_prime,0,sizeof(vis_prime));
    for(int i=2; i<=(int)sqrt(1.0*MAXN); i++)
    {
        if(vis_prime[i]==0)
          {
            for(int j=i*2; j<MAXN; j+=i)
            {
                vis_prime[j]=1;
            }
          }
    }
    //for(int i=1000;i<MAXN/2;i++) if(vis_prime[i]==0) printf("%d ",i);


}

int BFS(int a,int b)
{
    int head,next,i,j;
    memset(vis,0,sizeof(vis));
    queue<int>Q;
    Q.push(a);
    vis[a]=1;
    step[a]=0;
    while(!Q.empty())
    {
        head=Q.front();
        Q.pop();
        for(i=0;i<4;i++)
        {
            for(j=0;j<=9;j++)
            {
                if(i==0) next=head/10*10+j;
                if(i==1) next=head/100*100+j*10+head%10;
                if(i==2) next=head/1000*1000+head%100+j*100;
                if(i==3) next=j*1000+head%1000;
                if(next==b) return step[head]+1;
                if(!vis_prime[next] && !vis[next] && next>=1000)//这里要保证是4位数字
                {//有可能17是素数,这样很可能就减少了步数到b,而4位数字的话,可能步数就得多一点了
                    vis[next]=1;
                    Q.push(next);
                    step[next]=step[head]+1;
                }
            }
        }
    }
    return 0;
}

int main()
{
    int T,a,b;
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&a,&b);
        if(a==b) printf("0\n");
        else
        {
            int ans=BFS(a,b);
            if(ans==0) printf("Impossible\n");
            else printf("%d\n",ans);
        }
    }
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏聊聊技术

原 初学算法 - 求凸包的Garham's

47110
来自专栏Bingo的深度学习杂货店

Q172 Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!. Note: Your solut...

3265
来自专栏数据结构与算法

cf567E. President and Roads(最短路计数)

首先确定哪些边一定在最短路上,一个条件是 从起点到该点的最短路 + 边权 + 从该点到终点的最短路 = 从起点到终点的最短路

1122
来自专栏数据结构与算法

洛谷P3704 [SDOI2017]数字表格

题目描述 Doris刚刚学习了fibonacci数列。用f[i]f[i] 表示数列的第ii 项,那么 f[0]=0f[0]=0 ,f[1]=1f[1]=1 , ...

3419
来自专栏数据结构与算法

2018.7.21NOIP模拟赛?解题报告

那么我们还需要对每个已经加入的右括号维护一个小根堆。每次判断是否替换掉更小的会更优

825
来自专栏数据结构与算法

cf1028C. Rectangles(前缀和)

呵呵哒,昨天cf半夜场,一道全场切的题,我没做出来。。不想找什么理由,不会做就是不会做。。

743
来自专栏数据结构与算法

1893. [国家集训队2011]等差子序列(bitset)

★★   输入文件:nt2011_sequence.in   输出文件:nt2011_sequence.out 简单对比 时间限制:0.3 s   内存限制:5...

35210
来自专栏数据处理

人大代表数据分析爬取代表数据正则表达式提取需要的数据还可以把上面数据画成饼图民族词云图统计代表姓氏人数姓氏词云

3363
来自专栏小樱的经验随笔

Humble Numbers(丑数) 超详解!

给定一个素数集合 S = { p[1],p[2],...,p[k] },大于 1 且素因子都属于 S 的数我们成为丑数(Humble Numbers or Ug...

3038
来自专栏软件开发 -- 分享 互助 成长

C++中巧妙的位运算

位运算要多想到与预算和异或运算,并常常将两个数对应位上相同和不同分开处理 一、x&(x-1)消除x二进制中最右边的一个1。 这个比较厉害,比如统计某个 二、与和...

3096

扫码关注云+社区

领取腾讯云代金券