Pháo Đài Lớn Nhất

Đ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 M$ . Mỗi ô hoặc trống (ký hiệu .) hoặc là đầm lầy (ký hiệu X). Bạn cần xây dựng một pháo đài hình chữ nhật trên lưới này.

Pháo đài được xác định bởi một hình chữ nhật con $r_{1} \leq r \leq r_{2}$ , $c_{1} \leq c \leq c_{2}$ của lưới. Pháo đài chỉ sử dụng khung viền (border) dày 1 ô của hình chữ nhật — tức là tất cả các ô nằm trên hàng $r_{1}$ , hàng $r_{2}$ , cột $c_{1}$ , hoặc cột $c_{2}$ .

Pháo đài hợp lệ khi toàn bộ khung viền không chứa ô đầm lầy nào.

Hãy tìm diện tích lớn nhất (số ô trong hình chữ nhật $r_{1} . . r_{2} \times c_{1} . . c_{2}$ , kể cả phần bên trong) của một pháo đài hợp lệ. Nếu không có pháo đài nào hợp lệ, in ra $0$ .

Lưu ý: Một ô đơn (hình chữ nhật $1 \times 1$ ) hoặc một hàng/cột đơn ( $1 \times k$ hay $k \times 1$ ) cũng là pháo đài hợp lệ nếu toàn bộ các ô đó trống.

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $M$ .
$N$ dòng tiếp theo: mỗi dòng gồm $M$ ký tự . hoặc X mô tả lưới.

Dữ liệu ra

In ra một số nguyên duy nhất — diện tích lớn nhất của pháo đài hợp lệ.

Ràng buộc

$1 \leq N, M \leq 200$

Ví dụ

Input	Output	Giải thích
5 6 ...... ..X..X X..X.. ...... ..X...	16	Hình chữ nhật từ hàng 1..4, cột 2..5 có kích thước $4 \times 4 = 16$ . Hàng 1 và hàng 4 (cột 2..5) đều trống; cột 2 và cột 5 (hàng 1..4) đều trống — khung viền không có ô đầm lầy.
2 2 .. ..	4	Toàn bộ lưới $2 \times 2$ trống, diện tích tối đa là $4$ .

Bình luận

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