POJ 3126 Prime Path

Description

给出两个素数，求从这个变到那个需要几步。（变法：每步仅改变一位数）

题目链接 http://poj.org/problem?id=3126

Code

#include <set>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;

int tot;
int prime[1500];
bool vis[10500];
bool flag[10500];

struct node
{
    int val, step;
};
queue<node> q;

void get_prime()
{
    memset(vis, 1, sizeof(vis));
    tot = 0;
    vis[0] = vis[1] = 0;
    for(int i = 2; i < 10410; ++i)
    {
        if(vis[i])
            prime[++tot] = i;///下面的 j<= tot 决定了这里从1开始存
        for(int j = 1; j <= tot && prime[j] * i <= 10100; ++j)
        {
            vis[ prime[j] * i ] = 0;
            if(i % prime[j] == 0)
                break;
        }
    }
}

///起初这里写了形参队列q，结果在此函数内q不是全局内的q
void seek(node now, node nxt, int t)
{
    if(!flag[t] && vis[t])///未访问过且为素数
    {
        flag[t] = 1;
        nxt.val = t;
        nxt.step = now.step + 1;
        q.push(nxt);
    }
}

int bfs(int a, int b)
{
    while(q.size())
        q.pop();
    memset(flag, 0, sizeof(flag));
    node now, nxt;
    now.val = a;
    now.step = 0;
    flag[a] = 1;
    q.push(now);
    while(q.size())
    {
        now = q.front();
        q.pop();
        if(now.val == b)
            return now.step;
        int t;
        for(int i = 1; i <= 9; i += 2)///个位换奇数
        {
            t = now.val / 10 * 10 + i;
            seek(now, nxt, t);
        }
        for(int i = 0; i <= 9; ++i)///十位
        {
            t = (now.val / 100 * 10 + i) * 10 + now.val % 10;///此处及后面同位置易出错
            seek(now, nxt, t);
        }
        for(int i = 0; i <= 9; ++i)///百位
        {
            t = (now.val / 1000 * 10 + i) * 100 + now.val % 100;
            seek(now, nxt, t);
        }
        for(int i = 1; i <= 9; ++i)///千位
        {
            t = i * 1000 + now.val % 1000;
            seek(now, nxt, t);
        }
    }
    return inf;
}

int main()
{
    get_prime();
    int t, a, b;
    cin >> t;
    while(t--)
    {
        scanf("%d%d", &a, &b);
        int ans = bfs(a, b);
        if(ans != inf)
            cout << ans << '\n';
        else
            cout << "Impossible" << '\n';
    }
    return 0;
}