CTDL> bài 26.A18 CTDL> bài Đếm số đường đi trong mê cung.
Đếm số đường đi trong mê cung.
Cho mê cung được mô tả bởi một ma trận kí tự gồm N hàng và N cột. Mỗi ô trên ma trận chứa kí tự '.' tương ứng với đường đi và dấu * tương ứng với bẫy. Một con chuột muốn đi từ ô (1, 1) tới ô (N, N) và chỉ được di chuyển khi một ô nào đó là đường đi và nó được di chuyển sang phải hoặc xuống dưới. Hãy đếm số cách con chuột có thể di chuyển tới đích. Vì kết quả quá lớn nên hãy lấy dư với 10^9 + 7
Input Format
Dòng đầu tiên là N; N dòng tiếp theo mỗi dòng là N kí tự.(1<=N<=1000)
Constraints
.
Output Format
Số đường đi tối đa.
Ví dụ:
Dữ liệu vào
5
.....
.*..*
..*..
*..*.
.....
Dữ liệu ra
4
Comments