8. Исполнитель Робот передвигается по клетчатому полю, выполняя команды, которым присвоены номера: 1 — на клетку вверх, 2 — на клетку вниз, 3 — на клетку вправо, 4 — на клетку влево. Между соседними клетками поля могут стоять стены. Если при выполнении очередного шага Робот сталкивается со стеной, то он разрушается. В результате выполнения программы 3242332411 Робот успешно прошел из точки А в точку Б. Какую программу необходимо выполнить, чтобы вернуться из точки Б в точку А по кратчайшему пути и не подвергнуться риску разрушения? a) 41 б) 4131441322 в) 2231441314 г) 241314 д) 14

Решение:

Проанализируем программу, по которой Робот прошёл из точки А в точку Б: 3242332411.

Каждая цифра соответствует команде:

• 1 — на клетку вверх
• 2 — на клетку вниз
• 3 — на клетку вправо
• 4 — на клетку влево

Распишем шаги программы 3242332411:

• 3 — вправо 1 клетка.
• 2 — вниз 1 клетка.
• 4 — влево 1 клетка.
• 2 — вниз 1 клетка.
• 3 — вправо 1 клетка.
• 3 — вправо 1 клетка.
• 2 — вниз 1 клетка.
• 4 — влево 1 клетка.
• 1 — вверх 1 клетка.
• 1 — вверх 1 клетка.

Посчитаем суммарное перемещение по осям:

• Вправо/влево: +1 (вправо) -1 (влево) +1 (вправо) +1 (вправо) -1 (влево) = +1 клетка вправо.
• Вверх/вниз: -1 (вниз) -1 (вниз) -1 (вниз) +1 (вверх) +1 (вверх) = -1 клетка вниз.

Таким образом, точка Б находится на 1 клетку правее и на 1 клетку ниже точки А. Перемещение из А в Б по этой программе составило 1 клетку вправо и 1 клетку вниз.

Кратчайший путь из точки А в точку Б — это прямое перемещение на 1 клетку вправо и 1 клетку вниз. Это можно сделать программой 32.

Теперь нужно вернуться из точки Б в точку А. Если точка Б находится на 1 клетку правее и 1 клетку ниже точки А, то чтобы вернуться из Б в А, нужно сместиться на 1 клетку влево (команда 4) и на 1 клетку вверх (команда 1).

Кратчайший путь из точки Б в точку А — это последовательность команд: 1 клетка влево (4), затем 1 клетка вверх (1). Получаем программу 41.

Другие варианты:

• б) 4131441322: 4 (влево) + 1 (вверх) + 3 (вправо) + 1 (вверх) + 4 (влево) + 4 (влево) + 1 (вверх) + 3 (вправо) + 2 (вниз) + 2 (вниз) = (-1+1-1-1+1+1) + (1+1+1-1-1) = -1 по оси X, +1 по оси Y. Это смещение на 1 влево и 1 вверх. Это также путь из Б в А, но не кратчайший.
• в) 2231441314: 2 (вниз) + 2 (вниз) + 3 (вправо) + 1 (вверх) + 4 (влево) + 4 (влево) + 1 (вверх) + 3 (вправо) + 1 (вверх) + 4 (влево) = (-1-1+1+1-1-1+1) + (-1-1+1+1+1-1) = -1 по оси X, +1 по оси Y. Это смещение на 1 влево и 1 вверх. Это также путь из Б в А, но не кратчайший.
• г) 241314: 2 (вниз) + 4 (влево) + 1 (вверх) + 3 (вправо) + 1 (вверх) + 4 (влево) = (-1+1-1) + (-1+1+1) = -1 по оси X, +1 по оси Y. Это смещение на 1 влево и 1 вверх. Это также путь из Б в А, но не кратчайший.
• д) 14: 1 (вверх) + 4 (влево). Это смещение на 1 влево и 1 вверх. Это также путь из Б в А, но не кратчайший.

Кратчайший путь состоит из минимального количества шагов, чтобы вернуться из Б в А. Так как нам нужно сдвинуться на 1 клетку влево и на 1 клетку вверх, кратчайший путь составит 2 шага: 1 шаг влево (4) и 1 шаг вверх (1).

Ответ: а) 41