首页 > > 程序设计 > C/C++ >

kuangbin专题专题一简单搜索 Prime Path POJ -…

2019-08-16 07:48:07来源：博客园阅读 ()

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 }