THỰC HÀNH

(Đề đề xuất THHV 2016 của THPT CHUYÊN HÙNG VƯƠNG – PHÚ THỌ)

Cho bảng màu kích thước m × n ô (m dòng, n cột). Mỗi ô chỉ sơn màu đen hoặc trắng. Tìm cách sơn lại ít ô nhất để được bảng màu đẹp.

Bảng màu đẹp thỏa mãn điều kiện sau:

• Mỗi cột của bảng đều được sơn cùng màu
• Chiều rộng của mỗi đường thẳng đứng đơn sắc ít nhất là x và nhiều nhất là y. Nói cách khác, nếu nhóm tất cả các cột lân cận cùng màu, kích thước của mỗi nhóm không được bé hơn x và không được lớn hơn y.

Dữ liệu vào:

• Dòng đầu chứa bốn số nguyên dương m, n, x, y, hai số liên tiếp được ghi cách nhau một dấu cách.
• m dòng tiếp theo, dòng thứ i chứa một xâu ký tự độ dài n chỉ gồm hai ký tự “.” Và “#” mô tả trạng thái dòng thứ i của bảng màu (“.” là màu đen, “#” là màu trắng).

Dữ liệu ra:

            Một số nguyên không âm là số ô ít nhất cần sơn lại để được bảng màu đẹp, nếu không thể sơn thành bảng màu đẹp được thì ghi ra -1.

Ví dụ:

Dữ liệu vào:
6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..

Dữ liệu ra:
11

Giải thích: Bảng trước và sau khi sơn lại như sau:

Giới hạn: 1 ≤ m, n ≤ 1000; 1 ≤ x ≤ y ≤ n.