ZOJ Problem Set - 1719
Mr. Frugal bought a new house. He feels deeply in love with his new house because it has a comfortable living room in which he can put himself completely at ease. He thinks his new house is a really good buy.
But, to his disappointment, the floor of its living room has some scratches on it.
The floor has a rectangle shape, covered with square panels. He wants to replace all the scratched panels with flawless panels, but he cannot afford to do so. Then, he decides to cover all the scratched panels with carpets.
The features of the carpets he can use are as follows.
> Carpets are square-shaped.
The carpets must cover all the scratched panels, but must not cover any of the flawless ones.
For example, if the scratched panels are as shown in Figure 1, at least 6 carpets are needed.
Figure 1: Example Covering
As carpets cost the same irrespective of their sizes, Mr. Frugal would like to use as few number of carpets as possible.
Your job is to write a program which tells the minimum number of the carpets to cover all the scratched panels.
The positive integers W and H are the numbers of panels on the living room in the x- and y- direction, respectively. The values of W and H are no more than 10. The integer Pyx represents the state of the panel. The value of Pyx means,
0: flawless panel (must not be covered),
Source: Asia 2003, Aizu (Japan), Japan Domestic