Hình vuông lớn nhất

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
TST_CSP_2022
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một bảng hình chũ nhật kích thước ~m \times n~, được chia thành các ô vuông đơn vị. Trên mỗi ô, người ta ghi số ~0~ hoặc số ~1~. Một hình vuông được gọi là đẹp nếu:

Hình vuông chiếm trọn một số ô của bảng.

  • Có các cạnh song song với hình chữ nhật ban đầu.

  • Các ô ở viền ngoài của hình vuông được chọn chỉ gồm toàn số ~1~.

Ví dụ: hình chữ nhật dưới đây có kích thước ~8 \times 10~, ta có thể tìm được một hình vuông kích thước ~6 \times 6~ mà viền ngoài của hình vuông đó chỉ gồm các số ~1~:

Yêu cầu: Tìm một hình vuông đẹp có diện tích lớn nhất (Diện tích của hình vuông là số ô của nó).

Dữ liệu:

  • Dòng đầu gồm hai số nguyên dương ~m, n\left(m \times n \leq 10^{6}\right)~

  • ~m~ dòng tiếp theo, mỗi dòng ghi ~n~ số (chỉ gồm các số ~0,1~ cách nhau bởi dấu cách) mô tả bảng.

Kết quả:

  • Ghi ra một số duy nhất là diện tích hình vuông tìm được.

Ví dụ:

Sample Input 1
4 6  
0 0 0 0 0 0 
0 1 1 0 1 0 
0 1 1 0 1 0 
0 0 0 0 0 0
Sample Output 1
4
Sample Input 2
4 6  
0 0 0 0 0 0 
0 0 1 1 1 0 
0 1 1 0 1 0 
0 0 0 0 0 0
Sample Output 2
1

Ràng buộc:

  • Subtask 1: Có ~50 \%~ số test có ~m, n \leq 300~;

  • Subtask 2: ~50\%~ số test còn lại không có ràng buộc gì thêm.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.