TOP

kuangbin专题 专题一 简单搜索 Prime Path POJ - 3126
2019-07-10 16:11:19 】 浏览:45
Tags:kuangbin 专题 简单 搜索 Prime Path POJ 3126


题目链接:https://vjudge.net/problem/POJ-3126

题意:给你两个四位的素数N,M,每次改变N四位数中的其中一位,如果能经过有限次数的替换变成四位数M,那么求出最少替换次数,否则输出“Impossible”.(N,M必须一直是素数)

思路:bfs。四位数,每一位可以替换为0~9,那么我们可以每次改变N中的一位数,然后放入队列中,当然,在替换数字时难免会出现重复的四位数,这样会造成TLE,那么我们可以创建一个bool数组标记出现过的,我们也需要素数筛999 ~ 10000之间的素数(你想删哪里到哪就到哪里,不要纠结),因为是bfs,所以第一次出现的新的四位素数一定是替换次数最少的,那么题目就简单了。


 

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;  7 
 8 #define inf (1LL << 31) - 1
 9 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
 10 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
 11 #define per(i,j,k) for(int i = (j); i >= (k); i--)
 12 #define per__(i,j,k) for(int i = (j); i > (k); i--)
 13 
 14 const int N = (int)1e4 + 10;  15 bool vis[N]; //素数表 0为素数
 16 bool app[N]; //标记是否出现过
 17 int ans;  18 
 19 struct node{  20 
 21     int a[4];  22     int cost;  23 
 24     node(int* a,int e){  25         rep(i, 0, 3){  26             this->a[i] = a[i];  27  }  28         this->cost = e;  29  }  30 
 31     int x(){ //返回四位数的成员函数
 32         int num = 0;  33         rep(i, 0, 3) num = num * 10 + a[i];  34         return num;  35  }  36 };  37 
 38 void get_Prime(){ //素数打表
 39 
 40     rep(i, 2, (int)sqrt(N*1.0)){  41         if (!vis[i]){  42             for (int p = i * i; p <= N; p += i) vis[p] = true;  43  }  44  }  45 }  46 
 47 bool work(int x[], int y){  //true为有答案,false为没答案
 48 
 49     queue<node> que;  50     node t (x,0);  51 
 52     app[t.x()] = true;  53 
 54  que.push(t);  55 
 56     if (t.x() == y){  57         ans = 0;  58         return true;  59  }  60 
 61     while (!que.empty()){  62 
 63         node tmp = que.front();  64  que.pop();  65 
 66         rep(i, 0, 3){ //1~4不同位置
 67             rep(j, 0, 9){ //替换为0~9
 68                 if (i == 0 && j == 0) continue; //第一位不能是0
 69                 int tt = tmp.a[i]; //暂存该数
 70                 tmp.a[i] = j;      //改变  71                 
 72                 //该四位数没有出现过且该数是素数
 73                 if (!app[tmp.x()] && !vis[tmp.x()]){  74 
 75                     app[tmp.x()] = true; //标记一下
 76 
 77                     if (tmp.x() == y){ //如果变成了想变成的数了
 78                         ans = tmp.cost + 1;  79                         return true;  80  }  81                     que.push(node{tmp.a,tmp.cost + 1}); //新的四位数放入队列,花费加一
 82  }  83                 tmp.a[i] = tt; //变回原来的四位数
 84  }  85  }  86 
 87  }  88 
 89     return false;  90 }  91 
 92 int main(){  93 
 94     ios::sync_with_stdio(false);  95     cin.tie(0);  96 
 97     get_Prime();//得到素数表
 98     int n;  99     cin >> n; 100 
101     int a, b; 102     while (n--){ 103 
104         memset(app, 0, sizeof(app)); //每次初始化
105 
106         cin >> a >> b; 107 
108         int aa[4]; 109         int len = 0; 110         rep(i, 0, 3){ 111             aa[3-len++] = a % 10; 112             a /= 10; 113         } //分割a变为四个数 114 
115         //node tmp(aa, 0); 116         //cout << "tmp:::" << tmp.x() << endl;
117 
118         if (work(aa, b)) cout << ans << endl; 119         else cout << "Impossible" << endl; 120  } 121     
122     return 0; 123 }

 

 




kuangbin专题 专题一 简单搜索 Prime Path POJ - 3126 https://www.cppentry.com/bencandy.php?fid=49&id=227475

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇kuangbin专题 专题一 简单搜索 Fi.. 下一篇kuangbin专题 专题一 简单搜索 棋..