백준 #1963 : 소수경로

https://www.acmicpc.net/problem/1963

1963번: 소수 경로

 

 

숫자의 각 자리수 접근법:

for(int i = 0; i<4; i++){
    string str = to_string(cur);
    for(int j = 0; j<10; j++){
        str[i] = j + '0';
        int next = stoi(str);

숫자를 string으로 변환후 각 string의 자리를 숫자로 바꾸면 편하다

 

/**
 * @name: 소수경로
 * @link: https://www.acmicpc.net/problem/1963
 * @date 2020-04-30
 * @author sunmon
 * TIP: 에라토스테네스의 체 이용
**/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
bool prime[10000];
int dist[10000];
using namespace std;

void setup(){
    memset(prime, true, sizeof(prime));
    for(int i = 2; i<100; i++){
        int sum = i+i;
        while(sum < 10000){
            prime[sum] = false;
            sum+= i;
        }
    }
}


int solve(int a, int b){
    queue<int> q;
    q.push(a);
    dist[a] = 0;

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        if(cur == b) return dist[cur];

        for(int i = 0; i<4; i++){
            string str = to_string(cur);
            for(int j = 0; j<10; j++){
                str[i] = j + '0';
                int next = stoi(str);

                if(!prime[next]) continue;
                if(next < 1000 || next >= 10000) continue;
                if(dist[next] != -1) continue;
                q.push(next);
                dist[next] = dist[cur] + 1;
            }
        }
    }
    return dist[b];
}

int main(){
    setup();
    int t;
    cin >> t;
    while(t--){
        memset(dist, -1, sizeof(dist));
        int a, b;
        cin >> a >> b;
        cout << solve(a,b) << endl;
    }
}