Thu Jan 19, 2012 5:22 pm
Admin Cho một bảng A gồm M dòmh , N cột gồm NxM ô vuông , mỗi ô chứa một số là 0 hoặc 1 . Người ta muốn cắt bảng A thành các hình chữ nhật con sao cho các ô trong mỗi hình chữ nhật con toàn 0 hoặc 1 . Mỗi lần cắt là một nhát cắt thẳng theo dòng hoặc 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 được mọi hình chữ nhật toàn bằng 0 hoặc 1 . Hãy tìm cách cắt để được ít hình chữ nhật nhất mà các hình chữ nhật thu được toàn bằng 0 hoặc 1 .
Dữ liệu vào : Trong file văn bản CATHINH.IN có dạng :
- Dòng đầu là hai số nguyên dương M,N (M,N<=20).
- M dòng tiếp theo , mỗi dòng N số gồm 0 hoặc 1 thể hiện bảng A .
Kết quả ra file văn bản CATHINH.OUT chỉ có một dòng chứa đúng một số là số hình chữ nhật ít nhất .
vd: CATHINH.IN
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
CATHINH.OUT
8
------------------------------------------
--------------
Dữ liệu vào : Trong file văn bản CATHINH.IN có dạng :
- Dòng đầu là hai số nguyên dương M,N (M,N<=20).
- M dòng tiếp theo , mỗi dòng N số gồm 0 hoặc 1 thể hiện bảng A .
Kết quả ra file văn bản CATHINH.OUT chỉ có một dòng chứa đúng một số là số hình chữ nhật ít nhất .
vd: CATHINH.IN
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
CATHINH.OUT
8
------------------------------------------
--------------