Lưới chướng ngại vật

Buổi 22 — DP 2D & LIS Dynamic Programming
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$.

Draft saved