Cho một bảng kích
thước MxN, được chia thành lưới ô vuông đơn vị M dòng N cột ( 1 <= M, N
<= 1000 )
Trên các ô của bảng
ghi số 0 hoặc 1. Các dòng của bảng được đánh số 1, 2... M theo thứ tự từ trên
xuống dưới và các cột của bảng được đánh số 1, 2..., N theo thứ tự từ trái qua
phải
Yêu cầu:
Hãy tìm một hình chữ
nhật gồm các ô của bảng thoả mãn các điều kiện sau:
1 - Hình chữ nhật đó
chỉ gồm các số 1
2 - Cạnh hình chữ nhật
song song với cạnh bảng
3 - Diện tích hình chữ
nhật là lớn nhất có thể
Input
Dòng 1: Ghi hai số M,
N
M dòng tiếp theo, dòng
thứ i ghi N số mà số thứ j là số ghi trên ô (i, j) của bảng
Output
Gồm 1 dòng duy nhất
ghi diện tích của hình chữ nhật tìm được
Example
Input:
11
13
0
0 0 0 0 1 0 0 0 0 0 0 0
0
0 0 0 1 1 1 0 0 0 0 0 0
0
0 1 1 1 1 1 1 1 0 0 0 0
0
0 1 1 1 1 1 1 1 0 0 0 0
0
1 1 1 1 1 1 1 1 1 0 0 0
1
1 1 1 1 1 1 1 1 1 1 0 0
0
1 1 1 1 1 1 1 1 1 0 0 0
0
0 1 1 1 1 1 1 1 0 0 0 0
0
0 1 1 1 1 1 1 1 0 0 0 0
0
0 0 0 1 1 1 0 0 0 0 1 1
0
0 0 0 0 1 0 0 0 0 0 1 1
Output:
49
===================================
Thuật:
- H[j] là số số 1 liên tiếp ở cột thứ j (với mỗi dòng i ta lại cập nhật H[j], tăng H[j] lên 1 đơn vị nếu A[i,j]=1 ngược lại H[j]=0)
-Duyệt đến dòng thứ i, ta tìm vị trí trái nhất (L[j]) và phải nhất (R[j]) sao cho H[j] là bé nhất (ta dùng thuật toán left-right để tìm L và R ở mỗi dòng i)
- và diện tích hình chữ nhật lớn nhất tính đến dòng i sẽ là H[j] * (R[j]-L[j]+1)....tại mỗi dòng, ta lại cập nhật kết quả max...
====================================
Đây là code: QBRECT.PAS
