Đếm đường đi trên mê cung lưới
Points
46
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Đề 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$.
Community Discussion