Реши

Ответ: 252 пути.

Пошаговое решение:

1. Определим размер сетки. По изображению сетка состоит из 5 квадратов в строке и 5 квадратов в столбце (то есть 6x6 узлов). Чтобы пройти от левого верхнего узла к правому нижнему, нужно сделать 5 шагов вправо и 5 шагов вниз.

2. Любой путь можно записать как последовательность из 10 движений: 5 раз вправо (R) и 5 раз вниз (D). Количество таких последовательностей равно количеству сочетаний из 10 по 5: C(10, 5) = 10! / (5! · 5!) = 3628800 / (120 · 120) = 252.

3. Альтернативный способ — динамическое программирование:

   • Пути к узлу на первом ряду или в первом столбце всегда по одному (только вправо или только вниз).
   • Правило: ways[i][j] = ways[i-1][j] + ways[i][j-1].
   • Применив это к 6x6 узлам получаем в правом нижнем узле число 252.

Ответ: всего 252 пути.