Bài 18.3. Đường Đi Ma Thuật Trong Lưới Cây Cối - Độ khó: Khá

Bạn là một nhà thám hiểm đang lạc trong một khu rừng ma thuật được sắp xếp theo dạng lưới. Một số ô trong lưới là cây cối bình thường (có thể đi qua), nhưng một số ô lại chứa "cây cối bị nguyền rủa" (không thể đi qua). Nhiệm vụ của bạn là tìm tất cả các con đường duy nhất từ điểm xuất phát (góc trên cùng bên trái) đến điểm đích (góc dưới cùng bên phải) của khu rừng. Bạn chỉ có thể di chuyển xuống dưới hoặc sang phải.

Mô tả bài tập: Cho một lưới M x N với các giá trị 0 (ô trống, có thể đi qua) và 1 (cây cối bị nguyền rủa, không thể đi qua). Bạn đang ở ô (0,0) và muốn đến ô (M-1, N-1). Hãy tính số lượng con đường duy nhất từ (0,0) đến (M-1, N-1) bằng cách chỉ di chuyển xuống dưới hoặc sang phải.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên M và N (1 <= M, N <= 100), là kích thước của lưới. M dòng tiếp theo, mỗi dòng chứa N số nguyên (0 hoặc 1) mô tả lưới. grid[i][j] = 1 nếu ô đó là vật cản, 0 nếu là ô trống. Đảm bảo rằng ô (0,0) và ô (M-1, N-1) luôn là ô trống (có giá trị 0).

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng số con đường duy nhất tìm được.

Ví dụ:

Input:

3 3
0 0 0
0 1 0
0 0 0

Output:

2

Giải thích: Lưới có dạng:

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

Trong đó (1,1) là vật cản. Các con đường có thể là:

1. (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)
2. (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2)

Input:

2 2
0 1
0 0

Output:

1

Giải thích: Lưới:

(0,0) (0,1) (vật cản)
(1,0) (1,1)

Chỉ có một con đường: (0,0) -> (1,0) -> (1,1)