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

Example:

```
0110
1111
1111 

```

The solution would be 2.

I know it can be solved with Bitmask DP; but I can't really grasp it - after playing with it for hours. How does it work and how can it be formalised?
['https://Stackoverflow.com/questions/28071829', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1327559/']
I wanted to point out that the graph we get by putting vertices at the centers of squares and joining them when they overlap is *not* claw-free:

If we take (in the full plane) a 2x2 square and three of the four diagonally overlapping 2x2 squares, they form the induced subgraph

```
•   •
 \ /
  •
 /
•

```

This is a claw, meaning that any region containing those squares corresponds to a non-claw-free graph.
edit 20:18, there is a counterexample posted by @ILoveCoding

My intuition says, that this will work. I am unable to prove it since I'm not advanced enough. I can't think of any counterexample though.
I will try describe the solution and post the code, please correct me if my solution is wrong.

First we load input to an array.
Then we create second array of the same size and for every possible placing of 2x2 square we mark 1 in the second array. For the example posted by OP this would look like below.

```
0 1 0 0
1 1 1 0
0 0 0 0

```

Then for every 1 in second array we calculate the number of neighbours (including diagonals) + 1 (because if it doesn't have any neighbours we have to still see it as 1). We set those new numbers to the array. Now it should look like this.

```
0 4 0 0
3 4 3 0
0 0 0 0

```

Then for every non-zero value in the array we check whether it has any neighbour with bigger or equal value. If it has then move on since it can't be in the solution. 
If we don't find any such value then it will be in the solution. We have to reset to zero every neighbour of the original value (because it can't be in the solution, it would overlap the solution.

So the first such number found should be 2 on the left. After processing it the array should look like following.

```
0 0 0 0
3 0 3 0
0 0 0 0

```

When we check the other 3 situation is the same.

We end up with non-zero values in the array indicating where top left corners of 2x2 squares are.

If you need the numer of them just traverse 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 write can be found here
<http://ideone.com/Wq1xRo>