maximum number of dominoes can be placed inside a

问题:

Suppose some figure on the squared paper. Sides of the figure go straight on the lines of squared paper. Figure may have any (not even convex) shape. How to find the maximum number of dominoes (1x2 rectangular) that can be placed in that figure. It is not allowed to put domino over another one. It is allowed to put domino only in such way, when its sides fall exactly on the lines of squared paper.

回答1:

Looks like the maximum cardinality matching problem in a bipartite graph. The squares are the vertices and the dominoes are the edges that belong to the matching.

To see that the graph is bipartite, imagine the squares are checkerboard-painted. Black ones only neighbour white ones and vice versa.

回答2:

You can classify squares by the number of neighbor free squares as type 0, 1, 2, 3 or 4.

I believe that should work:

1. find a type 1 square, place there a domino in the only possible way and repeat

2. else, find a free corner formed by two contiguous type 2 and type 3 squares, place there a domino and go to 1

3. else, place a domino in any type 2 square and go to 1

4. you are done