02/10/2018, 14:31
[BFS] – SPOJ PPATH
Link: http://www.spoj.com/problems/PPATH/ Hiểu đề PPATH spoj Bạn đuợc cho 2 số nguyen tố 4 chữ số. Việc của bạn là tìm số bước ngắn nhất để biến số nguyen tố thứ 1 thành số thứ 2. Quy định rang trong mỗi bước bạn chỉ đổi được 1 trong 4 chữ số của số thứ 1 để đợợc 1 số nguyen ...
Link: http://www.spoj.com/problems/PPATH/
Hiểu đề PPATH spoj
Bạn đuợc cho 2 số nguyen tố 4 chữ số. Việc của bạn là tìm số bước ngắn nhất để biến số nguyen tố thứ 1 thành số thứ 2.
Quy định rang trong mỗi bước bạn chỉ đổi được 1 trong 4 chữ số của số thứ 1 để đợợc 1 số nguyen tố mới. Cứ thế tiếp diễn cho tới khi nào thành số thứ 2.
Ví du: 1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179. (không được chuyển chữ số đầu tiên thành chữ số 0). Nếu không tìm được thì xuất ra “Impossible”.
Gợi ý giải PPATH spoj
Sử dung BFS và Sieve of Eratosthenes. ( chi tiết mình note trong code bên dưới).
#include<iostream>
#include<queue>
#include<string.h>
#define max 10005
using namespace std;
int T, s, d, digit[4];
int prime[max], dist[max];
// mảng prime đánh dấu số nào là số nguyên tố ( snt:-1 và ko là snt: 0)
// mảng dist để lưu số bước
void sieve() // để đánh dấu các số nt trong mảng prime
{
for (int i = 2; i < 10000; i++)
{
if (prime[i])
{
int num = i;
for (int j = 2; num*j <=max; j++)
prime[num*j] =0;
}
}
}
void num_to_arr(int value[], int num)// chuyển 4 chữ số vào mảng
{
for (int i = 3; i >= 0; i--)
{
value[i] = num % 10;
num /= 10;
}
}
int arr_to_num(int value[])// từ mảng ra số
{
int res = 1000 * value[0] + 100 * value[1] + 10 * value[2] + value[3];
return res;
}
int main()
{
memset(prime, -1, sizeof(prime));
sieve();
cin >> T;//test case
while (T--)
{
cin >> s >> d;
memset(dist, -1, sizeof(dist));
queue<int> q;
q.push(s);
dist[s] = 0;
while (!q.empty())
{
s = q.front();
q.pop();
for (int i = 0; i <= 3; i++)// cố định 3 chữ số rồi chạy 3 chữ số còn lại để xét
{
num_to_arr(digit, s);
for (int j = 0; j <= 9; j++)
{
digit[i] = j;
int temp = arr_to_num(digit);
if (prime[temp] == -1 && temp > 1000 && dist[temp] == -1)// nếu số đó chưa đc xét và là snt thì đánh dấu số bước.
{
dist[temp] = dist[s] + 1;
q.push(temp);
}
}
}
}
if (dist[d] == -1)
cout << "Impossible" << endl;
else
cout << dist[d] << endl;
}
return 0;
}
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 | #include<iostream> #include<queue> #include<string.h> #define max 10005 using namespace std; int T, s, d, digit[4]; int prime[max], dist[max]; // mảng prime đánh dấu số nào là số nguyên tố ( snt:-1 và ko là snt: 0) // mảng dist để lưu số bước void sieve() // để đánh dấu các số nt trong mảng prime { for (int i = 2; i < 10000; i++) { if (prime[i]) { int num = i; for (int j = 2; num*j <=max; j++) prime[num*j] =0; } } } void num_to_arr(int value[], int num)// chuyển 4 chữ số vào mảng { for (int i = 3; i >= 0; i--) { value[i] = num % 10; num /= 10; } } int arr_to_num(int value[])// từ mảng ra số { int res = 1000 * value[0] + 100 * value[1] + 10 * value[2] + value[3]; return res; } int main() { memset(prime, -1, sizeof(prime)); sieve(); cin >> T;//test case while (T--) { cin >> s >> d; memset(dist, -1, sizeof(dist)); queue<int> q; q.push(s); dist[s] = 0; while (!q.empty()) { s = q.front(); q.pop(); for (int i = 0; i <= 3; i++)// cố định 3 chữ số rồi chạy 3 chữ số còn lại để xét { num_to_arr(digit, s); for (int j = 0; j <= 9; j++) { digit[i] = j; int temp = arr_to_num(digit); if (prime[temp] == -1 && temp > 1000 && dist[temp] == -1)// nếu số đó chưa đc xét và là snt thì đánh dấu số bước. { dist[temp] = dist[s] + 1; q.push(temp); } } } } if (dist[d] == -1) cout << "Impossible" << endl; else cout << dist[d] << endl; } return 0; } |
