Задача По периметру большого прямоугольного зала устроены небольшие ниши, отделённые друг от друга стенами. Роботу надо обойти все эти ниши. Для начала надо научить его двигаться…
Задача По периметру большого прямоугольного зала устроены небольшие ниши, отделённые друг от друга стенами. Роботу надо обойти все эти ниши. Для начала надо научить его двигаться вдоль одной стены. Напишите программу, которая позволит роботу перейти в следующую по часовой стрелке нишу (клетку) и покрасить её. move_left Сделать шаг влево move_right Сделать шаг вправо move_up Сделать шаг вверх move_down Сделать шаг вниз fill_cell Закрасить клетку free_from_up Проверить, свободно ли сверху free_from_down Проверить, свободно ли снизу free_from_left Проверить, свободно ли слева free_from_right Проверить, свободно ли справа wall_from_up Проверить, есть ли стена сверху wall_from_down Проверить, есть ли стена снизу wall_from_left Проверить, есть ли стена слева wall_from_right Проверить, есть ли стена справа cell_is_filled Проверить, закрашена ли клетка cell_is_clean Проверить, чиста ли клетка
Задача понятна. Мы будем обходить периметр прямоугольной зоны по часовой стрелке и закрашивать каждую нишу по пути. При этом мы предполагаем, что робот изначально находится в верхнем левом углу периметра (первая ниша слева сверху) и что начальная ниша тоже должна быть окрашена.
Что именно мы делаем
- закрашиваем стартовую нишу
- двигаемся вправо вдоль верхнего края периметра, окрашивая каждую занятую клетку (W-1 шагов вправо, всего W клеток вдоль верхней стороны)
- затем идём вниз по правому краю, окрашивая каждую нишу (H-1 шагов вниз, всего H клеток вдоль правого края)
- затем идём влево по нижнему краю, окрашивая каждую нишу (W-1 шагов влево, всего W клеток вдоль нижнего края)
- затем идём вверх по левому краю, окрашивая каждую нишу (H-2 шагов вверх, чтобы вернуться к клетке рядом с началом и не дублировать её)
Переменные, которые вам понадобятся
- W — число ниш на верхней стороне прямоугольника (ширина периметра в нишах)
- H — число ниш на левой стороне прямоугольника (высота периметра в нишах)
Псевдокод решения (используйте команды в таком виде)
Начальное окрашивание/start fill_cell
Двигаемся вправо по верхнему краю for i от 1 до W-1 move_right fill_cell end
Двигаемся вниз по правому краю for j от 1 до H-1 move_down fill_cell end
Двигаемся влево по нижнему краю for i от 1 до W-1 move_left fill_cell end
Двигаемся вверх по левому краю for j от 1 до H-2 move_up fill_cell end
Итого мы закрашиваем все клетки периметра ровно один раз. Формула количества закрашиваемых ниш: 2W + 2H - 4, что соответствует сумме верхней стороны (W), правой стороны (H-1), нижней стороны (W-1) и левой стороны (H-2), итого W + (H-1) + (W-1) + (H-2) = 2W + 2H - 4.
Пример для наглядности Пусть W = 6, H = 4 (периметр состоит из 16 ниш).
Начальное: fill_cell
Вверх вправо по верхнему краю move_right, fill_cell move_right, fill_cell move_right, fill_cell move_right, fill_cell move_right, fill_cell
Вниз по правому краю move_down, fill_cell move_down, fill_cell move_down, fill_cell
Влево по нижнему краю move_left, fill_cell move_left, fill_cell move_left, fill_cell move_left, fill_cell move_left, fill_cell
Вверх по левому краю move_up, fill_cell move_up, fill_cell
Итого окрашено 16 ниш, как и задумано.
Дополнительные замечания
- Условия задачи без явного указания размеров W и H можно решить и без них, но тогда понадобится алгоритм обхода по стенам (правило правой руки или левой руки) с ведением ориентации. Это потребовало бы хранения текущей ориентации и реализации "поворотов" через комбинацию команд перемещения и проверок wall_from_*/free_from_*. Если нужно, могу привести такой вариант с ориентированием и динамическим обходом периметра.
- Если задача подразумевает, что размеры ещё неизвестны во время выполнения, дайте знать — покажу универсальный алгоритм обхода по стене (правой или левой) с примером кода на вашем языке/среде.
Скажите, какие размеры W и H у вашего прямоугольного зала, или нужна версия с динамическим обходом по стенам? Я адаптирую решение под нужный формат и язык программирования.
