poj 3126 Prime Path

  1 #include<iostream>

  2 #include<cstdio>

  3 #include<cstdlib>

  4 #include<cstring>

  5 #include<string>

  6 #include<queue>

  7 #include<algorithm>

  8 #include<map>

  9 #include<iomanip>

 10 #include<climits>

 11 #include<string.h>

 12 #include<numeric>

 13 #include<cmath>

 14 #include<stdlib.h>

 15 #include<vector>

 16 #include<stack>

 17 #include<set>

 18 #define INF 1e7

 19 #define MAXN 100010

 20 #define maxn 1000010

 21 #define Mod 1000007

 22 #define N 1299800

 23 using namespace std;

 24 typedef long long LL;

 25 

 26 int prime[N];

 27 int vis[N];

 28 void run()

 29 {

 30     int k = 1;

 31     for (LL i = 2; i <= N; ++i)

 32         if (!vis[i]) {

 33             prime[k++] = i;

 34             for (LL j = i*i; j < N; j += i)

 35                 vis[j] = 1;

 36         }

 37     /*for (int i = 1; i < 1300; ++i)

 38         cout << prime[i] << " ";

 39     cout << endl;*/

 40 }

 41 

 42 int n, m;

 43 int T;

 44 int used[11000];

 45 

 46 int bfs()

 47 {

 48     queue<int> q;

 49     int step = 0;

 50     q.push(n);

 51     used[n] = 1;

 52     q.push(-1);

 53     while (!q.empty()) {

 54         int now = q.front();

 55         if (now == -1) {

 56             q.pop();

 57             if (q.empty()) return -1;

 58             step++;

 59             q.push(-1); continue;

 60         }q.pop();

 61         if (now == m) return step;

 62         for (int i = 0; i < 4; ++i) {

 63             if (i == 0) {

 64                 for (int j = 1; j <= 9; ++j) {

 65                     if (now / 1000 == j) continue;

 66                     int next = j * 1000 + now % 1000;

 67                     if (!vis[next] && !used[next]) {

 68                         q.push(next);

 69                         used[next] = 1;

 70                     }

 71                 }

 72             }

 73             else if (i == 1) {

 74                 for (int j = 0; j <= 9; ++j) {

 75                     if ((now / 100) % 10 == j) continue;

 76                     int next = j * 100 + now % 100 + (now / 1000) * 1000;

 77                     if (!vis[next] && !used[next]) {

 78                         q.push(next);

 79                         used[next] = 1;

 80                     }

 81                 }

 82             }

 83             else if (i == 2) {

 84                 for (int j = 0; j <= 9; ++j) {

 85                     if ((now / 10) % 10 == j) continue;

 86                     int next = j * 10 + now % 10 + (now / 100) * 100;

 87                     if (!vis[next] && !used[next]) {

 88                         q.push(next);

 89                         used[next] = 1;

 90                     }

 91                 }

 92             }

 93             else if (i == 3) {

 94                 for (int j = 0; j <= 9; ++j) {

 95                     if (now % 10 == j) continue;

 96                     int next = j + (now / 10) * 10;

 97                     if (!vis[next] && !used[next]) {

 98                         q.push(next);

 99                         used[next] = 1;

100                     }

101                 }

102             }

103         }

104     }

105     return -1;

106 }

107 

108 

109 void process()

110 {

111     memset(used, 0, sizeof(used));

112     scanf("%d%d", &n, &m);

113     int ans = bfs();

114     if (ans == -1) puts("Impossible");

115     else printf("%d
",ans);

116 }

117 

118 int main()

119 {

120     run();

121     scanf("%d", &T);

122     while (T--)

123         process();

124     return 0;

125 }