— В клетчатом мире живут клетки, тогда кто живет в мире в горошинку?
— …
Теория
Всё происходит на разлинованой клетками ограниченной площади. Например, поле 5x7. Клетка поля может иметь несколько состояний: пуста, закрашена изначально и с меткой определенного цвета. Для взаимодействия с полем доступен робот, который может изменять свое положение и состояния клеток вокруг. Для решения лабораторной работы существует необходимый и достаточный набор набор инструкций, который приведен ниже:
Данные:
текущая позиция
ширина поля
длина поля
Команды:
запомним <имя-памяти> <значение>
передвижение <направление>
переместиться <координата-X> <координата-Y>
залить <положение> <цвет>
проверить <положение> на <цвет>
Конструкции:
если (<условие>), то <команды> [, иначе <команды>]
цикл-пока (<условие>), делать <команды> конец цикла-пока
цикл-счетчик (<переменная>, <начало>, <конец>), делать <команды> конец цикла-счетчика
Всегда можно изменить команду, конструкцию, переменную или константу с учетом русского языка, превратив все в плавный текст (если сможете). Например:
В цикле-счетчике с переменной X от 0 до ширины, выполнить следующее: в
цикле-счетчике с переменной Y от 0 до высоты, выполнить следующее:
переместить на координату (X, Y) и, если не закрашена, закрасить
красным цветом. Конец.
или
Пробежаться змейкой по полю от (0, 0) до (ширины, высоты) и, если встречается
незакрашенное поле, закрасить красным цветом. Конец.
или
Пробежаться по каждой клетке и, если встречается незакрашенное поле, закрасить
красным цветом. Конец.
Зачем все эти сложности? Чтоб вам и проверяющему потом было понятно что происходит.
Задача
Дано поле, на котором расположены закрашенные клетки. Робот может ставить метки, метка может быть поставлена на любую клетку. Однако стирать метку нельзя. Красными метками пользоваться с осторожностью, так как относительно них будет считаться решение. Неоптимизированное или примитивное решение, например, с полной заливкой будет, оцениваться отрицательно. ✍(◔◡◔)
1 часть
Требуется расставить красные метки так, чтоб все изначально закрашенные клетки были соединены. Закрашенные клетки не могут быть отдалены больше, чем на 1 клетку друг от друга.
2 часть
Требуется сделать максимально оптимальное решение (соединяет за минимальное количество меток), с условием, что закрашенные клетки не могут быть отдалены больше, чем на 2 клетки.
Пример решения усложненной задачи:
Что требуется как решение?
Алгоритм должен соединить все закрашенные клетки, используя минимальное количество маркеров. Робот может ходить по полю и ставить маркеры вокруг себя и даже под себя. При этом для использования есть несколько штук маркеров (разных цветов), чтоб временно отмечать клетки. Однако красные маркеры будут считаться закрашенными клетками после завершения алгоритма. Если вы всё отметили красными метками, то все клетки будут закрашены.
Заключающей частью решения будет отчет, в котором будут записаны ваше решение и размышления, процесс создания и варианты развития.