1963 소수경로

1963 소수경로

1. 에라토스테네스의 체를 이용하여 1000~9999 사이의 소수를 찾는다.

2. 한 타임당 한자리를 바꿔가며 소수인경우 큐에 넣고 몇번째인지 기록한다.

3. 찾는 숫자에 도착하면 출력한다.

#include <iostream>
#include <queue>
#include <string>
#include <memory.h>
using namespace std;
 
int n, a, b;
bool primes[10001];
int visited[10001];
 
void bfs(int a,int b) {
    queue<int> q;
    q.push(a);
    visited[a] = 1;
 
    while (!q.empty()) {
        a = q.front();
        q.pop();
 
        if (a == b) {
            cout << visited[b] - 1 << endl;
            return;
        }
 
        for (int i = 0; i < 4; i++) {
            int next;
            for (int j = 0; j < 10; j++) {
                if (i == 0 && j == 0) continue;
 
                string s = to_string(a);
                s[i] = j + '0';
                next = stoi(s);
 
                if (!primes[next]) {
                    if (visited[next] == 0 || visited[next] > visited[a] + 1) {
                        visited[next] = visited[a] + 1;
                        q.push(next);
                    }
                }
            }
        }
    }
 
    cout << "Impossible" << endl;
}
 
int main() {
    
    for (int i = 2; i <= 10000; i++) {
        for (int j = 2; i*j <= 10000; j++) {
            if (primes[i*j])continue;
            primes[i*j] = true;
        }
    }
    
    cin >> n;
    while (n--) {
        cin >> a >> b;
        bfs(a, b);
        memset(visited, 0, sizeof(visited));
    }
}