Исполнитель РОБОТ ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по...

Question

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

Answer 1

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