Hình chữ nhật lớn nhất

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1400 (p) Thời gian: 0.5s Bộ nhớ: 1G Input: MAXRECT.INP Output: MAXRECT.OUT

Cho một bảng kích thước \(m \times n\) được chia thành lưới ô vuông đơn vị. Các hàng của bảng được đánh số từ \(1\) tới \(m\) từ trên xuống và các cột của bảng được đánh số từ \(1\) tới \(n\) từ trái qua phải. Ô nằm trên hàng \(i\) và cột \(j\) của bảng gọi là ô \((i,j)\). Mỗi ô được tô bởi một trong hai màu: Đen (B) hoặc Trắng (W).

Hãy tìm một hình chữ nhật có diện tích lớn nhất thỏa mãn các điều kiện sau:

  • Cạnh hình chữ nhật song song với cạnh bảng,
  • Hình chữ nhật chiếm trọn một số ô của bảng và chỉ gồm các ô trắng.

Input

Vào từ file văn bản MAXRECT.INP

  • Dòng 1 chứa hai số nguyên dương \(m,n \leq 1000\) cách nhau bởi dấu cách.
  • \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) ký tự liền nhau, ký tự thứ \(j\)B nếu ô \((i,j)\) là ô đen, là W nếu ô \((i,j)\) là ô trắng.

Output

Ghi ra file văn bản MAXRECT.OUT một số nguyên duy nhất là diện tích (số ô nằm trong) hình chữ nhật tìm được (ghi số \(0\) nếu bảng đã cho không có ô trắng).

Example

Test 1

MAXRECT.INP
4 6
BBWWBB
BWWWWB
BWWWWB
BBWBBB
MAXRECT.OUT
8

Nguồn: Thầy Lê Minh Hoàng

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.