文档章节

sicily 1444 Prime Path

Ciel
 Ciel
发布于 2013/01/04 23:41
字数 788
阅读 49
收藏 0

Description

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices. 
— It is a matter of security to change such things every now and then, to keep the enemy in the dark. 
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know! 
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door. 
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime! 
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds. 
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime. 

Now, the minister of finance, who had been eavesdropping, intervened. 
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound. 
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you? 
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above. 
1033
1733
3733
3739
3779
8779
8179
The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input

One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).

Output

One line for each case, either with a number stating the minimal cost or containing the word Impossible.

Sample Input

3
1033 8179
1373 8017
1033 1033

Sample Output

6
7
0

分析:

本题主要是为了找到路线的最短长度,但并不要求完整路径,而且DFS方法可能会产生指数型时间复杂度的操作数,明显应该使用BFS方法。但是,要注意到本题的一些陷阱,改变单个位置的数字产生的中间数以及初始数可能会大于结果要求的数字,所以要每位从零到九变化并且不包括原先未变化的数字。当然必须保证得到的数字都是真正的四位数。剩余要注意的就是筛法素数表和取特定位置数字,不再详述。

代码:

// Problem#: 1444
// Submission#: 1858029
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

#define MAX 10000
#define DEBUG 1

bool isprime[MAX];
bool visit[MAX];
struct node{
    int value;
    int step;
    node( int a, int b ){
        value = a;
        step = b;
    }
};
int pos[5] = {1,10,100,1000,10000};

void sieve(){
    memset(isprime,true,sizeof(isprime));
    isprime[0] = isprime[1] = false;
    for( int i=2 ; i<=100 ; i++ )
        for( int j=i ; i*j<=MAX ; j++ )
            if( isprime[i] ) isprime[i*j] = false;
}

inline int digit( int a, int n ){
    return (a % pos[n]) / pos[n-1]; 
}

void bfs( int a, int b ){
    queue<node> buffer;
    buffer.push(node(a,0));
    memset(visit,false,sizeof(visit));
    visit[a] = true;
    while( !buffer.empty() ){
        node tmp = buffer.front();
        buffer.pop();
        if( tmp.value==b ){
            cout << tmp.step << endl;
            return ;
        }
        for( int i=3 ; i>=0 ; i-- ){
            node next = tmp;
            next.step++;
            int temp = next.value - digit(next.value,i+1) * pos[i];
            for( int j=0 ; j <= 9 ; j++ ){
                next.value = temp + j*pos[i];
                if( next.value==tmp.value || next.value<1000 ) continue;
                if( isprime[next.value] && !visit[next.value] ){
                    buffer.push(next);
                    visit[next.value] = true;
                }
            }
        }
    }
    cout << "Impossible" << endl;
}

int main(){
    sieve();
    int n,a,b;
    cin >> n;
    while(n--){
        cin >> a >> b;
        bfs(a,b);
    }
    return 0;
}

© 著作权归作者所有

Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
使用xxl-job-spring-boot-starter开发xxl-job执行器

简述 本文简单描述如何使用xxl-job-spring-boot-starter开发xxl-job的执行器服务。 开发步骤 添加依赖 创建一个Spring Boot项目 添加依赖包 修改xxl-job配置 添加以下xxl-job配置,也可不配置...

centychen
05/10
401
0
Oracle 11g R2 ADG 搭建

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v$database; 如果为noarchivelog模式,切换到archivelo......

UltraSQL
2018/07/23
0
0
渗透杂记2015-01-21

今天来熟悉一下meterpreter,使用环境是KALI、windowsXP Kali地址:192.168.11.41 windowsXP地址:192.168.11.58 首先生成可执行文件 root@kali:~# msfpayload windows/meterpreter/reverset......

w2630460
2015/01/21
0
0
jsp+javabean数据库操作报错

关于jsp中使用javabean老报空指针异常javbean代码: public class connectsql { public static Statement getStatement(){ Connection conn=null; Statement stmt=null; String url="jdbc:sq......

淡淡爱ing
2016/04/23
141
1
Hibernate Validator 6.0.8 发布,支持 WildFly 12

Hibernate Validator 6.0.8.Final 发布了,建议 6.x 版本的用户尽快升级,特别是 6.0.7 版本。 该版本主要更新内容包括将有效载荷传递给约束验证器,一些性能改进(HV-1566、HV-1543 和 HV-1...

淡漠悠然
2018/03/09
771
3

没有更多内容

加载失败,请刷新页面

加载更多

Spring使用ThreadPoolTaskExecutor自定义线程池及实现异步调用

多线程一直是工作或面试过程中的高频知识点,今天给大家分享一下使用 ThreadPoolTaskExecutor 来自定义线程池和实现异步调用多线程。 一、ThreadPoolTaskExecutor 本文采用 Executors 的工厂...

CREATE_17
今天
5
0
CSS盒子模型

CSS盒子模型 组成: content --> padding --> border --> margin 像现实生活中的快递: 物品 --> 填充物 --> 包装盒 --> 盒子与盒子之间的间距 content :width、height组成的 内容区域 padd......

studywin
今天
7
0
修复Win10下开始菜单、设置等系统软件无法打开的问题

因为各种各样的原因导致系统文件丢失、损坏、被修改,而造成win10的开始菜单、设置等系统软件无法打开的情况,可以尝试如下方法解决 此方法只在部分情况下有效,但值得一试 用Windows键+R打开...

locbytes
昨天
8
0
jquery 添加和删除节点

本文转载于:专业的前端网站➺jquery 添加和删除节点 // 增加一个三和一节点function addPanel() { // var newPanel = $('.my-panel').clone(true) var newPanel = $(".triple-panel-con......

前端老手
昨天
8
0
一、Django基础

一、web框架分类和wsgiref模块使用介绍 web框架的本质 socket服务端 与 浏览器的通信 socket服务端功能划分: 负责与浏览器收发消息(socket通信) --> wsgiref/uWsgi/gunicorn... 根据用户访问...

ZeroBit
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部