3

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!

enter image description hereenter image description here

hampusohlsson
  • 10,109
  • 5
  • 33
  • 50
  • A dynamic programming approach could work if there was a limited "bandwidth" to the graph. For example, if the graph consisted of a path or a tree that was only a few squares thick, but the number of combinations becomes unmanageable otherwise. – Vaughn Cato Jan 04 '13 at 03:57
  • 2
    Possible duplicate: http://stackoverflow.com/q/4780201/951890 – Vaughn Cato Jan 04 '13 at 04:54
  • Possible duplicate of [maximum number of dominoes can be placed inside a figure](https://stackoverflow.com/questions/4780201/maximum-number-of-dominoes-can-be-placed-inside-a-figure) – Rafał Dowgird Nov 07 '17 at 15:30

1 Answers1

6

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.

Jun HU
  • 3,176
  • 6
  • 18
  • 21