Предположим, что на квадратной бумаге есть фигура. Стороны фигуры идут прямо на линии квадратной бумаги. Рисунок может иметь любую (даже не выпуклую) форму. Как найти максимальное количество домино (прямоугольник 1x2), которое можно разместить на этом рисунке. Нельзя ставить домино над другим. Разрешено помещать домино только таким образом, когда его стороны падают точно на линии квадратной бумаги.
Максимальное число домино можно разместить внутри фигуры
Ответ 1
Похож на проблему согласования максимальной мощности на двухстороннем графике. Квадраты - это вершины, а домино - это ребра, принадлежащие сопоставлению.
Чтобы увидеть, что граф двудольный, представьте, что квадраты окрашены в шахматы. Черные только соседние белые и наоборот.
Ответ 2
Вы можете классифицировать квадраты по числу соседних свободных квадратов типа 0, 1, 2, 3 или 4.
Я считаю, что это должно работать:
-
найдите квадрат типа 1, поместите там домино единственным возможным способом и повторите
-
else, найдите свободный угол, образованный двумя смежными квадратами типа 2 и 3, разместите там домино и перейдите к 1
-
else, поместите домино в квадрат любого типа 2 и перейдите к 1
-
вы закончили