ELEVTRBL.cpp

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