【搜索】 Prime Path

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;

int n, m;
const int N = 1e4 + 100;
int vis[N];
struct node
{
    int x, step;
};
queue<node> Q;

bool judge_prime(int x) //判断素数
{
    if(x == 0 || x == 1)
        return false;
    else if(x == 2 || x == 3)
        return true;
    else
    {
        for(int i = 2; i <= (int)sqrt(x); i++)
            if(x % i == 0)
                return false;
        return true;
    }
}

void BFS()
{
    int X, STEP, i;
    while(!Q.empty())
    {
        node tmp;
        tmp = Q.front();
        Q.pop();
        X = tmp.x;
        STEP = tmp.step;
        if(X == m)
        {
            printf("%d\n",STEP);
            return ;
        }
        for(i = 1; i <= 9; i += 2) //个位
        {
            int s = X / 10 * 10 + i;
            if(s != X && !vis[s] && judge_prime(s))
            {
                vis[s] = 1;
                node temp;
                temp.x = s;
                temp.step = STEP + 1;
                Q.push(temp);
            }
        }
        for(i = 0; i <= 9; i++) //十位
        {
            int s = X / 100 * 100 + i * 10 + X % 10;
            if(s != X && !vis[s] && judge_prime(s))
            {
                vis[s] = 1;
                node temp;
                temp.x = s;
                temp.step = STEP + 1;
                Q.push(temp);
            }
        }
        for(i = 0; i <= 9; i++) //百位
        {
            int s = X / 1000 * 1000 + i * 100 + X % 100;
            if(s != X && !vis[s] && judge_prime(s))
            {
                vis[s] = 1;
                node temp;
                temp.x = s;
                temp.step = STEP + 1;
                Q.push(temp);
            }
        }
        for(i = 1; i <= 9; i++) //千位
        {
            int s = i * 1000 + X % 1000;
            if(s != X && !vis[s] && judge_prime(s))
            {
                vis[s] = 1;
                node temp;
                temp.x = s;
                temp.step = STEP + 1;
                Q.push(temp);
            }
        }
    }
    printf("Impossible\n");
    return ;
}

int main()
{
    int t, i;
    scanf("%d",&t);
    while(t--)
    {
        while(!Q.empty()) Q.pop();
        scanf("%d%d",&n,&m);
        memset(vis,0,sizeof(vis));
        vis[n] = 1;
        node tmp;
        tmp.x = n;
        tmp.step = 0;
        Q.push(tmp);
        BFS();
    }
    return 0;
}
时间: 02-11

【搜索】 Prime Path的相关文章

搜索------prime path

给定两个数a,b,每次只能变动a的其中一个数,变成的数也必须是素数,问最少经过几次可以变成b: ---------------------------------------------------------------------------------------------- #include<stdio.h>#include<string.h>#include<algorithm>#include<queue>#include<stack&g

Prime Path (poj 3126 bfs)

Language: Default Prime Path Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 11703   Accepted: 6640 Description The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to c

F - Prime Path POJ 3126 筛选素数+bfs

F - Prime Path Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 3126 Description The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have t

(简单) POJ 3126 Prime Path,BFS。

Description The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices. — It is a matter of security to change such things every now

双向广搜 POJ 3126 Prime Path

POJ 3126  Prime Path Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 16204   Accepted: 9153 Description The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change th

poj 3126 Prime Path (bfs)

Prime Path Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 13813   Accepted: 7796 Description The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-dig

POJ 3126 Prime Path(BFS)

Prime Path Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 12060   Accepted: 6843 Description The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-dig

Prime Path bfs搞定

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices. — It is a matter of security to change such things every now and then, to

POJ 3126 Prime Path(素数路径)

p.MsoNormal { margin-bottom: 10.0000pt; font-family: Tahoma; font-size: 11.0000pt } h1 { margin-top: 5.0000pt; margin-bottom: 5.0000pt; text-align: left; font-family: 宋体; font-weight: bold; font-size: 24.0000pt } span.10 { font-family: "Times New Rom

hdu 1973 Prime Path

题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=1973 Prime Path Description The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices