CTDL&GT bài 26.A18 CTDL&GT bài Đếm số đường đi trong mê cung.


LÀM BÀI

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Đế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

There are no comments at the moment.

Zalo