Все вы знаете игру домино. Домино напоминает кирпичики, сделанные из двух квадратиков. Есть много разных задач, связанных с замощением домино различных фигур. Например, знаете ли вы, что доминошками нельзя замостить шахматную доску без клеток A1 и H8, хотя клеток на ней 62, а число 62 делится на 2? Здесь подразумевается, что домино достаточно большое, чтобы покрывать ровно две клетки.
Предлагаем вам другую игру с домино. Нужно перемещениями доминошек замостить квадрат 4х4:
В вашем распоряжении два преобразования:
Чем меньше вы сделаете преобразований, тем лучше. При равном числе преобразований лучшим считается решение с меньшим числом сдвигов.