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
Các 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:
(Các bạn nên tự mình nghĩ ra thuật toán và lập trình trước khi tham khảo code của tôi 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 tôi 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 các 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; | |
| } |
Code by Phạm Văn Lâm.