Tranh Hang Động

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một lưới ô vuông $N \times M$ , trong đó mỗi ô có thể là đá (#) hoặc trống (.). Toàn bộ viền ngoài của lưới đều là đá. Một bức tranh hợp lệ là cách tô màu một số ô trống thành nước, sao cho thỏa mãn điều kiện sau:

Nếu ô $a$ là nước, và tồn tại đường đi từ $a$ đến $b$ chỉ qua các ô trống hoặc nước không cao hơn $a$ (liền kề theo cạnh), thì $b$ cũng phải là nước.

(Ô ở hàng $i$ có "độ cao" bằng $N - i$ , tức là hàng dưới cùng là thấp nhất.)

Đếm số bức tranh hợp lệ modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu: $N$ và $M$ ( $1 \leq N, M \leq 1000$ ).
$N$ dòng tiếp theo: mỗi dòng gồm $M$ ký tự . hoặc #.

Dữ liệu ra

Một số nguyên duy nhất — số bức tranh hợp lệ modulo $10^{9} + 7$ .

Ví dụ

Input	Output	Giải thích
4 9 ######### #...#...# #.#...#.# #########	9	Có 2 vùng hang động độc lập, mỗi vùng có 3 cách tô, tổng $3 \times 3 = 9$ .

Bình luận

Không có bình luận tại thời điểm này.