一天一道算法题--5.25--bfs或者最短路

  1 #include <iostream>
  2 #include <cstring>
  3 #include <queue>
  4 using namespace std;
  5 
  6 const int num = 10010;
  7 bool vis[num];
  8 bool prime[num];
  9 int step[num];
 10 
 11 void judge( int n )
 12 {
 13     bool flag = false;
 14     for( int i = 2 ; i*i<=n ; i++ )
 15     {
 16         if( n%i == 0 )
 17         {
 18             flag = true;
 19             break;
 20         }
 21     }
 22     if( flag )
 23         prime[n] = true;//合数 就是 true
 24 }
 25 
 26 bool bfs( int st , int end )
 27 {
 28     int temp;
 29     int i;
 30     int a , b;
 31     queue<int>q;
 32     while( !q.empty() )
 33         q.pop();
 34     q.push(st);
 35     if( st==end )
 36     {
 37         return true;
 38     }
 39     while( !q.empty() )
 40     {
 41         int now = q.front();
 42         q.pop();
 43         if( now == end )
 44             return true;
 45         a = now%10; //个位上的数
 46         b = (now/10)%10;//十位上的数
 47         //枚举个位：肯定是奇数 不然不可能是素数
 48         for( i = 1 ; i<=9 ; i+=2 )
 49         {
 50             temp = (now/10)*10 + i;
 51             if( temp!=now && !vis[temp] && !prime[temp] )
 52             {
 53                 vis[temp] = true;
 54                 step[temp] = step[now] + 1;
 55                 q.push( temp );
 56             }
 57         }
 58         //枚举十位：
 59         for( i = 0 ; i<=9 ; i++ )
 60         {
 61             temp = ( now/100 )*100 + 10*i +a;
 62             if( temp!=now && !vis[temp] && !prime[temp] )
 63             {
 64                 vis[temp] = true;
 65                 step[temp] = step[now] + 1;
 66                 q.push( temp );
 67             }
 68         }
 69         //枚举百位：
 70         for( i = 0 ; i<=9 ; i++ )
 71         {
 72             temp = ( now/1000)*1000 + 100*i + 10*b + a;
 73             if( temp!=now && !vis[temp] && !prime[temp] )
 74             {
 75                 vis[temp] = true;
 76                 step[temp] = step[now] + 1;
 77                 q.push( temp );
 78             } 
 79         }
 80         //枚举千位  肯定不能以0开头
 81         for( i = 1 ; i<=9 ; i++ )
 82         {
 83             temp = now%1000 + i*1000;
 84             if( temp!=now && !vis[temp] && !prime[temp] )
 85             {
 86                 vis[temp] = true;
 87                 step[temp] = step[now] + 1;
 88                 q.push( temp );
 89             }
 90         }
 91     }
 92     return false;
 93 }
 94 
 95 int main()
 96 {
 97     int t;
 98     int st , end;
 99     memset( prime , false , sizeof(prime) );
100     for( int i = 1000 ; i<=9999 ; i++ )
101     {
102         judge(i);
103     }
104     while( ~scanf("%d",&t) )
105     {            
106         while( t-- )
107         {
108             memset( vis , false , sizeof(vis) );
109             memset( step , 0 , sizeof(step) );
110             scanf( "%d %d",&st,&end );
111             if( bfs( st , end ) )
112             {
113                 printf( "%d\n",step[end] );
114             }
115             else
116             {
117                 printf( "Impossible\n" );
118             }
119         }
120     }
121     return 0;
122 }