백준알고리즘

소수 경로

먼지의삶 2019. 10. 6. 02:49

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<queue>
#include<cstring>
 
using namespace std;
 
int tc;
int a, b;
bool d[10000];
int dist[10000];
 
int origin(int a, int b, int c, int d) {
    return (a * 1000 + b * 100 + c * 10 + d);
}
 
bool prime(int a) {
    for (int i = 2; i * i <= a; i++) {
        if (a % i == 0)
            return false;
    }
    return true;
}
 
int bfs(int a, int b) {
    queue<int> q;
    q.push(a);
    d[a] = true;
 
    while (!q.empty()) {
        a = q.front();
        if (a == b) {
            return dist[a];
        }
        int one = a % 10; int two = (a / 10)% 10;
        int three = (a / 100) % 10;
        int four = (a / 1000) % 10;
        q.pop();
        for (int i = 0; i < 10; i++) {
                int s = origin(four, three, two, i);
                if (!d[s] && prime(s)) {
                    d[s] = true;
                    dist[s] = dist[a] + 1;
                    q.push(s);
                }
        }
        for (int i = 0; i < 10; i++) {
                int s = origin(four, three, i, one);
                if (!d[s] && prime(s)) {
                    d[s] = true;
                    dist[s] = dist[a] + 1;
                    q.push(s);
                }
        }
        for (int i = 0; i < 10; i++) {
                int s = origin(four,i, two, one);
                if (!d[s] && prime(s)) {
                    d[s] = true;
                    dist[s] = dist[a] + 1;
                    q.push(s);
                }
        }
        for (int i = 1; i < 10; i++) {
                int s = origin(i,three, two, one);
                if (!d[s] && prime(s)) {
                    d[s] = true;
                    dist[s] = dist[a] + 1;
                    q.push(s);
                }
        }
    }
    return -1;
 
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> tc;
    for (int t = 0; t < tc; t++) {
        cin >> a >> b;
        int ans = bfs(a, b);
        if (ans == -1)
            cout << "Impossible" << '\n';
        else
            cout << ans << '\n';
        memset(d, false, sizeof(d));
        memset(dist, false, sizeof(dist));
    }
 
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
  

그냥 딱 예전에 풀어봤을법한 문제가아닐까 싶다

BFS개념자체는 그대로 적용되지만, 소수구할때 저렇게나마 줄이지않으면 분명히 시간초과가날것같은 문제다