Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу: вверх; влево; влево; вверх ;
вправо; вверх; вправо
Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную.
Для начала, введем пару обозначений: пусть "U" обозначает перемещение вверх по клеткам, "D" - перемещение вниз, "L" - влево и "R" - вправо.
Изначально, робот находится в некоторой клетке начальной позиции. Для того чтобы вернуться в эту клетку, необходимо использовать равное количество команд вверх и вниз, а также равное количество команд влево и вправо.
Заметим, что в данной программе указано два перемещения вверх и два перемещения влево. Будем сохранять суммарные перемещения отдельно по горизонтали и вертикали:
- По горизонтали у нас два перемещения влево и одно перемещение вправо, т.е. нам нужно двигаться на 2 клетки влево.
- По вертикали у нас два перемещения вверх, поэтому нам нужно двигаться на 2 клетки вверх.
Таким образом, чтобы робот вернулся в ту же конечную клетку, достаточно добавить две команды перемещения влево и две команды перемещения вверх.
Таким образом, минимальное возможное число команд в программе, переводящей робота из начальной клетки в конечную, равно 6. Программа будет выглядеть следующим образом:
1. вверх
2. влево
3. влево
4. вверх
5. вверх
6. влево