Prime Path(POJ - 3126)
题目链接
算法BFS+筛素数打表
1.题目主要就是给定你两个四位数的质数a，b，让你计算从a变到b共最小需要多少步。要求每次只能变1位，并且变1位后仍然为质数。
2.四位数的范围是1000~9999，之间共有1000多个质数。由于已经知道位数为4位，所以可以通过BFS来寻找最小步数。每次需要分别变换个位、十位、百位、千位，并且把符合要求的数放到队列中，同时需标记这个数已经遍历过一次，避免重复遍历，直到找到目标数。
C++代码 #include<iostream> #include<cstring> #include<queue> using namespace std; const int N = 1e4; int primes[N], cnt; bool st[N]; bool vis[N]; int t, a, b; struct Number{ int data; int steps; }; void get_primes(int n) { for(int i = 2; i <= n; i++) { if(!st[i]) primes[cnt++] = i; for(int j = 0; primes[j] <= n / i; j++) { st[primes[j]*i] = true; if(i % primes[j] == 0) break; } } } void bfs() { queue<Number> que; que.push({a, 0}); vis[a] = true; while(que.size()) { Number cur = que.front(); que.pop(); if(cur.data == b) { cout << cur.steps << endl; return ; } Number tmp; /*遍历可能的个位*/ for(int i = 0; i <= 9; i++) { tmp.data = cur.data / 10 * 10 + i; if(vis[tmp.data] || st[tmp.data]) continue; tmp.steps = cur.steps + 1; que.push(tmp); vis[tmp.data] = true; } /*遍历可能的十位*/ for(int i = 0; i <= 9; i++) { tmp.data = cur.data / 100 * 100 + i * 10 + cur.data % 10; if(vis[tmp.data] || st[tmp.data]) continue; tmp.steps = cur.steps + 1; que.push(tmp); vis[tmp.data] = true; } /*遍历可能的百位*/ for(int i = 0; i <= 9; i++) { tmp.data = cur.data % 100 + i * 100 + cur.data / 1000 * 1000; if(vis[tmp.data] || st[tmp.data]) continue; tmp.steps = cur.steps + 1; que.push(tmp); vis[tmp.data] = true; } /*遍历可能的千位*/ for(int i = 1; i <= 9; i++) { tmp.data = cur.data % 1000 + i * 1000; if(vis[tmp.data] || st[tmp.data]) continue; tmp.steps = cur.steps + 1; que.push(tmp); vis[tmp.data] = true; } } } int main() { get_primes(9999); cin >> t; while(t--) { memset(vis, 0, sizeof vis); cin >> a >> b; bfs(); } }代码中使用的线性筛素数模板来源