Lưới chướng ngại vật
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một bảng lưới $N \times M$ gồm các ô trống . và các ô chướng ngại vật #. Robot xuất phát từ $(1, 1)$ và muốn đi đến $(N, M)$, mỗi bước chỉ được đi sang phải hoặc xuống dưới và không được đi vào ô #. Nếu ô $(1, 1)$ hoặc $(N, M)$ là # thì không có đường đi nào.
Cấu trúc con tối ưu: nếu ô $(i, j)$ là ., $dp[i][j] = (dp[i-1][j] + dp[i][j-1]) \bmod (10^9+7)$, ngược lại $dp[i][j] = 0$.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên $N, M$.
$N$ dòng tiếp theo, mỗi dòng chứa xâu độ dài $M$ gồm . và #.
Dữ liệu ra
Một số nguyên duy nhất là số đường đi hợp lệ chia dư cho $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 3 3 ... .#. ... |
2 |
| 2 2 .# #. |
0 |
Giới hạn
$1 \le N, M \le 1000$.
Community Discussion