Đếm đường đi trên mê cung lưới

Buổi 05 — Hàm & Đệ quy Mathematics
Points
46
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Submissions
Đề bài

Cho một lưới kích thước $N \times M$ gồm các ô trống . và ô vật cản #. Xuất phát từ ô $(1, 1)$, mỗi bước bạn chỉ được đi sang phải hoặc đi xuống dưới một ô, và không được đi vào ô #. Hãy dùng đệ quy có nhớ để đếm số đường đi khác nhau đến ô $(N, M)$ theo modulo $10^9 + 7$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $M$. $N$ dòng tiếp theo mỗi dòng là một xâu độ dài $M$ gồm . và #.

Dữ liệu ra

Một số nguyên duy nhất là số đường đi modulo $10^9 + 7$.

Ví dụ
Input Output
3 3\n...\n.#.\n... 2
2 2\n.#\n#. 0
Giới hạn

$1 \le N, M \le 500$.

Draft saved