文档章节

POJ -- 3126 Prime Path

傅芃芃
 傅芃芃
发布于 2016/03/11 19:36
字数 442
阅读 19
收藏 0

题目网址: POJ -- 3126

给出变化规律,问最少变化几次。使用宽搜就可以解决,每个数的出度是40。

这道题目还用到了简单的素数判定,四位数不大,判断一个四位数是否是素数只要O(100)的复杂度就够了(最大数不超过10000)。

一个小技巧是将每次变化出来的新数都做上标记,如果是素数就进队,不是素数下次遇到也不用再花时间去判定了。

#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
using namespace std;
queue<int> q;
const int maxn = 10010;
int dis[maxn];
int vis[maxn];
bool judge(int n)
{
    for(int i = 2; i*i <= n; i++)
    {
        if(!(n % i)) return false;
    }
    return true;
}
int main()
{
    int a, b;
    int T;
    cin >> T;
    while(T--)
    {
        memset(vis, 0, sizeof(vis));
        memset(dis, -1, sizeof(dis));
        while(!q.empty()) q.pop();

        scanf("%d%d", &a, &b);
        q.push(a);
        dis[a] = 0;
        vis[a] = 1;
        while(!q.empty())
        {
            int x = q.front(); q.pop();
            if(x == b)
            {
                printf("%d\n", dis[x]);
                break;
            }
            int X[5], x_ = x;
            X[1] = x_ % 10; x_ /= 10;
            X[2] = x_ % 10; x_ /= 10;
            X[3] = x_ % 10; x_ /= 10;
            X[4] = x_ % 10; x_ /= 10;
            for(int i = 1; i <= 4; i++)
            {
                for(int k = 0; k <= 9; k++)
                {
                    int y = 0;
                    if(i != 1) y += X[1];
                    else y += k;
                    if(i != 2) y += X[2] * 10;
                    else y += k * 10;
                    if(i != 3) y += X[3] *100;
                    else y += k * 100;
                    if(i != 4) y += X[4] *1000;
                    else y += k * 1000;
                    if(y >= 1000 && !vis[y])
                    {
                        vis[y] = 1;
                        if(judge(y))
                        {
                            q.push(y);
                            dis[y] = dis[x] + 1;
                        }
                    }
                }
            }
        }
    }
    return 0;
}

把四位数剥离出来再重组的过程是挺恶心的。。。

© 著作权归作者所有

傅芃芃
粉丝 14
博文 21
码字总数 19341
作品 0
私信 提问
POJ 3126 Prime Path 【bfs】

传送门 题意: 给定两个四位数的素数, 然后每次可以将第一个素数的某一位数字变成其他数字, 但是要保证变化后的那个数依旧是素数, 问最少需要多少步可以变成第二素数. 很明显的bfs, 先预处理下...

Anxdada
2018/02/25
0
0
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
156
1
[Data Structures and Algorithms - 1] Introduction & Mathematics

References: 1. Stanford University CS97SI by Jaehyun Park 2. Introduction to Algorithms 3. Kuangbin's ACM Template 4. Data Structures by Dayou Liu 5. Euler's Totient Function Ge......

rgvb178
2018/01/26
0
0
Chef 12.3.0 发布,面向云计算开源系统整合框架

Chef 12.3.0 发布,此版本主要有以下更新: pr#3160: Use Chef Zero in socketless mode for local mode, add --no-listen flag to disable port binding Nolan Davidson: Removed after_cre......

oschina
2015/05/05
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

社区投稿 | 线程简介和 MySQL 调试环境搭建

作者:高鹏 文章末尾有他著作的《深入理解MySQL主从原理 32讲》,深入透彻理解MySQL主从,GTID相关技术知识。 本文节选自《深入理解MySQL主从原理》第29节 注意:本文分为正文和附件两部分,...

爱可生
13分钟前
4
0
DDOS攻击可以分为什么类型?怎么样才能解决?

DDoS 是一种多源网络攻击,其目的是针对终端用户扰乱其网络的资源或服务。其不断进化的复杂性能够造成各种各样的伤害,例如欺诈以及勒索等。DDoS 攻击通常透过多重受损的系统或者装置注入殭尸...

云漫网络Ruan
16分钟前
2
0
从零开始入门 K8s| 阿里技术专家详解 K8s 核心概念

作者| 阿里巴巴资深技术专家、CNCF 9个 TCO 之一 李响 一、什么是 Kubernetes Kubernetes,从官方网站上可以看到,它是一个工业级的容器编排平台。Kubernetes 这个单词是希腊语,它的中文翻译...

阿里巴巴云原生
16分钟前
2
0
修改和编译spring源码,构建jar(spring-context-4.0.2.RELEASE)

上周在定位问题时,发现Spring容器实例化Bean的时候抛出异常,为了查看更详细的信息,决定修改spring-context-4.0.2.RELEASE.jar中的CommonAnnotationBeanPostProcessor类的代码,在里面打印...

程序员欣宸
19分钟前
1
0
MongoDB集群配置

MongoDB集群配置 2019年06月30日 13:21:05 2014Team 阅读数 77更多 分类专栏: MongoDB 版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文...

linjin200
20分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部