Tập Con Cân Bằng

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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 N$ , mỗi ô được đánh dấu là có cỏ ('G') hoặc không có cỏ ('.').

Một tập con không rỗng các ô được gọi là cân bằng nếu thỏa mãn tất cả các điều kiện sau:

Tất cả các ô trong tập con đều có cỏ.
Tập con liên thông 4 chiều: tồn tại đường đi giữa bất kỳ hai ô nào trong tập con, mỗi bước di chuyển đến ô kề cạnh (trên, dưới, trái, phải).
Nếu các ô $(x_{1}, y)$ và $(x_{2}, y)$ (với $x_{1} \leq x_{2}$ ) thuộc tập con, thì mọi ô $(x, y)$ với $x_{1} \leq x \leq x_{2}$ cũng thuộc tập con.
Nếu các ô $(x, y_{1})$ và $(x, y_{2})$ (với $y_{1} \leq y_{2}$ ) thuộc tập con, thì mọi ô $(x, y)$ với $y_{1} \leq y \leq y_{2}$ cũng thuộc tập con.

Đếm số tập con cân bằng theo modulo $10^{9} + 7$ .

Dòng đầu tiên chứa số nguyên $N$ .

$N$ dòng tiếp theo, mỗi dòng là một chuỗi $N$ ký tự. Ký tự thứ $j$ của dòng thứ $i$ (từ trên xuống) bằng 'G' nếu ô $(i, j)$ có cỏ, hoặc '.' nếu không.

Một số nguyên duy nhất: số tập con cân bằng theo modulo $10^{9} + 7$ .

Input	Output	Giải thích
2 GG GG	13	Tất cả 13 tập con liên thông 4 chiều đều thỏa mãn điều kiện cân bằng.
4 GGGG GGGG GG.G GGGG	642	Ví dụ tập con không thỏa mãn điều kiện 3: các ô {(1,1),(1,2),(2,2),(3,1),(3,2)} tạo thành hình liên thông nhưng trong cột 1 có ô (1,1) và (3,1) mà thiếu (2,1).

Bình luận

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