poj 3126 Prime Path （bfs）

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

题意：给你两个四位数，a和b，然后改变四位中的一位，从a改变到b，每次得到的数必须是素数，求最小改变次数

注意：初始化问题，就是队列一开始一定要是空的。。。（wa了好几次）

代码：

View Code

  1 #include <iostream>
  2 #include<queue>
  3 #include<cmath>
  4 #include<cstring>
  5 using namespace std;
  6 queue<int>q;
  7 int num[10010],m,n;
  8 int vis[10010];
  9 int head,tail;
 10 int flag;
 11 int pan(int a)
 12 {
 13     int i;
 14     int k=sqrt(double(a));
 15     for(i=2;i<=k;i++)
 16     {
 17         if(a%i==0)
 18         return 0;
 19     }
 20     return 1;
 21 }
 22 void bfs(int a)
 23 {
 24     int s;
 25     int i;
 26     for(i=1;i<=9;i++)
 27     {
 28         s=i*1000+a%1000;
 29         if(s==n)
 30         {
 31             cout<<num[a]+1<<endl;
 32             flag=1;
 33             return ;
 34         }
 35         if(pan(s)&&vis[s]==0)
 36         {
 37             q.push(s);
 38             num[s]=num[a]+1;
 39             vis[s]=1;
 40         }
 41     }
 42     for(i=0;i<=9;i++)
 43     {
 44         s=(a/1000)*1000+i*100+a%100;
 45         if(s==n)
 46         {
 47             cout<<num[a]+1<<endl;
 48             flag=1;
 49             return ;
 50         }
 51         if(pan(s)&&vis[s]==0)
 52         {
 53             q.push(s);
 54             num[s]=num[a]+1;
 55             vis[s]=1;
 56         }
 57     }
 58     for(i=0;i<=9;i++)
 59     {
 60 
 61         s=(a/100)*100+i*10+a%10;
 62         if(s==n)
 63         {
 64             cout<<num[a]+1<<endl;
 65             flag=1;
 66             return ;
 67         }
 68         if(pan(s)&&vis[s]==0)
 69         {
 70             q.push(s);
 71             num[s]=num[a]+1;
 72             vis[s]=1;
 73         }
 74     }
 75     for(i=1;i<=9;i+=2)
 76     {
 77         s=(a/10)*10+i;
 78         if(s==n)
 79         {
 80             cout<<num[a]+1<<endl;
 81             flag=1;
 82             return ;
 83         }
 84         if(pan(s)&&vis[s]==0)
 85         {
 86             q.push(s);
 87             num[s]=num[a]+1;
 88             vis[s]=1;
 89         }
 90     }
 91     return ;
 92 }
 93 int main()
 94 {
 95 
 96     int t;
 97     cin>>t;
 98     while(t--)
 99     {
100         while(!q.empty())
101         {
102             q.pop();
103         }
104         cin>>m>>n;
105         int s;
106         if(m==n)
107         {
108             flag=1;
109             cout<<"0"<<endl;
110         }
111         else
112         {
113             memset(vis,0,sizeof(vis));
114             q.push(m);
115             vis[m]=1;
116             num[m]=0;
117             flag=0;
118             while(!q.empty())
119             {
120                 s=q.front();
121                 bfs(s);
122                 if(flag)
123                 {
124                     break;
125                 }
126                 q.pop();
127             }
128         }
129         if(!flag)
130         {
131             cout<<"Impossible"<<endl;
132         }
133     }
134     return 0;
135 }