trang chủ / bài tập / fortmoo16

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

Đề bài

Mô tả

Cho một lưới ô vuông kích thước N×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 r1rr2, c1cc2 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 r1, hàng r2, cột c1, hoặc cột c2.

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 r1..r2×c1..c2, 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×1) hoặc một hàng/cột đơn (1×k hay k×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 NM.
  • 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

  • 1N,M200

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×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×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.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0