Đếm đường đi trên lưới có vật cản
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một lưới kích thước $N \times M$ gồm các ô trống . và các ô vật cản #. Bạn bắt đầu tại ô $(1, 1)$ và muốn đi đến ô $(N, M)$. Mỗi bước chỉ được đi sang phải hoặc đi xuống dưới và không được bước vào ô vật cản.
Hãy đếm số đường đi khác nhau từ $(1, 1)$ đến $(N, M)$ theo modulo $10^9 + 7$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N, M \le 1000$).
- $N$ dòng tiếp theo, mỗi dòng gồm $M$ ký tự
.hoặc#.
Dữ liệu ra
Số nguyên duy nhất là số đường đi hợp lệ modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
3 3<br>...<br>.#.<br>... |
2 |
Giới hạn
- $1 \le N, M \le 1000$
Community Discussion