Робот находится в углу квадрата 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 путей.