题意
给出你两个四位素数，保证这个素数不会有前导0（也就是1003起跳）。给定一个操作，在只改变一位的前提下，把当前素数变为另一个四位素数（无前导0）。现在问你至少进行多少次这样的操作才能把一个素数变为另一个。
思路
素数的朴素判断需要O(sqrt(n))的时间复杂度，显然不符合本题要求。不妨使用欧氏筛法，在O(n)的时间复杂度内预处理出10000以内的全部素数，之后O(1)时间解决查询某个数是否为素数的问题。
解决完素数问题，剩下的就是近似于求最短路的BFS过程了。具体的实作方法可以参考下面的代码。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; vector<int> primes; bool isPrime[10001]; void genPrime(){ memset(isPrime, true, sizeof(isPrime)); isPrime[2] = true; for (int i = 2; i <= 10000; i++) { if (isPrime[i]) { for (int k = 2; k * i <= 10000; k++) { isPrime[k*i] = false; } } } for (int i = 1000; i < 10000; i++) { if (isPrime[i]) { primes.push_back(i); } } } struct State{ int num,step; State(int _num,int _step){ num = _num; step = _step; } State(); }; bool vis[10001]; int bfs(int start,int end){ queue<State> que; que.push(State(start,0)); memset(vis, false, sizeof(vis)); while (!que.empty()) { State now = que.front(); que.pop(); if (now.num == end) { return now.step; } if (vis[now.num]) { continue; } vis[now.num] = true; int fac = (now.num/10)*10; for (int i = 0; i <= 9; i++) { if (!vis[fac + i] && isPrime[fac + i]) { que.push(State(fac+i,now.step+1)); } } fac = (now.num/100)*100+now.num%10; for (int i = 0; i <= 9; i++) { if (!vis[fac + i*10] && isPrime[fac + i*10]) { que.push(State(fac+i*10,now.step+1)); } } fac = (now.num/1000)*1000+now.num%100; for (int i = 0; i <= 9; i++) { if (!vis[fac + i*100] && isPrime[fac + i*100]) { que.push(State(fac+i*100,now.step+1)); } } fac = now.num%1000; for (int i = 1; i <= 9; i++) { if (!vis[fac + i*1000] && isPrime[fac + i*1000]) { que.push(State(fac+i*1000,now.step+1)); } } } return -1; } int main(){ genPrime(); int caseCnt; scanf(" %d",&caseCnt); while (caseCnt--) { int a,b; scanf(" %d %d",&a,&b); int res = bfs(min(a, b),max(a,b)); if (res == -1) { puts("Impossible"); }else{ printf("%d\n",res); } } return 0; } |
