POJ 3126 Prime Path bfs, 水题 难度:0

题目

http://poj.org/problem?id=3126

题意

多组数据，每组数据有一个起点四位数s， 要变为终点四位数e，　此处s和e都是大于1000的质数，现在要找一个最短的路径把s变为e，每步可以做如下操作，把当前的s中的四位数上的某一位改变，比如1009可以变为2009，1008，1309,1049，然后检验结果是否为大于1000的质数，如果是，那就可以把s变为这个数。

思路

质数明显需要先处理出来，然后采用bfs获取结果即可。

感想

下次需要先计算空间复杂度, 1e8的空间复杂度肯定会MLE

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <map>

#include <set>

#include <queue>

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

const int maxn = 10000;

bool p[maxn];

int ans[maxn];

int b[9 * 4], num;

void calPrime()

{

    p[2] = true;

    for(int i = 3; i < maxn; i += 2)p[i] = true;

    for(int i = 3; i < maxn; i += 2)

    {

        if(p[i])

        {

            for(int j = 3; j * i < maxn; j+= 2)

            {

                p[i * j] = false;

            }

        }

    }

}

void getSameShape(int s)

{

    num = 0;

    for(int base = 1; base < maxn; base *= 10)

    {

        int t = s - ((s % (base * 10)) / base) * base;

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

        {

            int tmp = t + i * base;

            if(tmp > 1000 && p[tmp] && tmp != s)

            {

                b[num++] = tmp;

            }

        }

    }

}

void calAns(int s, int e)

{

    memset(ans, -1, sizeof ans);

    if(!p[s])return;

    ans[s] = 0;

    queue<int> que;

    que.push(s);

    while(!que.empty())

    {

        s = que.front();

        que.pop();

        getSameShape(s);

        for(int j = 0; j < num; j++)

        {

            if(ans[b[j]] == -1)

            {

                ans[b[j]] = ans[s] + 1;

                if(e == b[j])return;

                que.push(b[j]);

            }

        }

    }

}

int main()

{

#ifdef LOCAL

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

#endif // LOCAL

    int n, m;

    int T;

    calPrime();

    scanf("%d",&T);

    for(int ti = 0; ti < T && scanf("%d%d", &n, &m) == 2; ti++)

    {

        calAns(n, m);

        if(ans[m] != -1)printf("%d\n",ans[m]);

        else puts("Impossible");

    }

    return 0;

}