[BFS] – Dhoom4 – Hackereath

Link đề bài: https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/practice-problems/algorithm/dhoom-4/description/

1. Giải thích đề BFS Dhoom hackerearth

Bạn có chìa khóa mang giá trị cho trước và một giá trị khóa cần tìm. Cho bạn danh sách các giá trị. Hỏi bạn có thể nhân lần lượt giá trị chìa khóa lần lượt với các số trong danh sách để được giá trị khóa hay không. Nếu được thì trải qua bao nhiêu giây (mỗi phép tính là 1 giây), nếu không xuất ra -1. Mỗi số trong danh danh sách có thể được nhân tiếp tục với số trước.

2. Hướng giải BFS Dhoom hackerearth

Giả sử giá trị chìa khóa là điểm đầu và giá trí khóa là điểm cuối. Mình sẽ tìm khoảng cách từ điểm đầu và điểm cuối. 2 điểm x và y được nối với nhau khi tồn tại (x*a[i])%100000=y.

a. Chuẩn bị

•   mảng dist[i] là số giây, được khởi tạo với giá trị -1 cho tất cả các phần tử đã được đi qua.
•   queue: lưu các đỉnh đã được đi qua.

Mỗi khi lấy 1 đỉnh u từ queue ra, ta sẽ tìm được n đỉnh v mới thông qua phép tính. Ta kiểm tra xem đỉnh v này đã được đi qua hay chưa. Nếu chưa ( tức dist[v] == -1) thì ta sẽ gán dist[v] = dis[u] +1 (thời gian tới v sẽ bằng thời gian tới u +1) rồi đưa đỉnh v vào queue.

b. Độ phức tạp

Độ phức tạp thuật toán giải thuật này là O(100000).

Chú ý giá trị của đỉnh v mới có thể vuợt quá miền của kiểu int.

3. Code BFS Dhoom hackerearth C++

#include<iostream>
#include<queue>
using namespace std;
#define max 100001
int a[1005], n;
int dist[max];
int BFS(long long s, int d)
{
    for (int i = 0; i < max; i++)
        dist[i] = -1;
    queue <long long> q;
    q.push(s);
    dist[s] = 0;
    while (!q.empty())
    {
        s = q.front();
        q.pop();
        if (s == d)
            break;
        for (int i = 0; i < n; i++)
        {
            long long temp = (s*a[i]);
            temp %= 100000;
            if (dist[temp] == -1)
            {
                dist[temp] = dist[s] + 1;
                q.push(temp);
            }
        }

    }
    return dist[d];
}
int main()
{
    int s, d;
    cin >> s >> d >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int  res = BFS(s, d);
    cout << res;
    return 0;
}