Cho một
bảng số A gồm M dòng, N cột, các giá trị của bảng A chỉ là 0 hoặc 1. Ta muốn cắt
bảng A thành các hình chữ nhật con sao cho các hình chữ nhật có có giá trị toàn
bằng 0 hoặc bằng 1. Mỗi lần cắt là một nhát cắt thẳng theo dòng hoặc theo cột của
một hình chữ nhật thành hai hình chữ nhật riêng biệt. Cứ tiếp tục cắt cho đến
khi hình chữ nhật có các giá trị toàn bằng 1 hoặc toàn bằng 0. Hãy tìm cách cắt
để số hình chữ nhật con nhận được, có giá trị toàn băng 0 hoặc toàn bằng 1, là
nhỏ nhất.
Ví dụ,
bảng số 5x5 sau được chia thành 8 hình chữ nhật con.
|
0
|
1
|
0
|
0
|
1
|
|
0
|
1
|
0
|
0
|
1
|
|
0
|
1
|
0
|
0
|
1
|
|
0
|
1
|
0
|
0
|
1
|
|
1
|
1
|
0
|
0
|
1
|
|
1
|
1
|
0
|
0
|
1
|
|
1
|
1
|
1
|
0
|
0
|
|
1
|
1
|
1
|
0
|
0
|
|
0
|
0
|
1
|
0
|
0
|
|
0
|
0
|
1
|
0
|
0
|
Dữ liệu vào: từ tệp
văn bản HCN2. INP
+ Dòng đầu tiên là hai số nguyên dương
M và N (M, N≤30)
+ M dòng tiếp theo mỗi dòng gồm N đô chỉ
gồm 0 hoặc 1 thể hiện bảng số A
Dữ liệu ra: Ghi
vào tệp văn bản HCN2.OUT gồm một dòng duy nhất chứa một số là số lượng hình chữ
nhật ít nhất
Ví dụ:
|
HCN2.INP
|
HCN2.OUT
|
|
5 5
0 1 0 0 1
0 1 0 0 1
1 1 0 0 1
1 1 1 0 0
0 0 1 0 0
|
8
|
