Atcoder Educational DP Contest H - Grid 1
View as PDF
Cho lưới hình chữ nhật gồm ~H~ hàng và ~W~ cột. Ô ~(i,j)~ được định nghĩa là ô vuông giao giữa hàng thứ ~i~ (từ trên xuống dưới) và cột thứ ~j~ (từ trái qua phải).
Mỗi ô vuông ~(i,j)~ ~(1 \leq i \leq H, 1 \leq j \leq W)~ được biểu diễn bởi 1 kí tự ~a_{i,j}~. Nếu ~a_{i,j}~ là ., ô ~(i,j)~ là một ô rỗng. Ngược lại, nếu ~a_{i,j}~ là #, ô ~(i,j)~ chứa vật cản.
Taro sẽ bắt đầu từ ô ~(1,1)~ đi tới ô ~(H,W)~. Mỗi bước đi, Taro chỉ có thể có di chuyển từ ô hiện tại tới ô liền kề bên phải hoặc ô liền kề phía dưới, với điều kiện ô đó phải là một ô rỗng.
Xác định số đường đi mà Taro có thể đi từ ô ~(1,1)~ tới ô ~(H,W)~. Đáp án có thể rất lớn, vì vậy chỉ in ra phần dư của nó khi chia cho ~10^9 + 7~.
Input
Dòng đầu tiên chứa hai số nguyên ~H~ và ~W~, lần lượt là số hàng và số cột của lưới. ~(2 \leq H, W \leq 1000)~
Dòng thứ ~i~ trong số ~H~ dòng tiếp theo chứa ~W~ kí tự, lần lượt là ~a_{i,1}....a_{i,W}~.
Đảm bảo rằng hai ô ~(1,1)~ và ~(H,W)~ luôn là ô rỗng.
Output
Gồm một số nguyên duy nhất là phần dư của số đường đi thỏa mãn mà Taro có thể đi khi chia cho ~10^9 + 7~.
Sample 1
Input
3 4
...#
.#..
....
Output
3
Giải thích
Có ~3~ cách đi như hình sau:
Sample 2
Input
5 2
..
#.
..
.#
..
Output
0
Giải thích
Không có bất cứ cách đi nào thỏa mãn.
Sample 3
Input
5 5
..#..
.....
#...#
.....
..#..
Output
24
Sample 4
Input
20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
Output
345263555
Comments
ai vote up mik vs mik cho Yuki Suo
This comment is hidden due to too much negative feedback. Show it anyway.