Bài 3. ĐƯỜNG ĐI (5,0 điểm; Đề HSG9 tỉnh Gia Lai 2025-2026)

Cho lưới ô vuông hình chữ nhật m × n, mỗi ô chỉ chứa một giá trị 0 hoặc 1. Có bao nhiêu cách khác nhau để đi từ ô (1,1) đến ô (m, n). Biết rằng mỗi lần đi chỉ được đi xuống dưới (từ ô (i, j) đến ô (i+1, j)) hoặc sang phải (từ ô (i, j) đến ô (i, j+1)) và không được đi vào ô có giá trị 1 (kể cả ô xuất phát (1,1)).

Dữ liệu vào: Từ tệp BAI3.INP theo định dạng:

• Dòng đầu là 2 số nguyên dương m và n (m, n ≤ 50).
• m dòng tiếp theo, mỗi dòng gồm n số (0 hoặc 1) viết liền nhau của một hàng trong bảng.

Dữ liệu ra: Ghi ra tệp BAI3.OUT số đường đi khác nhau tìm được.

Ví dụ:

Ràng buộc

• Subtask 1: Có 60% số test n, m ≤ 30.
• Subtask 2: Có 40% số test n, m ≤ 50.