Реши задание на изображении

Краткий ответ: на фото — инструкция: нужно самому составить задачу о маршрутах по квартальной схеме, построить граф и найти кратчайший путь. Готовый пример: сетка 3 квартала вправо и 2 вверх даёт 10 кратчайших маршрутов, длина каждого — 5 участков.

Пример задачи

От перекрёстка \(A\) нужно попасть в перекрёсток \(B\), двигаясь только вправо и вверх, без возвращений. Схема: 3 квартала вправо, 2 вверх. Сколько существует различных кратчайших маршрутов?

Граф улиц

Вершины — перекрёстки, рёбра — участки улиц между соседними перекрёстками:

(0,2) — (1,2) — (2,2) — (3,2)=B
  |       |       |       |
(0,1) — (1,1) — (2,1) — (3,1)
  |       |       |       |
(0,0) — (1,0) — (2,0) — (3,0)
 =A

Как считать

Любой кратчайший маршрут состоит ровно из:

• 3 шагов вправо: \(\rightarrow\);
• 2 шагов вверх: \(\uparrow\).

Всего 5 шагов. Маршрут однозначно задаётся тем, на каких местах стоят 3 шага вправо:

\[ N=\binom{5}{3}=\frac{5!}{3!\cdot2!}=10. \]

Проверка по таблице: в каждой клетке — число способов дойти до неё; клетка равна сумме соседей слева и снизу:

\[ \begin{matrix} 1&3&6&10\\ 1&2&3&4\\ 1&1&1&1 \end{matrix} \]

В правом верхнем углу получаем \(10\).

Кратчайший путь

Один из них:

\[ A(0,0)\to(1,0)\to(2,0)\to(2,1)\to(3,1)\to B(3,2). \]

Это \(\rightarrow,\rightarrow,\uparrow,\rightarrow,\uparrow\) — 5 участков. Короче нельзя: нужно пройти 3 квартала по горизонтали и 2 по вертикали, то есть минимум 5 шагов.

Принцип для похожей задачи: для сетки \(m\times n\) без препятствий число кратчайших маршрутов равно \(\binom{m+n}{m}\). Если есть закрытый участок, в соответствующей клетке ставят \(0\) и продолжают сумму по соседям.

Если нужна именно ваша схема с другими размерами или перекрытиями, пришлите её крупнее — по одной инструкции конкретных чисел в ней нет.