Bài 13.3. Hành Trình Của Robot - [Độ khó: Khá]

Một con robot được lập trình để khám phá một mê cung hình lưới chữ nhật có kích thước m hàng và n cột. Robot bắt đầu tại ô (0,0) (góc trên bên trái) và muốn đến ô (m-1, n-1) (góc dưới bên phải). Quy tắc duy nhất của robot là nó chỉ có thể di chuyển xuống (tăng chỉ số hàng) hoặc sang phải (tăng chỉ số cột). Bạn cần tính toán tổng số cách mà robot có thể đi để đến đích.

INPUT FORMAT

Dòng duy nhất chứa hai số nguyên m và n, lần lượt là số hàng và số cột của lưới.

• 1 <= m, n <= 10

OUTPUT FORMAT

Một số nguyên duy nhất là tổng số cách mà robot có thể đi đến đích.

Ví dụ:

Input:

3 2

Output:

3

Giải thích:

• Robot bắt đầu ở (0,0) và muốn đến (2,1).
• Các đường đi có thể là:
  1. (0,0) -> (1,0) -> (2,0) -> (2,1) (Xuống, Xuống, Phải)
  2. (0,0) -> (1,0) -> (1,1) -> (2,1) (Xuống, Phải, Xuống)
  3. (0,0) -> (0,1) -> (1,1) -> (2,1) (Phải, Xuống, Xuống)
• Tổng cộng có 3 cách.
• Phương pháp đệ quy:
  • Định nghĩa hàm countPaths(r, c): trả về số cách đi từ ô (r,c) đến đích (m-1, n-1).
  • Nếu r == m-1 và c == n-1 (đã đến đích), trả về 1.
  • Nếu r >= m hoặc c >= n (ra ngoài biên), trả về 0.
  • Ngược lại, countPaths(r, c) = countPaths(r+1, c) + countPaths(r, c+1). (Tổng số cách đi xuống và số cách đi sang phải)