poj 3126 Prime Path( bfs + 素数)

题目:http://poj.org/problem?id=3126

题意:给定两个四位数,求从前一个数变到后一个数最少需要几步,改变的原则是每次只能改变某一位上的一个数,而且每次改变得到的必须是一个素数;

 #include <iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<stack> #include<queue> #include<iomanip> #include<cmath> #include<map> #include<vector> #include<algorithm> using namespace std; ],vis[]; int a,b,t; struct node {     int a,step; }pos,next; void prime() //快速求素数的模板 {     int i,j;     memset(p,-,sizeof(p));     p[]=p[]=;     ; i<; i++)     {         ==) p[i]=;         if(p[i])         ; j<; j+=i)         p[j]=;     } } int change(int x,int i,int j) //i代表改变哪一位(个十百千),j代表改变为几,x是原数 {     )  )*+j;     ) )*+x%+j*;     ) )*+x%+j*;     ) )+j*;     ; } void bfs() {     int i,j;     queue<node>q;     next.a=a; next.step=;     vis[a]=;     q.push(next);     while(!q.empty())     {         pos=q.front();         q.pop();         next.step=pos.step+;         ; i<=; i++)         ; j<; j++)         {             &&j==)             continue;             next.a=change(pos.a,i,j);             if(next.a==b)             {                 cout<<next.step<<endl;                 return;             }             if(p[next.a]&&!vis[next.a])             {                 q.push(next); vis[next.a]=;             }         }     }     cout<<"Impossible"<<endl; } int main() {     prime();     cin>>t;     while(t--)     {         memset(vis,,sizeof(vis));         cin>>a>>b;         if(a==b)         {             cout<<"<<endl;             continue;         }         bfs();     }     ; }