Bandle City (DUTPC'21)

View as PDF

Submit solution

Points: 100
Time limit: 2.0s
Memory limit: 646M

Author:
Problem type

Bandle, là đất nước của bộ tộc người lùn Yordle. Nơi đây, không những có những khung cảnh thiên nhiên tuyệt đẹp mà còn là nơi trú ngụ của hàng ngàn loài thực vật, động vật quý hiếm đáng giá hàng triệu đô. Vì thế, tại Bandle, xuất hiện rất nhiều những bọn lâm tặc từ khắp nơi trên thế giới. Teemo, là một trong những trinh sát mạnh nhất tại Bandle. Anh ấy, đã đặt những quả bom hình nấm khắp lãnh thổ Bandle để ngăn chặn việc săn bắt hái trộm của bọn lâm tặc.

Bandle được biểu thị như một ma trận ô vuông gồm \(𝑀\) hàng và \(𝑁\) cột. Mỗi ô vuông \((𝑖,𝑗)\) được mô tả trạng thái bởi ký tự \(𝑎_{𝑖,𝑗}\). Nếu \(𝑎_{𝑖,𝑗} = \)# thì ô vuông này đã được Teemo đặt bom nấm, nếu \(𝑎_{𝑖,𝑗} = \). thì ô vuông này chưa được Teemo đặt bom nấm. Từ ô vuông (\(𝑖,𝑗\)) có thể đi đến ô vuông (\(𝑖,𝑗 + 1\)) hoặc ô vuông (\(𝑖 + 1,𝑗\)).

Mặc dù đặt các bom nấm ở các ô vuông giúp ngăn chặn bọn lâm tặc, nhưng việc đặt quá nhiều bom nấm sẽ khiến cho việc đi lại giữa các khu vực sẽ trở nên khó khăn. Vì thế, Teemo sẽ xác định việc đặt bom nấm của mình có hiệu quả hay không bằng cách tính số đường đi từ ô vuông (\(1,1\)) đến ô vuông (\(𝑀, 𝑁\)) mà trong suốt quá trình đi không được đi đến ô vuông có đặt bom nấm. Nhưng vì Bandle quá rộng lớn, Teemo không thể xác định được cho nên bạn hãy giúp Teemo nhé !

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên \(𝑀, 𝑁 (2 ≤ 𝑀, 𝑁 ≤ 10^3)\).
  • \(𝑀\) dòng tiếp theo, dòng thứ \(𝑖\) gồm \(𝑁\) ký tự \(𝑎_{𝑖,1}, 𝑎_{𝑖,2}, … , 𝑎_{𝑖,𝑁}\)
  • Dữ liệu vào luôn đảm bảo tồn tại ít nhất 1 đường đi từ ô vuông (1,1) đến ô vuông (\(𝑀, 𝑁\)) mà trong suốt quá trình đi không đi đến ô vuông có đặt bom nấm.

Dữ liệu ra:

  • Số đường đi từ ô vuông (1,1) đến ô vuông (\(𝑀, 𝑁\)) mà trong suốt quá trình đi không đi đến ô vuông có đặt bom nấm. Vì đáp án có thể rất lớn nên ta chỉ lấy phần dư của đáp án khi chia cho \(10^9 + 7\).

Input

3 4
...#
.#..
....

Output

3


Nguồn: DUTPC 2021


Comments