bfs--POJ 3126Prime Path

思路： 搜索位上的数字 可以构成素数 #include <iostream> #include <stdio.h> #include <queue> #include <cstring> using namespace std; int n, m; int prime[10000]; void init() { int i,j; for( i=1000;i<=9999;i++) { for(j=2;j<=i/2;j++) if(i%j==0) break; if(j==i/2+1) prime[i]=1; } } const int N = 10010; int vis[N]; struct node { int x, step; }; queue<node > Q; void bfs() { int x,stp,i; while(!Q.empty()) { node tmp; tmp=Q.front(); Q.pop(); x=tmp.x; stp=tmp.step; if(x==m) { printf("%d\n",stp); return ; } for(int i=1;i<=9;i+=2) { int tep=x/10*10+i; if((!vis[tep])&&(tep!=x)&&(prime[tep])) { vis[tep]=1; node temp; temp.x=tep; temp.step=stp+1; Q.push(temp); } } for(int i=0;i<=9;i++) { int tep=x/100*100+i*10+x%10; if(!vis[tep]&&tep!=x&&prime[tep]) { vis[tep]=1; node temp; temp.x=tep; temp.step=stp+1; Q.push(temp); } } for(int i=0;i<=9;i++) { int tep=x/1000*1000+i*100+x%100; if(!vis[tep]&&tep!=x&&prime[tep]) { vis[tep]=1; node temp; temp.x=tep; temp.step=stp+1; Q.push(temp); } } for(int i=1;i<=9;i++) { int tep=i*1000+x%1000; if(!vis[tep]&&tep!=x&&prime[tep]) { vis[tep]=1; node temp; temp.x=tep; temp.step=stp+1; Q.push(temp); } } } printf("Impossible\n"); return ; } int main() { int t; cin>>t; init(); while(t--) { while(!Q.empty()) Q.pop(); memset(vis,0,sizeof(vis)); cin>>n>>m; vis[n]=1; node tmp; tmp.x=n; tmp.step=0; Q.push(tmp); bfs(); } return 0; }