SPOJ.COM – Thuật toán bài NUMPATH - Gutibazi
Đề bài:
Xunayed rất là mạnh mẽ. Anh ấy đã phát hiện ra rằng bạn của anh ta là Nurulla - người giống với anh trai mình, đã làm một việc không có khí phách với anh ta. Xunayed có thể tha thứ bất cứ điều gì, nhưng việc làm điều không có khí phách với anh ta là không thể tha thứ được. Nhưng để dạy cho Nurulla một bài học, Xunayed đầu tiên phải đến chỗ Nurulla qua một vài đường. Vì vậy, vấn đề xảy ra ở đây là những con đường thuộc về một người rất quyền lực tên là Rizvi và tất cả mọi người phải xin phép người này để có thể đi qua được những con đường. Rizvi sẽ cho phép Xunayed nếu như Xunayed giải quyết được một điều bí ẩn.
Đường đi là một vài lưới 2 chiều. Xunayed hiện tại đang đứng ở vị trí ô trên cùng bên trái (1, 1) - là điểm bắt đầu. Nurulla đang đứng ở ô dưới cùng bên phải - là điểm đích. Biết Xunayed chỉ có thể đi xuống, hay sang phải. Hỏi có bao nhiêu đường mà Xunayed có thể tiếp cận Nurulla.
Hãy giải quyết bài toán này để giúp Xunayed đòi lại quyền công bằng.
Đầu vào:
Bắt đầu với số nguyên T (T <= 50) là số lượng test case. Mỗi test case sẽ gồm một dòng chứa 2 số nguyên R, C (1 <= R, C <= 7), trong đó, R là số lượng hàng, C là số lượng cột.
Đầu ra:
Với mỗi test case, in ra số nguyên là số đường mà Xunayed có thể tiếp cận Nurulla.
Ví dụ:
Đầu vào:
2
1 1
2 2
Đầu ra:
1
2
Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/NUMPATH/
Phân tích:
- Bài toán này tôi sẽ dùng thuật toán vét cạn Brute force, được triển khai bằng đệ quy để duyệt hết tất cả các trường hợp. Điểm bắt đầu là (0, 0) và điểm đích là (R-1,C-1). Tại mỗi điểm chỉ có thể đi xuống, hoặc sang bên phải.
Lời giải:
(Các 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 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; | |
| int R, C; | |
| int Matrix[7][7]; | |
| int Num_path; | |
| void Visit(int row, int col) | |
| { | |
| // Nếu đi được đến điểm đích thì tăng số đường lên 1 | |
| if(row == R-1 && col == C-1) Num_path++; | |
| else | |
| { | |
| // Nếu sang bên phải | |
| if(row + 1 <= R-1) Visit(row + 1,col); | |
| // Nếu đi xuống dưới | |
| if(col + 1 <= C-1) Visit(row,col + 1); | |
| } | |
| } | |
| int main() | |
| { | |
| int Testcase; | |
| cin >> Testcase; | |
| for(int tc = 0; tc < Testcase; tc++) | |
| { | |
| cin >> R >> C; | |
| Num_path = 0; | |
| Visit(0, 0); | |
| cout << Num_path << endl; | |
| } | |
| return 0; | |
| } |
Code by Phạm Văn Lâm.