Разбиение доски на части

Оценка. Если в каждой строке есть клетки двух цветов, то можно из каждой строки вырезать по одной разноцветной доминошке. Пусть одна из строк оказалась одноцветной, без ограничения общности, белой. В каждом столбце тогда не более черных клеток, поэтому черные клетки есть хотя бы в столбцах. Из каждого такого столбца можно вырезать по разноцветной доминошке.

Пример. Разобьем доску на два квадрата и покрасим все клетки каждого квадрата в один цвет. В этом примере можно вырезать только разноцветных доминошек.