Задание 15. Алгоритм для исполнителя Робот — теория и разбор

Робот двигается по клетчатому полю и разбивается о стену, если получает команду пройти сквозь неё — вся сложность задания в том, чтобы написать алгоритм, работающий при любом размере комнаты, а не только для конкретной картинки в условии.

Что нужно знать

У Робота девять команд.

Команды-приказы (пять): вверх, вниз, влево, вправо — сдвигают Робота на одну клетку; если по пути стена — Робот разрушается. Пятая — закрасить, закрашивает клетку, где Робот находится сейчас.

Команды проверки условия (четыре): сверху свободно, снизу свободно, слева свободно, справа свободно — проверяют, нет ли стены в соответствующем направлении, не двигая Робота.

Из проверок строятся управляющие конструкции:

если <условие> то
    <команды>
все

нц пока <условие>
    <команды>
кц

если...то...все выполняет команды один раз, если условие истинно. нц пока...кц повторяет команды, пока условие остаётся истинным — это и есть способ пройти комнату любого размера, не зная заранее, сколько клеток впереди.

Размер поля в условии не задан явно и никогда не совпадает с тем, что нарисовано на картинке для примера — правильный алгоритм должен использовать нц пока <проверка направления>, а не заранее известное число шагов, иначе он сработает только на одном конкретном поле.

Правило оценивания: 2 балла — алгоритм работает для поля любого размера и конфигурации стен; 1 балл — алгоритм завершается и не разрушает Робота, но допускает немного (не больше 10) лишних или пропущенных закрашенных клеток; 0 баллов — Робот разрушается, алгоритм не завершается или решает только конкретную картинку из примера.

Разбор примера

Робот находится в левом верхнем углу прямоугольной комнаты неизвестного размера (стены — только по периметру, без проёмов). Закрасьте все клетки верхнего ряда комнаты и весь правый столбец, начиная от старта.

Как думать. Задача распадается на два независимых прохода вдоль стен: сначала пройти вправо до упора, закрашивая путь, затем — вниз до упора, тоже закрашивая. Оба прохода — циклы «пока свободно в нужную сторону».

закрасить
нц пока справа свободно
    вправо
    закрасить
кц
нц пока снизу свободно
    вниз
    закрасить
кц

Как проверить логику в Python

Логику алгоритма Робота удобно проверить симуляцией на виртуальной сетке — если множество закрашенных клеток совпадает с ожидаемым (верхний ряд + правый столбец), алгоритм верен:

def run(width, height):
    x, y = 0, 0
    painted = {(x, y)}
    while x + 1 < width:      # аналог "нц пока справа свободно"
        x += 1
        painted.add((x, y))
    while y + 1 < height:     # аналог "нц пока снизу свободно"
        y += 1
        painted.add((x, y))
    return painted

for w, h in [(5, 3), (2, 2), (8, 6)]:
    result = run(w, h)
    expected = {(i, 0) for i in range(w)} | {(w - 1, j) for j in range(h)}
    print(w, h, result == expected)   # True для любого размера

Такая проверка — не часть решения на экзамене (там алгоритм пишут в среде исполнителя или текстом), а способ убедиться, что логика действительно универсальна.