Khối tam hình chữ nhật
Xem PDF
Điểm:
1900
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho bảng chữ nhật \(m \cdot n\) (\(1 \le m, n \le 200\)) gồm các số \(0\) và \(1\). Ta gọi một khối tam chữ nhật là một hình gồm ba hình chữ nhật, mỗi hình chữ nhật gồm toàn số \(1\), xếp chồng lên nhau sao cho hình chữ nhật ở giữa phải rộng hơn về mỗi phía của hai hình chữ nhật trên và dưới ít nhất một ô.
Ví dụ, các hình sau đây là các khối tam chữ nhật:
1 11
111 11
1 11111
1
1
Các hình sau đây không phải là khối tam chữ nhật:
-
Trường hợp 1:
111 11111 111 111
(Ba hình chữ nhật không liên thông) -
Trường hợp 2:
1111 1111 11111 111 111
(Hình chữ nhật ở giữa không rộng hơn hình chữ nhật phía trên một ô về bên phải)
Yêu cầu: Tìm khối tam chữ nhật có diện tích lớn nhất trong bảng đã cho.
Input
- Dòng đầu tiên: hai số nguyên \(m, n\).
- \(m\) dòng tiếp theo, mỗi dòng gồm \(n\) số \(0\) hoặc \(1\) (viết liền nhau) mô tả bảng chữ nhật.
Output
- In ra diện tích của khối tam chữ nhật lớn nhất, hoặc \(0\) nếu không tìm được khối tam chữ nhật nào.
Constraints
- \(1 \le m, n \le 200\)
Example
Test 1
Input
6 8
00000110
00111000
00110100
01111001
01111110
00111010
Output
15
Bình luận