題意：一個四位數的質數，每次只能變換一個數字，而且變換后的數也要為質數。給出兩個四位數的質數，輸出第一個數變換為第二個數的最少步驟。
利用廣搜就能很快解決問題了。還有一個要注意的地方，千位要大于0。例如0373這個數不符合要求。
#include <iostream> #include <cstdio> #include <queue> #include <cmath> #include <map> using namespace std;struct Struct {int num;int step; }; bool Prime(int a) //判斷是否為質數 {for(int i=2;i<=sqrt(a);i++)if(a%i==0)return false;return true; } int bfs(int a,int b) {queue<Struct>q;map<int,bool>m; //用map來標記數字是否被訪問過 Struct temp,next;temp.num=a;temp.step=0;m[a]=true;q.push(temp);while(!q.empty()){temp=q.front();if(temp.num==b)return temp.step;q.pop();for(int i=1;i<10;i++) //變換千位 {next=temp;next.num=next.num%1000+i*1000;if(!m[next.num] && Prime(next.num)){m[next.num]=true;next.step++;q.push(next);}}int x=100;for(int i=0;i<3;i++) //變換百位，十位，個位 {for(int j=0;j<10;j++){next=temp;next.num=next.num%x+j*x+next.num/(x*10)*(x*10);if(!m[next.num] && Prime(next.num)){m[next.num]=true;next.step++;q.push(next);}}x=x/10;}}return -1; } int main() {//freopen("in.txt","r",stdin);int n;scanf("%d",&n);while(n--){int a,b;scanf("%d%d",&a,&b);int ans=bfs(a,b);if(ans!=-1)printf("%d\n",ans);elseprintf("Impossible\n");}return 0; }
?
