Author: lllyouo
Date: 20250812
tag: 简单搜索
link: http://poj.org/problem?id=3126

问题描述

link

分析

略

参考代码

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int prime[10000], d[10000], vis[10000];

bool is_prime(int n) {
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

void init() {
    for (int i = 1000; i < 10000; i++) {
        if (is_prime(i)) prime[i] = 1;
    }
}

string t_string(int x) {
    string sx;
    while (x) {
        int g = x % 10;
        x /= 10;
        sx += '0' + g;
    }
    reverse(sx.begin(), sx.end());
    return sx;
}

int t_int(string sx) {
    int x = 0;
    for (int i = 0; i < sx.size(); i++) {
        x = x * 10 + sx[i] - '0';
    }

    return x;
}


void bfs(int a, int b) {
    queue<int> q;
    q.push(a);

    memset(vis, 0, sizeof vis);
    memset(d, 0x3f, sizeof d);
    d[a] = 0;
    vis[a] = 1;

    while (q.size()) {
        int x = q.front();
        q.pop();

        // 转换为字符串便于处理
        string sx = t_string(x);

        for (int i = 0; i < sx.size(); i++) {
            char c = sx[i];
            for (int num = 0; num < 10; num++) {
                if (num != c - '0') {
                    sx[i] = num + '0';
                    int xx = t_int(sx);
                    if (prime[xx] && !vis[xx]) {
                        q.push(xx);
                        d[xx] = d[x] + 1;
                        vis[xx] = 1;
                    }
                }
            }
            sx[i] = c;
        }
    }

    if (d[b] != 0x3f3f3f3f) cout << d[b] << endl;
    else cout << "Impossible" << endl;
}

int main() {
    init();
    
    int T; cin >> T;
    while (T--) {
        int a, b; cin >> a >> b;

        bfs(a, b);
    }
    
    return 0;
}