Hình số tám

Đ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 kích thước $N \times N$ . Mỗi ô là ký tự . (hoàn hảo) hoặc * (có khuyết điểm).

Một hình số tám gồm hai hình chữ nhật (trên và dưới) thỏa mãn:

Cả hai hình chữ nhật đều có ít nhất một ô bên trong (interior).
Cạnh dưới của hình chữ nhật trên là một phần con (subset) của cạnh trên của hình chữ nhật dưới. Nghĩa là hai hình chữ nhật chia sẻ một đường ngang, và hình chữ nhật dưới có thể rộng hơn hình chữ nhật trên.
Tất cả các ô trên viền (biên) của cả hai hình chữ nhật phải là ô hoàn hảo (.).

Điểm thẩm mỹ của hình số tám bằng tích diện tích phần bên trong của hai hình chữ nhật.

Tìm điểm thẩm mỹ cao nhất có thể. Nếu không tồn tại hình số tám hợp lệ, in ra $- 1$ .

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ .
$N$ dòng tiếp theo, mỗi dòng chứa $N$ ký tự (. hoặc *).

Dữ liệu ra

In ra một số nguyên duy nhất: điểm thẩm mỹ cao nhất, hoặc $- 1$ .

Ràng buộc

$5 \leq N \leq 300$

Ví dụ

Input	Output	Giải thích
5 ..... ..... ..... ..... .....	9	Hình số tám tối ưu: hai hình chữ nhật $5 \times 3$ xếp chồng. Mỗi hình có diện tích bên trong $3 \times 1 = 3$ . Điểm thẩm mỹ $= 3 \times 3 = 9$ .
15 ............... ............... ...******..... ............ ............ .............. ......*.... ............... .......... ......*..... ............ ............... ............. .............. ...............	3888	Tồn tại hình số tám với tích diện tích bên trong bằng $3888$ .

Ghi chú

Viền (biên) của hình chữ nhật bao gồm tất cả các ô ở hàng đầu, hàng cuối, cột đầu, và cột cuối của hình chữ nhật đó. Phần bên trong (interior) là các ô không nằm trên viền.

Bình luận

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