POJ 3126 Prime Path

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<queue>
  5 #include<algorithm>
  6 using namespace std;
  7 
  8 int n, m;
  9 const int N = 1e4 + 100;
 10 int vis[N];
 11 struct node
 12 {
 13     int x, step;
 14 };
 15 queue<node> Q;
 16 
 17 bool judge_prime(int digit) //判断素数
 18 {
 19     if(digit==2 || digit==3)
 20         return true;
 21     else if(digit<=1 || digit%2==0)
 22         return false;
 23     else
 24     {
 25         for(int i=3;i*i<=digit;i+=2)
 26             if(digit%i==0)
 27                 return false;
 28         return true;
 29     }
 30 }
 31 
 32 void BFS()
 33 {
 34     int X, STEP, i;
 35     while(!Q.empty())
 36     {
 37         node tmp;
 38         tmp = Q.front();
 39         Q.pop();
 40         X = tmp.x;
 41         STEP = tmp.step;
 42         if(X == m)
 43         {
 44             printf("%d
",STEP);
 45             return ;
 46         }
 47         for(i = 1; i <= 9; i += 2) //个位
 48         {
 49             int s = X / 10 * 10 + i;
 50             if(s != X && !vis[s] && judge_prime(s))
 51             {
 52                 vis[s] = 1;
 53                 node temp;
 54                 temp.x = s;
 55                 temp.step = STEP + 1;
 56                 Q.push(temp);
 57             }
 58         }
 59         for(i = 0; i <= 9; i++) //十位
 60         {
 61             int s = X / 100 * 100 + i * 10 + X % 10;
 62             if(s != X && !vis[s] && judge_prime(s))
 63             {
 64                 vis[s] = 1;
 65                 node temp;
 66                 temp.x = s;
 67                 temp.step = STEP + 1;
 68                 Q.push(temp);
 69             }
 70         }
 71         for(i = 0; i <= 9; i++) //百位
 72         {
 73             int s = X / 1000 * 1000 + i * 100 + X % 100;
 74             if(s != X && !vis[s] && judge_prime(s))
 75             {
 76                 vis[s] = 1;
 77                 node temp;
 78                 temp.x = s;
 79                 temp.step = STEP + 1;
 80                 Q.push(temp);
 81             }
 82         }
 83         for(i = 1; i <= 9; i++) //千位
 84         {
 85             int s = i * 1000 + X % 1000;
 86             if(s != X && !vis[s] && judge_prime(s))
 87             {
 88                 vis[s] = 1;
 89                 node temp;
 90                 temp.x = s;
 91                 temp.step = STEP + 1;
 92                 Q.push(temp);
 93             }
 94         }
 95     }
 96     printf("Impossible
");
 97     return ;
 98 }
 99 
100 int main()
101 {
102     int t;
103     scanf("%d",&t);
104     while(t--)
105     {
106         while(!Q.empty()) Q.pop();
107         scanf("%d%d",&n,&m);
108         memset(vis,0,sizeof(vis));
109         vis[n] = 1;
110         node tmp;
111         tmp.x = n;
112         tmp.step = 0;
113         Q.push(tmp);
114         BFS();
115     }
116     return 0;
117 }