素数路径Prime Path POJ-3126 素数，BFS

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：Prime Path

题目大意

从一个四位素数m开始，每次只允许变动一位数字使其变成另一个四位素数。求最终把m变成n所需的最少次数。

思路

BFS。搜索的时候，最低位为0，2，4，6，8可以先排除（偶数不会是素数），最高位是0的也可以排除。这个题判断素数的次数比较少，可以不打素数表。

题解

第二次写的时候代码写的很乱。。没有第一遍干净了

 #include <iostream>

 #include <cstring>

 #include <queue>

 using namespace std;

 int num, m, n, ans;

 int vis[];

 int a[] = {,,,,,,,,,};

 int digit[];

 struct point

 {

     int val;

     int step;

 }p;

 void div(int x)        //把数拆分

 {

     for(int i = ; i < ; i++)

     {

         digit[i] = x % ;

         x = x/;

     }

 }

 bool isPrime(int n)

 {

     for(int i = ; i*i <= n; i++)

     {

         if(n % i == )

         {

             return false;

         }

     }

     return true;

 }

 int bfs(int m, int n)

 {

     queue<point> q;

     p.val = m;

     p.step = ;

     q.push(p);

     while(!q.empty())

     {

         point cur = q.front();

         if(cur.val == n)

         {

             return cur.step;

         }

         //cout << cur.val << " ";

         vis[cur.val] = ;

         div(cur.val);

         for(int i = ; i < ; i++)

         {

             if(i == digit[] || i ==  || i ==  || i ==  || i == ) continue;

             int x = digit[]* + digit[]* + digit[]* + i;

             if(vis[x] || !isPrime(x)) continue;

             p.val = x;

             p.step = cur.step+;

             q.push(p);

         }

         for(int i = ; i < ; i++)

         {

             if(i == digit[]) continue;

             int x = digit[]* + digit[]* + i* + digit[];

             if(vis[x] || !isPrime(x)) continue;

             p.val = x;

             p.step = cur.step+;

             q.push(p);

         }

         for(int i = ; i < ; i++)

         {

             if(i == digit[]) continue;

             int x = digit[]* + i* + digit[]* + digit[];

             if(vis[x] || !isPrime(x)) continue;

             p.val = x;

             p.step = cur.step+;

             q.push(p);

         }

         for(int i = ; i < ; i++)

         {

             if(i == digit[]) continue;

             int x = i* + digit[]* + digit[]* + digit[];

             if(vis[x]|| !isPrime(x)) continue;

             p.val = x;

             p.step = cur.step+;

             q.push(p);

         }

         q.pop();

     }

     return -;            //没有找到

 }

 int main(int argc, char const *argv[])

 {

     #ifdef debug

         freopen("test.txt","r",stdin);

     #endif

     cin >> num;

     while(num--)

     {

         memset(vis,  ,sizeof(vis));

         cin >> m >> n;

         ans = bfs(m, n);

         if (ans == -)

         {

             cout << "Impossible" << endl;

             continue;

         }

         cout << ans << endl;

     }

 }