Square Carpets

Time limit2sMemory limit512 MB

Summary

Find the fewest overlapping square carpets that cover every scratched panel in a grid of up to 10 by 10 and no flawless panel.

Level: Medium6 of 10
Topics: Backtracking, Brute force, Matrix
Solved: No attempts yet

Problem

Mr. Frugal bought a new house. He loves its comfortable living room, where he can relax completely, and he thinks it is a really good buy.

To his disappointment, the living room floor has some scratches.

The floor is a rectangle covered with square panels. He wants to replace every scratched panel with a flawless one, but he cannot afford to do so. So he decides to cover the scratched panels with carpets.

The carpets he can use have these features:

Carpets are square.
Carpets may overlap each other.
Carpets cannot be folded.
Carpets come in different sizes. The side length of a carpet is a multiple of the side length of a panel.

The carpets must cover all scratched panels, and must not cover any flawless panel.

For example, if the scratched panels are as shown in Figure 1, at least 6 carpets are needed.

Figure 1: Example Covering

Input

The input consists of multiple data sets. The end of the input is marked by a line containing two zeros.

DataSet1
DataSet2
...
DataSetn
0 0

Each data set represents the state of a floor, in the following format.

W H
P11 P12 P13 ... P1W
P21 P22 P23 ... P2W
...
PH1 PH2 PH3 ... PHW

W and H are positive integers, the numbers of panels in the x and y directions of the living room. Both are at most 10. $P_{yx}$ is the state of the panel in row y and column x. 0 means a flawless panel (must not be covered), and 1 means a scratched panel (must be covered).

Output

For each data set, output one line containing the minimum number of carpets needed to cover all scratched panels.

Examples1

Example 1

Input

4 3
0 1 1 1
1 1 1 1
1 1 1 1
8 5
0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1
0 1 1 1 0 1 1 1
8 8
0 1 1 0 0 1 1 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 0
10 10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1
0 0

Expected output