Bài 14.2. Đường Đi Của Robot Thám Hiểm - [Độ khó: Khá]

Bạn điều khiển một robot thám hiểm tiên tiến trong một khu vực nghiên cứu hình lưới \(R \times C\). Robot bắt đầu từ góc trên cùng bên trái \((0, 0)\) và cần di chuyển đến góc dưới cùng bên phải \((R-1, C-1)\). Robot chỉ có thể di chuyển xuống dưới hoặc sang phải. Tuy nhiên, có một số ô trong khu vực bị chặn bởi địa hình nguy hiểm hoặc chướng ngại vật và robot không thể đi vào.

Hãy viết một chương trình đệ quy để tính toán số lượng các đường đi duy nhất mà robot có thể đi từ điểm xuất phát đến điểm đích mà không đi qua các ô bị chặn.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên dương \(R\) và \(C\) (\(1 \le R, C \le 10\)). Tiếp theo là \(R\) dòng, mỗi dòng chứa \(C\) số nguyên \(0\) hoặc \(1\), mô tả bản đồ. \(0\) nghĩa là ô trống (có thể đi qua), \(1\) nghĩa là ô bị chặn. Ô xuất phát \((0, 0)\) và ô đích \((R-1, C-1)\) luôn là ô trống (\(0\)).

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng số đường đi duy nhất từ \((0,0)\) đến \((R-1, C-1)\).

Ví dụ:

Input:

3 3
0 0 0
0 1 0
0 0 0

Output:

2

Giải thích: Bản đồ \(3 \times 3\) với ô \((1,1)\) bị chặn:

(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)

Robot bắt đầu từ \((0,0)\) đến \((2,2)\). Ô \((1,1)\) là chướng ngại vật. Các đường đi hợp lệ là:

1. \((0,0) \to (0,1) \to (0,2) \to (1,2) \to (2,2)\) (R-R-D-D)
2. \((0,0) \to (1,0) \to (2,0) \to (2,1) \to (2,2)\) (D-D-R-R) Các đường đi khác đều phải đi qua ô \((1,1)\) hoặc không hợp lệ. Ví dụ, \((0,0) \to (0,1) \to (1,1)\) là không hợp lệ. Tổng cộng có 2 đường đi.