Hình chữ nhật lớn nhất
Xem PDF
Đ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\) là
Bnếu ô \((i,j)\) là ô đen, làWnế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