SPOJ.COM - Thuật toán bài ELEVTRBL - Elevator Trouble

Đề bài:

Bạn đang trên đường đi đến buổi phỏng vấn cho vị trí lập trình viên. Và thực tế, bạn đã bị muộn. Buổi phỏng vấn được diễn ra ở một tòa nhà rất cao và bạn đang ở tầng s, nơi mà bạn gặp một chiếc thang máy. Biết rằng, thang máy sẽ có 2 nút bấm được đánh dấu là "UP u" và "DOWN d". Bạn kết luận là nút UP sẽ đưa thang máy lên trên u tầng nếu như có đủ số tầng phía trên, và nút DOWN sẽ đưa thang máy đi xuống d tầng nếu có đủ số tầng phía dưới. Trường hợp không có đủ số tầng thì thang máy sẽ không lên hoặc không xuống. Biết rằng buổi phỏng vấn được diễn ra tại tầng g, và tòa nhà này có f tầng. Bạn hãy nghĩ ra thuật toán và lập trình để tính ra số lần phải bấm nút là ít nhất để đi được đến đúng vị trí tầng phỏng vấn. Nếu không thể đển được đúng tầng thì in ra dòng chữ "use the stairs".

Cho số f, s, g, u và d (lần lượt là số lượng tầng tại tòa nhà, tầng bắt đầu, tầng đích, số tầng lên và số tầng xuống). Tìm ra số lần phải bấm nút ít nhất để đi được từ tầng s đến tầng g và in ra số đó hoặc trong trường hợp không thể đi được thì in ra "use the stairs".

Đầu vào

Đầu vào bao gồm một dòng, chứa các số f s g u d, trong đó 1 <= s, g <= f <= 1000000 và 0 <= u, d <= 1000000. Các tầng được đánh số từ 1. Ví dụ có 10 tầng thì các tầng sẽ là 1, 2, 3,…,10.

Đầu ra

In ra số lần phải bấm nút là ít nhất để đi được từ tầng s đến tầng g. Trường hợp không thể đi được thì in ra dòng chữ "use the stairs".

Ví dụ 1:

Đầu vào:

10 1 10 2 1 

Đầu ra:

6

Ví dụ 2:

Đầu vào:

100 2 1 1 0 

Đầu ra:

use the stairs 

Bạn có thể tham khảo link gốc đề bài tiếng anh và submit code tại đây: http://www.spoj.com/problems/ELEVTRBL/

Phân tích

Bài toán này ta khó có thể sử dụng thuật toán vét cạn, hay quay lui có điều kiện vì số lượng tầng ở đây có thể lên đến N = 1000000. Như vậy, chắc chắn sẽ bị time limit.

Ta sẽ sử dụng thuật toán tìm kiếm theo chiều rộng - BFS. Tư tưởng ở đây là ta sẽ đi tính số lần bấm nút nhỏ nhất để đi được hết tất cả các tầng.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include <iostream>
using namespace std;

const int MAX = 1000005;

int f, s, g, u, d;          // Chứa những thông tin với tên trùng với đầu bài cho
int Number[MAX];            // Lưu số lần bấm nút nhỏ nhất để đi đến mỗi tầng

// mảng đóng vai trò là hàng đợi - queue,
// để triển khai thuật toán tìm kiếm theo chiều rộng.
int queue[MAX];
int fr, re, leng;

void Enqueue(int id)
{
    queue[re] = id;
    re = (re + 1) % MAX;
    leng++;
}

int Dequeue()
{
    int t = queue[fr];
    fr = (fr + 1) % MAX;
    leng--;
    return t;
}

void BFS(int start)
{
    fr = re = leng = 0;

    // Cho tầng đầu tiên vào hàng đợi, giá trị số lần bấm nút sẽ là 0
    Number[start] = 0;
    Enqueue(start);

    while(leng > 0)
    {
        // Lần lượt dequeue ra và cập nhật trạng thái mới
        int tmp = Dequeue();

        // Nếu gặp phải tầng đích thì dừng luôn
        if(tmp == g) break;

        // Nếu bấm lên trên
        if (tmp + u <= f && Number[tmp + u] == -1)
        {
            Number[tmp + u] = Number[tmp] + 1;
            Enqueue(tmp + u);
        }

        // Nếu bấm xuống dưới
        if (tmp - d >= 1 && Number[tmp - d] == -1)
        {
            Number[tmp - d] = Number[tmp] + 1;
            Enqueue(tmp - d);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);

    // comment dòng này trước khi submit
    freopen("input.txt","r",stdin);

    // nhập thông tin đầu vào, tên biến giống với đề bài cho
    cin >> f >> s >> g >> u >> d;

    // khởi tạo
    for(int i = 1; i <= f; i++)
        Number[i] = -1;

    BFS(s);

    // Nếu Number[g] == -1 nghĩa là không thể đi được tới tầng g
    if(Number[g] == -1) cout << "use the stairs" << endl;
    else cout << Number[g] << endl;

    return 0;
}