Select the maximum number of 2x2 non-overlapping squares in the binary bitmap

Question

For a rectangle consisting of 1 and 0, how can I find the maximum number of non-overlapping 2x2 squares of 1?

Example:

0110 1111 1111 

The solution will be 2.

I know that this can be solved with Bitmask DP; but I can’t understand this - after playing with him for hours. How does it work and how can it be formalized?

Answer 1

Bitmap Shell → Graphic Independent Sets

First translate this into a graph task. Place the node in the center of each 2x2 square of 1s and connect the nodes of the squares that overlap. Your example is as follows:

 0110 1111 1111 

:

  • /|\ •-•-• 

Now our goal is to find the largest independent set . This is usually NP-Hard, but there are graph classes where this is not the case.

Easy because Claw Free

I read the wikipedia page linked above, looking for easy graph classes and checking if your graph type was one of them. The class I found are graphs without a claw .

Our graphs do not have a claw due to three properties:

• Nodes fall on integer points in 2d plane
• If there are nodes at (x, y) and (x + 2, y), then there must be a node at (x + 1, y). Similarly for (x, y) and (x, y + 2) we mean (x, y + 1). This is because two 2x2 squares of 1s, implied by outside points, must touch each other and mean an inside point.
• A node at (x, y) must have an edge for any nodes at 8 points around it. These nodes have 2x2 squares that overlap with the central 2x2 square.

These three properties are enough to show that although you can make two nodes that do not separate the edge connecting to the central node, you cannot do it in three (make a claw). The third node always ends with an edge to one of the other two.

Paper

Here's a link to a clawless document that links to wikipedia . (This is in French. Sorry.)

Answer 2

Here is a solution for dynamic programming.

• State (row number, mask of occupied cells, shift position) . It looks like this:

   ..#.. .##.. .#... .#... 

  In this case, the line number is 2 (I use indexes with zero base), the mask depends on whether we take a c # cell or not, the shift position is 1. The number of states is O(n * m * 2 ^ n) . The status value is the maximum number of selected squares 2x2. The base register is f(1, 0, 0) = 0 (it corresponds to the first row and 2 × 2 squares so far selected).

• The transitions are as follows:

   ..#.. ..#.. .00.. -> ..1.. .0... .11.. .#... .#... 

  This can be used if and only if the square consists of units in the original matrix and the mask contains zeros (this means that we select this square). Other:

   ..#.. ..#.. .##.. -> ..#.. .#... .#0.. .#... .#... 

  This is always applicable. This means that we select this 2x2 square. When we finish with one line, we can move on to the following:

   ..#.. ..#0. ..#.. -> ..#.. ..#.. ..#.. .##.. ..#.. 

There are no more than two transitions from each state, so the total time complexity is O(n * m * 2 ^ n) . The answer is the maximum among all masks and shifts for the last line.

Answer 3

If you build a graph in which each node represents a 2x2 square of 1, and if they overlap, an edge appears between the two nodes, then the problem is this: find the maximum independent set in this graph.

Answer 4

edit 20:18, there is a counterexample posted by @ILoveCoding

My intuition says this will work. I can not prove it, because I'm not advanced enough. However, I cannot come up with any counterexample. I will try to describe the solution and publish the code, please correct me if my solution is not true.

First we load the input into the array. Then we create a second array of the same size and for each possible placement of a 2x2 square, we mark 1 in the second array. For the example published by OP, it will look below.

 0 1 0 0 1 1 1 0 0 0 0 0 

Then, for each 1 in the second array, we calculate the number of neighbors (including diagonals) + 1 (because if it does not have any neighbors, we should see it as 1). We set these new numbers to an array. Now it should look like this.

 0 4 0 0 3 4 3 0 0 0 0 0 

Then, for each nonzero value in the array, we check to see if it has any neighbor with a greater or equal value. If he will move on, because he cannot be in a decision. If we do not find such a value, then it will be in the solution. We must reset to zero each neighbor of the original value (because it cannot be in the solution, it will overlap the solution.

So, the first number found should be 2 on the left. After processing, the array should look like this.

 0 0 0 0 3 0 3 0 0 0 0 0 

When we check that the other situation is the same.

As a result, we get non-zero values ​​in the array indicating where the upper left corners of 2x2 squares are located.

If you want the number of them to just cross the array and count non-zero elements.

Another example

 1111 -> 1 1 1 0 -> 4 6 4 0 -> 4 0 4 0 1111 -> 1 1 1 0 -> 6 9 6 0 -> 0 0 0 0 1111 -> 1 1 1 0 -> 6 9 6 0 -> 6 0 6 0 1111 -> 1 1 1 0 -> 6 9 6 0 -> 0 0 0 0 1111 -> 1 1 1 0 -> 4 6 4 0 -> 4 0 4 0 1111 -> 0 0 0 0 -> 0 0 0 0 -> 0 0 0 0 

The code I'm writing can be found here http://ideone.com/Wq1xRo