Максимальное количество домино может быть размещено внутри фигуры

Question

Предположим, какая-то фигура на бумаге в клетку. Стороны фигуры идут прямо по линиям бумаги в клетку. Фигура может иметь любую (даже не выпуклую) форму. Как найти максимальное количество домино (прямоугольник 1х2), которое можно разместить на этом рисунке. Нельзя ставить домино поверх другого. Допускать домино разрешается только таким образом, когда его стороны падают точно на линии бумаги в клетку.

Answer 1

Похоже, что проблема максимального совпадения количества элементов в двудольном графе .Квадраты - это вершины, а домино - ребра, которые принадлежат совпадению.

Чтобы увидеть, что график является двудольным, представьте, что квадраты нарисованы шахматной доскойЧерные только соседние белые и наоборот.

Answer 2

Вы можете классифицировать квадраты по количеству соседних свободных квадратов как тип 0, 1, 2, 3 или 4.

Я считаю, что должно работать:

1. найдите квадрат типа 1, поместите туда домино единственно возможным способом и повторите

2. еще, найдите свободный угол, образованный двумя смежными квадратами типа 2 и 3, поместите туда домино и перейдите к 1

3. еще, поместите домино в любой квадрат типа 2 и перейдите к 1

4. все готово