Khối tam hình chữ 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: 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\)\(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

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

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