[백준 1963번] 소수 경로

소스코드

---

#include <iostream>
using namespace std;
 
int a, b, visit[10001] = { 0, };
int que[10001], head = 0, tail = 0;
int n_que[10001], n_head = 0, n_tail = 0;
 
void push(int a) {
    que[tail++] = a;
}
int pop() {
    return que[head++];
}
void n_push(int a) {
    n_que[n_tail++] = a;
}
int n_pop() {
    return n_que[n_head++];
}
 
int chk(int a) {
    for (int i = 2; i < a; i++) {
        if (a%i == 0) return 0;
    }
    return 1;
}
 
void bfs() {
    while (1) {
        int num = pop();
        int cnt = n_pop();
        if (num == b) {
            cout << cnt << '\n';
            break;
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 10; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                char tmp[4] = { (num / 1000) + '0', ((num % 1000) / 100) + '0', (((num % 1000) % 100) / 10) + '0', (((num % 1000) % 100) % 10) + '0' };
                if ((tmp[i] - '0') != j) {
                    tmp[i] = j + '0';
                    int tmp_num = (tmp[0] - '0') * 1000 + (tmp[1] - '0') * 100 + (tmp[2] - '0') * 10 + (tmp[3] - '0');
                    if (chk(tmp_num) == 1 && visit[tmp_num]==0) {
                        visit[tmp_num] = 1;
                        push(tmp_num);
                        n_push(cnt + 1);
                    }
                }
            }
        }
        if (head == tail) {
            cout << "Impossible" << '\n';
            break;
        }
    }
}
 
int main() {
    int tc;
    cin >> tc;
    while (tc>0) {
        cin >> a >> b;
        head = 0, tail = 0, n_head=0, n_tail=0;
        for (int i = 0; i < 10000; i++) {
            visit[i] = 0;
        }
        push(a);
        n_push(0);
        bfs();
        tc--;
    }
    return 0;
}