題目：

孤單的zydsg又一次孤單的度過了520，不過下一次不會再這樣了。zydsg要做些改變，他想去和素數(shù)小姐姐約會。
所有的路口都被標(biāo)號為了一個4位素數(shù)，zydsg現(xiàn)在的位置和素數(shù)小姐姐的家也是這樣，如果兩個路口間只差1個數(shù)字，則有一條路連通兩個路口。（例如1033和1073間有一條路連接）
現(xiàn)在，你知道了zydsg的位置和素數(shù)小姐姐的家，問最少zydsg要走多少條路才能見到素數(shù)小姐姐。例如：如果zydsg在1033，素數(shù)小姐姐的家在8179，最少要走6條街，走法為：
1033
1733
3733
3739
3779
8779
8179
Input
輸入數(shù)據(jù)有多組，首先是一個數(shù)字n，代表之后有n組數(shù)據(jù)。 其次，在每一組輸入中，都包含兩個數(shù)字a和b，代表zydsg的位置和素數(shù)小姐姐家的位置。 其中，a和b都是四位數(shù)，而且不含前導(dǎo)0。
Output
每組輸入輸出一行，表示zydsg最少需要走多少條路。若不存在合法的路徑，則輸出單詞“Impossible”。
Sample Input
3
1033 8179
1373 8017
1033 1033
Sample Output
6
7
0

分析與解答：

水題，一個 結(jié)點 改個位十位百位千位，最終到達要求的答案，仍然是層次遍歷，把各個位的數(shù)都變一遍存到隊列里，然后一層存完，拿出隊首，再往里面存，直到隊首剛好是答案，那就輸出并return。
注意這個是多實例，也就是說需要多個queue，所以每次bfs之前注意把前面的queue清空，這題我是把queue定義到外面了，如果定義到bfs里面，就不用再清空queue了
代碼參考：
https://blog.csdn.net/LYHVOYAGE/article/details/18228531

#include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<algorithm> using namespace std;int n, m; const int N = 1e4 + 100; int vis[N]; struct node {int x, step; }; queue<node> Q;int prime[10001]; int pri(int k){for(int i=2;i*i<=k;++i){if(k%i==0) return 0;}return 1; }void abd(){memset(prime,0,sizeof(prime));for(int i=1000;i<=9999;++i){if(pri(i)) prime[i]=1;} }void BFS(int n) {node tmp;tmp.x = n;tmp.step = 0;Q.push(tmp);int X, STEP, i;while(!Q.empty()){node tmp;tmp = Q.front();Q.pop();X = tmp.x;STEP = tmp.step;if(X == m){printf("%d\n",STEP);return ;}for(i = 1; i <= 9; i += 2) //個位{int s = X / 10 * 10 + i;if(s != X && !vis[s] && prime[s]){vis[s] = 1;node temp;temp.x = s;temp.step = STEP + 1;Q.push(temp);}}for(i = 0; i <= 9; i++) //十位{int s = X / 100 * 100 + i * 10 + X % 10;if(s != X && !vis[s] && prime[s]){vis[s] = 1;node temp;temp.x = s;temp.step = STEP + 1;Q.push(temp);}}for(i = 0; i <= 9; i++) //百位{int s = X / 1000 * 1000 + i * 100 + X % 100;if(s != X && !vis[s] && prime[s]){vis[s] = 1;node temp;temp.x = s;temp.step = STEP + 1;Q.push(temp);}}for(i = 1; i <= 9; i++) //千位{int s = i * 1000 + X % 1000;if(s != X && !vis[s] && prime[s]){vis[s] = 1;node temp;temp.x = s;temp.step = STEP + 1;Q.push(temp);}}}printf("Impossible\n");return ; }int main() {int t, i;scanf("%d",&t);abd();while(t--){while(!Q.empty()) Q.pop();scanf("%d%d",&n,&m);memset(vis,0,sizeof(vis));vis[n] = 1;BFS(n);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的（BFS）Prime Path （poj3126）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。