Задача № 4 Робот находится в произвольной клетке столбца шириной в одну клетку. Он должен остановиться в самой нижней закрашенной клетке этого столбца. Такая точно есть.…
Задача № 4 Робот находится в произвольной клетке столбца шириной в одну клетку. Он должен остановиться в самой нижней закрашенной клетке этого столбца. Такая точно есть. 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() Проверить, чиста ли клетка
Задача: робот в произвольной клетке одной колонки. Нужно остановиться в самой нижней закрашенной клетке этой колонки. Есть команды: move_down, move_up, wall_from_down, cell_is_filled и т.д.
Подход (пошагово, понятно для средней школы):
- Сначала дойдём до нижней клетки этой колонки (до стены снизу).
- Затем подниматься вверх и найти первую закрашенную клетку. Эта клетка и будет нижней закрашенной клеткой в колонке.
- Остановимся на ней.
Пошаговое решение:
Добираемся до нижней границы колонки:
- Пока не есть стена снизу (пока wall_from_down() ложно), делай move_down().
- Таким образом, достигнем нижней клетки столбца и будем у стены снизу.
Поднимаемся, пока не найдем закрашенную клетку:
- Пока текущая клетка не закрашена (пока cell_is_filled() ложно), делай move_up().
- Как только попадаем в клетку, которая закрашена, остановимся. Это и будет нижняя закрашенная клетка.
Почему так работает:
- В колонке шириной 1 клетка есть стена снизу. Дойдя до неё, мы находимся в самой нижней клетке.
- Если идти вверх и останавливаться на первой закрашенной клетке, мы именно достигнем самой нижней закрашенной, потому что ниже этой клетки закрашенных клеток быть не может (она нижняя среди закрашенных).
Псевдокод с использованием ваших команд:
- while not wall_from_down(): move_down()
- while not cell_is_filled(): move_up()
- Здесь робот и остановится на нижней закрашенной клетке.
Дополнительные пояснения:
- Сложность алгоритма: за O(N) шагов по количеству клеток в колонке (примерно до удвоенного числа клеток в худшем случае: столько, сколько нужно пройти вниз и затем вверх до нужной клетки).
- Предположение: в колонке действительно есть хотя бы одна закрашенная клетка (уверенность, как и в задаче).
Готово: робот будет остановлен на самой нижней закрашенной клетке этой колонны.
