3126 Prime Path

问题来自 poj 3126 Prime Path

---

一道典型的BFS搜索题。先求出10000到1000以内的所有素数，接着就是bfs了。

---

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int N = 10000;
int s, e;
bool primes[N];
bool used[N];

void init()
{
    memset(primes, true, sizeof(primes));
    primes[0] = primes[1] = false;
    int bound = sqrt(N);
    for(int i = 2; i <= bound; ++i)
        if(primes[i])
        {
            int j = i*i;
            while(j < N)
            {
                primes[j] = false;
                j += i;
            }
        }
}

int setDigit(int num, int power, int digit)
{
    int left = num/(power*10);
    int right = num%power;
    return left*power*10+digit*power+right;
}

int bfs()
{
    memset(used, false, sizeof(used));
    queue tool;
    tool.push(s);
    used[s] = true;
    int step = 0;
    while(!tool.empty())
    {
        int size = tool.size();
        while(size--)
        {   
            int t = tool.front(); tool.pop();
            int power = 1;
            for(int i = 0; i < 4; ++i)
            {
                for(int j = 0; j < 10; ++j)
                {
                    int tmp = setDigit(t, power, j);
                    if(tmp == t || t < 1000)
                        continue;
                    if(primes[tmp] && !used[tmp])
                    {
                        used[tmp] = true;
                        tool.push(tmp);
                    }
                    if(tmp == e)
                        return step+1;
                }
                power *= 10;
            }
        }
        ++step;
    }
    return step;
}

int solve()
{
    scanf("%d%d", &s, &e);
    if(s == e) return 0;
    return bfs();
}

int main()
{
    init();
    int tcase;
    scanf("%d", &tcase);
    while(tcase--)
        printf("%d\n", solve());
    return 0;
}