Робот находится в углу квадрата 3×3. Роботу надо оказаться в противоположном углу.

Классическая интерпретация задачи: квадрат 3×3 состоит из 3 по 3 клеток (делим на 4×4 узлов). Робот стартует в одном углу и должен попасть в противоположный.

Расставим координаты: старт = (0,0), цель = (3,3). Владение перемещениями: вправо (R) и вверх (U). Пути без диагоналей и без препятствий.

Детальное решение:

1. Сколько нужно сделать горизонтальных и вертикальных перемещений?

• Нужно пройти 3 шага вправо и 3 шага вверх. Итого 3 R и 3 U.

2. Какое минимальное количество ходов?

• Каждый ход меняет либо x, либо y на единицу. Чтобы дойти до (3,3) требуется 3 раза двигать вправо и 3 раза вверх. Итого минимум — 6 ходов.

3. Сколько существует кратчайших путей?

• Кратчайшие пути — это все перестановки из 3 R и 3 U. Количество таких перестановок равно биномиальному коэффициенту: C(6,3) = 6! / (3!·3!) = 20.

4. Примеры кратчайших путей (показано как последовательности ходов):

• R R R U U U
• R R U R U U
• R U R R U U
• R U U R R U
• U R R R U U и т. д. Всего 20 вариантов.

Итого:

• Минимальное число ходов: 6.
• Число различных кратчайших путей: 20.

Дополнительная заметка: если разрешены диагональные перемещения по диагонали квадрата (то есть можно двигаться напрямую по диагонали от одного угла к противоположному), то минимальное расстояние будет длиной диагонали квадрата: sqrt(3^2 + 3^2) = sqrt(18) = 3√2, то есть за один ход можно дойти напрямую по диагонали. Но в классической сеточной постановке без диагоналей ответ выше: 6 ходов и 20 путей.