素数路(prime)-白红宇

素数路(prime)

阅读量：4641 次

发布时间：2019-06-09

本文共 1958 字，大约阅读时间需要 6 分钟。

素数路(prime)

题目描述

已知一个四位的素数，要求每次修改其中的一位，并且要保证修改的结果还是一个素数，还不能出现前导零。你要找到一个修改数最少的方案，得到我们所需要的素数。

例如把1033变到8179，这里是一个最短的方案：

1033

1733

3733

3739

3779

8779

8179

修改了6次。

输入

1行，两个四位的素数（没有前导零），表示初始数和目标数。

输出

一个数，表示最少的操作次数。如果不可能，输出“Impossible”。

样例输入

1033 8179

样例输出

6 分析：bfs，预处理四位素数； 代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set
                    
                     ::iterator it=s.begin();it!=s.end();it++)#define vi vector
                     
                      #define pii pair
                      
                       #define mod 1000000007#define inf 0x3f3f3f3f#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)const int maxn=1e5+10;const int dis[4][2]={ { 0,1},{-1,0},{ 0,-1},{ 1,0}};using namespace std;using namespace __gnu_cxx;ll gcd(ll p,ll q){ return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){ if(q&1)f=f*p;p=p*p;q>>=1;}return f;}int n,m,all,a[maxn],vis[maxn];bool sushu(int p){ if(p<=1)return false; else if(p==2)return true; else if(p%2==0)return false; for(int i=3;i*i<=p;i+=2)if(p%i==0)return false; return true;}void dfs(){ queue
                       
                        p;p.push(n);vis[n]=1; while(!p.empty()) { int u=p.front(),v; p.pop(); if(u==m)return; for(int i=0;i<=9;i++) { v=u-u%10+i; if(!vis[v]&&a[v])p.push(v),vis[v]=vis[u]+1; } for(int i=0;i<=9;i++) { v=u-u/10%10*10+i*10; if(!vis[v]&&a[v])p.push(v),vis[v]=vis[u]+1; } for(int i=0;i<=9;i++) { v=u-u/100%10*100+i*100; if(!vis[v]&&a[v])p.push(v),vis[v]=vis[u]+1; } for(int i=0;i<=9;i++) { v=u-u/1000*1000+i*1000; if(!vis[v]&&a[v])p.push(v),vis[v]=vis[u]+1; } }}int main(){ int i,j,k,t; scanf("%d%d",&n,&m); for(int i=1000;i<=9999;i++) if(sushu(i))a[i]=1; dfs(); if(vis[m])printf("%d\n",vis[m]-1); else puts("Impossible"); //system ("pause"); return 0;}