Question

Исполнитель РОБОТ ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд ВВЕРХ (1), ВНИЗ (2), ВПРАВО (3), ВЛЕВО (4) в соседнюю клетку в указанном направлении. РОБОТ выполнил следующую программу: 3322331111444. Укажите наименьшее число команд в программе, приводящей РОБОТа из той же начальной точки в ту же конечную. Сколько всего таких оптимальных маршрутов возможно?

Answer 1

Если в алгоритме есть одновременно 1 и 2, или 3 и 4, то оба этих числа можно убрать:
3322331111444 = 1111223333444 = 113 - наименьшее число команд - три. Т.е. если робот был в клетке (0, 0), то он окажется в клетке (1, 2). Оптимальных маршрутов 3: 113, 131, 311 

Answer 2

Для решения этой задачи нам нужно определить, какие команды из исходной программы можно сократить, чтобы РОБОТ все равно пришел к тому же конечному результату.

Исходная программа РОБОТа: 3322331111444

Мы можем заметить, что последовательности команд 33 и 22 можно заменить на одну команду, так как они отменяют друг друга. То же самое касается последовательностей 11 и 44.

Таким образом, мы можем сократить программу РОБОТа до: 3231

Это означает, что наименьшее число команд в программе, приводящей РОБОТа из той же начальной точки в ту же конечную, равно 4.

Чтобы определить количество возможных оптимальных маршрутов, нам нужно посчитать количество различных перестановок команд в сокращенной программе. В данном случае у нас 4 различных команды, поэтому количество возможных оптимальных маршрутов равно 4! = 24.

Таким образом, наименьшее число команд в программе, приводящей РОБОТа из той же начальной точки в ту же конечную, равно 4, и всего существует 24 оптимальных маршрутов.