[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 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;
}