POJ3126 Prime Path(BFS)

January 17, 2016

题目链接

题意:从一个四位质数到另一个四位质数,每次只能改变一位的数字并且改变后的数字也是质数,数字不可以重复,为多少步。

思路:入口为 40 的 BFS,剪枝如下:千位没有 0,个位偶数的都不是质数。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
int a, b;
bool vis[10005];
struct point{
    int n;
    int cnt;      //步数
};
bool judge(int x){   //是否为质数
    for(int i = 2; i <= sqrt(x); i++)
        if(x%i == 0)
            return 0;
    return 1;
}
void bfs(){
    queue<point> q;
    point p1, p2;
    p1.cnt = 0;
    p1.n = a;
    vis[a] = 1;
    q.push(p1);
    while(!q.empty()){
        p1 = q.front();
        if(p1.n == b){
            cout << p1.cnt << endl;
            return;
        }
        q.pop();
        int ge = p1.n%10;          //个位
        int shi = (p1.n/10)%10;     //十位
        int bai = (p1.n/100)%10;     //百位
        int qian = p1.n/1000;     //千位
        for(int i = 1; i < 10; i+=2){
            int w = p1.n-ge+i;
            if(w != p1.n && !vis[w] && judge(w)){
                vis[w] = 1;
                p2.n = w;
                p2.cnt = p1.cnt+1;
                q.push(p2);
            }
        }
        for(int i = 0; i < 10; i++){
            int w = p1.n-shi*10+i*10;
            if(w != p1.n && !vis[w] && judge(w)){
                vis[w] = 1;
                p2.n = w;
                p2.cnt = p1.cnt+1;
                q.push(p2);
            }
        }
        for(int i = 0; i < 10; i++){
            int w = p1.n-bai*100+i*100;
            if(w != p1.n && !vis[w] && judge(w)){
                vis[w] = 1;
                p2.n = w;
                p2.cnt = p1.cnt+1;
                q.push(p2);
            }
        }
        for(int i = 1; i < 10; i++){
            int w = p1.n-qian*1000+i*1000;
            if(w != p1.n && !vis[w] && judge(w)){
                vis[w] = 1;
                p2.n = w;
                p2.cnt = p1.cnt+1;
                q.push(p2);
            }
        }
    }
    cout << "Impossible" << endl;
    return;
}
int main(){
    //freopen("a.txt", "r", stdin);
    int num; cin >> num;
    while(num--){
        scanf("%d %d", &a, &b);
        memset(vis, 0, sizeof(vis));
        bfs();
    }
    return 0;
}

Profile picture

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]