BFS POJ 3126 Prime Path-白红宇

BFS POJ 3126 Prime Path

阅读量：5331 次

发布时间：2019-06-14

本文共 1955 字，大约阅读时间需要 6 分钟。

1 /*  2     题意：从一个数到另外一个数，每次改变一个数字，且每次是素数  3     BFS：先预处理1000到9999的素数，简单BFS一下。我没输出Impossible都AC，数据有点弱  4 */  5 /************************************************  6 Author        :Running_Time  7 Created Time  :2015-8-2 15:46:57  8 File Name     :POJ_3126.cpp  9 *************************************************/ 10  11 #include 
     
       12 #include 
      
        13 #include 
       
         14 #include 
        
          15 #include 
         
           16 #include 
          
            17 #include 
           
             18 #include 
            
              19 #include 
             
               20 #include 
              
                21 #include 
               
                 22 #include 
                
                  23 #include 
                  24 #include 
                  
                    25 #include 
                   
                     26 #include 
                    
                      27 #include 
                     
                       28 using namespace std; 29 30 #define lson l, mid, rt << 1 31 #define rson mid + 1, r, rt << 1 | 1 32 typedef long long ll; 33 const int MAXN = 1e4 + 10; 34 const int INF = 0x3f3f3f3f; 35 const int MOD = 1e9 + 7; 36 bool is_prime[MAXN]; 37 bool vis[MAXN]; 38 int x, y, res; 39 struct Digit { 40 int d[5]; 41 int step; 42 }; 43 44 void solve(void) { 45 memset (is_prime, true, sizeof (is_prime)); 46 for (int i=1000; i<=9999; ++i) { 47 for (int j=2; j
                      
                       =1; --i) { 66 tmp.d[i] = u % 10; u /= 10; 67 } 68 tmp.step = 0; 69 queue
                       
                         Q; Q.push (tmp); vis[u] = true; 70 int ans = -1; 71 while (!Q.empty ()) { 72 Digit x = Q.front (); Q.pop (); 73 int m = get_num (x.d); 74 if (m == v) { 75 ans = x.step; break; 76 } 77 for (int i=1; i<=4; ++i) { 78 for (int j=0; j<=9; ++j) { 79 if (i == 1 && j == 0) continue; 80 if (x.d[i] != j) { 81 Digit y = x; 82 y.d[i] = j; m = get_num (y.d); 83 if (is_prime[m] && !vis[m]) { 84 vis[m] = true; y.step++; Q.push (y); 85 } 86 } 87 } 88 } 89 } 90 if (ans == -1) puts ("Impossible"); 91 else printf ("%d\n", ans); 92 } 93 94 int main(void) { //POJ 3126 Prime Path 95 solve (); 96 int T; scanf ("%d", &T); 97 while (T--) { 98 scanf ("%d%d", &x, &y); 99 memset (vis, false, sizeof (vis));100 BFS (x, y);101 }102 103 return 0;104 }