Graph algorithm for maximum packing of double squares

Question

I have an area of connected squares (img to the left), and want to find the maximum number of "double" squares that could be fitted into the area (img to the right).

My approach is to represent the original area as a graph, where each square represents a vertex connected by edges to the squares below, above, left and/or right.

I was thinking it could be done by using a BFS algorithm, examining each vertex and applying color. But I also have the feeling it could be done with dynamic programming... I need some help on the way!

Answer 1

Lemma 1:

If we consider the squares as the vertice in the graph, due to its spetial structure, the graph is bipartite graph. Link a edge from each vertice to all its neighborhood vertices.

Proof:

If we paint each squares white or black, we can form that no two blacks neighbored and no two whites neighbored, so the edges in the graph would only between one black and one white.

Algorithm:

After construct the bipartite graph, you can find maximum matching of the bipartite graph, and the value of the maximum matching would be the answer. You can use Hungarian algorithm or faster Hopcroft-Karp algorithm to calculate the answer.