Задача № 13 Робот находится в левой нижней клетке прямоугольника 2×12. Задача робота — покрасить все клетки прямоугольника, в которых есть проход из прямоугольника. Остановиться…

Задача №13. Понимание и подробное решение

Коротко: в прямоугольнике 2×12 каждая клетка граничная, следовательно, нужно покрасить все 24 клетки и вернуться в исходную.

Предложенный маршрут (работ начинает в нижнем левом углу, координаты можно считать как (ряд, столбец): нижний ряд = 2, верхний = 1; старт — (2,1)):

• Старт: (2,1) — покрасьте эту клетку.
• Дальше двигайтесь вправо вдоль нижнего ряда до правого конца: выполните 11 шагов вправо, чтобы оказаться в (2,12).
• Поднимитесь на одну клетку вверх: до (1,12).
• Затем идите влево вдоль верхнего ряда до левого конца: выполните 11 шагов влево, чтобы оказаться в (1,1).
• И, наконец, опуститесь вниз обратно в исходную клетку: до (2,1).

Итак, маршрут можно записать как: Right 11, Up 1, Left 11, Down 1.

Почему это решение подходит:

• В 2×12 все клетки являются пограничными, значит нужно покрасить все 24 клетки.
• Данный маршрут образует цикл Гамильтона по графу «соседние клетки» прямоугольника: он за visits каждую клетку ровно один раз и возвращается в стартовую, что удовлетворяет условиям задачи.
• Любая эквивалентная дуга-последовательность, начинающаяся в (2,1) и проходящая по верхнему и нижнему рядам по краю, тоже будет верной (например, начать вверх к (1,1), затем по верхнему ряду вправо до (1,12), затем вниз к (2,12) и обратно по нижнему ряду до (2,1)).

Дополнительные пояснения:

• В прямоугольнике высотой 2 клетки нет «внутренних» клеток, поэтому задача сводится к покрытию всех 24 клеток одним непрерывным обходом и возврату в стартовую.
• Маршрут можно записать в виде последовательности направлений: R, R, ..., R (11 раз), U, L, L, ..., L (11 раз), D. Это эквивалентно описанному выше.

Если нужно, могу привести аналогичный маршрут для любой 2×N, объяснить, как строить такие циклы для произвольного N.