ОГЭ по информатике · задание 15

Исполнитель Робот: алгоритм для лабиринта

Нужно написать алгоритм для Робота на языке Кумир, который работает при любой длине стен и любом положении проходов. Алгоритм можно проверить прямо на странице: он запустится на поле из условия и на 40 случайных полях.

Команды Робота

  • Приказы: вверх, вниз, влево, вправо, закрасить.
  • Условия: сверху/снизу/слева/справа свободно (или стена), клетка закрашена/чистая.
  • нц пока условие … кц; если условие то … иначе … все.

Как решать

  1. Нарисовать поле и путь Робота.
  2. Каждый участок стены — свой цикл: «пока стена — красим и идём».
  3. Проход — отдельный цикл без закрашивания.
  4. Проверить крайние случаи: короткая стена, широкий проход, проход у угла.

Типичные ошибки

  • Робот врезается в стену в углу.
  • Цикл не заканчивается за концом стены.
  • Закрашена клетка прохода или клетка за концом стены.

Разобранные варианты

Исполнитель Робот умеет перемещаться по лабиринту, начерченному на плоскости, разбитой на клетки. Между соседними (по сторонам) клетками может стоять стена, через которую Робот пройти не может. Команды-приказы: вверх, вниз, влево, вправо, закрасить. Команды проверки условий: сверху свободно, снизу свободно, слева свободно, справа свободно (и обратные им: сверху стена и т. д.). Условия используются в конструкциях если … то … иначе … все и нц пока … кц; их можно соединять словами и, или, не.

Вариант 1

угол из двух стен (как в демоверсии)

На бесконечном поле есть горизонтальная и вертикальная стены. Правый конец горизонтальной стены соединён с верхним концом вертикальной стены. Длины стен неизвестны. В каждой стене есть ровно один проход, точное место прохода и его ширина неизвестны. Робот находится в клетке, расположенной рядом с вертикальной стеной слева от её нижнего конца. Напишите для Робота алгоритм, закрашивающий все клетки, расположенные непосредственно левее вертикальной стены и ниже горизонтальной стены. Проходы должны остаться незакрашенными.

Пример поля (Р — Робот, серым — клетки, которые нужно закрасить):

Разбор

Идея. Обе стены проходим по три цикла: «пока стена — красим и идём», «пока проход — просто идём», «пока снова стена — красим». Подъём вдоль вертикальной стены заканчивается, когда сверху появилась горизонтальная стена — это угол.

Алгоритм:

использовать Робот
алг
нач
  | вдоль вертикальной стены вверх: до прохода, проход, после прохода
  нц пока справа стена
    закрасить
    вверх
  кц
  нц пока справа свободно
    вверх
  кц
  нц пока сверху свободно
    закрасить
    вверх
  кц
  | в углу; дальше влево вдоль горизонтальной стены
  нц пока сверху стена
    закрасить
    влево
  кц
  нц пока сверху свободно
    влево
  кц
  нц пока сверху стена
    закрасить
    влево
  кц
кон

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

Вариант 2

коридор

На бесконечном поле есть две параллельные горизонтальные стены, образующие коридор шириной в одну клетку. Длина коридора неизвестна. В верхней и в нижней стене есть ровно по одному проходу; проходы не расположены друг напротив друга и не находятся у концов стен. Робот находится в самой левой клетке коридора. Напишите алгоритм, закрашивающий все клетки коридора, у которых есть стена и сверху, и снизу.

Пример поля (Р — Робот, серым — клетки, которые нужно закрасить):

Разбор

Идея. Идём вправо, пока хотя бы с одной стороны есть стена: проходы не стоят друг напротив друга, поэтому цикл закончится только за правым концом коридора. Красим клетку, только если стены есть с обеих сторон.

Алгоритм:

использовать Робот
алг
нач
  нц пока сверху стена или снизу стена
    если сверху стена и снизу стена то
      закрасить
    все
    вправо
  кц
кон

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

Вариант 3

стена с двух сторон

На бесконечном поле есть вертикальная стена. Длина стены неизвестна, проходов в ней нет. Робот находится в клетке, расположенной слева от верхнего конца стены. Напишите алгоритм, закрашивающий все клетки, прилегающие к стене слева и справа.

Пример поля (Р — Робот, серым — клетки, которые нужно закрасить):

Разбор

Идея. Спускаемся вдоль левой стороны, пока справа стена. Ниже конца стены обходим её: шаг вправо и шаг вверх — и поднимаемся по правой стороне, пока слева стена.

Алгоритм:

использовать Робот
алг
нач
  нц пока справа стена
    закрасить
    вниз
  кц
  вправо
  вверх
  нц пока слева стена
    закрасить
    вверх
  кц
кон

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

Вариант 4

стена с проходом

На бесконечном поле есть горизонтальная стена. Длина стены неизвестна. В стене есть ровно один проход, его место и ширина неизвестны, у концов стены прохода нет. Робот находится в клетке под левым концом стены. Напишите алгоритм, закрашивающий все клетки, расположенные непосредственно под стеной. Проход должен остаться незакрашенным.

Пример поля (Р — Робот, серым — клетки, которые нужно закрасить):

Разбор

Идея. Три цикла: красим до прохода, проходим проход, красим остаток стены.

Алгоритм:

использовать Робот
алг
нач
  нц пока сверху стена
    закрасить
    вправо
  кц
  нц пока сверху свободно
    вправо
  кц
  нц пока сверху стена
    закрасить
    вправо
  кц
кон

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

Для самостоятельного решения

Варианты 5–6 без разбора. Проверка на полях работает так же.

Вариант 5

угол: только вертикальная стена

На бесконечном поле есть горизонтальная и вертикальная стены. Правый конец горизонтальной стены соединён с верхним концом вертикальной стены. Длины стен неизвестны. В каждой стене есть ровно один проход, место и ширина прохода неизвестны. Робот находится в клетке слева от нижнего конца вертикальной стены. Напишите алгоритм, закрашивающий все клетки, расположенные непосредственно левее вертикальной стены. Проход должен остаться незакрашенным.

Пример поля (Р — Робот, серым — клетки, которые нужно закрасить):

Вариант 6

клетки над стеной

На бесконечном поле есть горизонтальная стена. Длина стены неизвестна. В стене есть ровно один проход, его место и ширина неизвестны, у концов стены прохода нет. Робот находится в клетке над левым концом стены. Напишите алгоритм, закрашивающий все клетки, расположенные непосредственно над стеной. Проход должен остаться незакрашенным.

Пример поля (Р — Робот, серым — клетки, которые нужно закрасить):