Задания № 25, 26 · ЕГЭ

Препятствия на поле Кузнечика

Как исключать запрещённые клетки из числа маршрутов
2 мин чтенияСложность: Обновлено 29 сентября 2026

Препятствия на поле Кузнечика — это клетки, в которые исполнитель не может попасть. При подсчёте маршрутов такие клетки получают значение \(0\), поэтому через них не проходят допустимые пути.

Препятствие на поле КузнечикаВ задачах об исполнителе Кузнечике поле обычно представляют в виде клеток или точек, а переходы между ними задаются командами исполнителя.
Запрещённая клетка поля, посещение которой запрещено условиями задачи. Кузнечик не может приземлиться на неё, а маршрут через такую клетку не считается допустимым.

Сначала полезно повторить правила работы исполнителя Кузнечика. В задачах на маршрут Кузнечика запрещённые клетки учитываются внутри общей схемы маршрута Кузнечика: если клетка недоступна, её не рассматривают как промежуточную и конечную точку.

Как учитывать препятствие

При подсчёте числа маршрутов удобно записывать в каждой клетке количество способов попасть в неё. Для запрещённой клетки сразу записывают \(0\). Для обычной клетки складывают значения в тех клетках, из которых Кузнечик может выполнить один разрешённый прыжок.

\[F(x,y)=\begin{cases}0, & \text{если клетка }(x,y)\text{ запрещена};\\[4pt]\displaystyle\sum F(x_i,y_i), & \text{если клетка доступна}. \end{cases}\]1

Суммируются только предшественники, соответствующие командам Кузнечика. Если запрещена начальная или конечная клетка, число маршрутов также равно \(0\).

№
Короткий пример

Пусть Кузнечик движется только вправо и вверх, а клетка \((2,2)\) запрещена. Если в неё можно попасть из двух соседних клеток, её значение всё равно равно \(0\). Поэтому при вычислении значения клетки \((3,2)\) путь через \((2,2)\) не добавляется: учитывается только доступный предшественник.

!
Не путайте препятствие с нулевым числом маршрутов

Запрещённая клетка недоступна по условию. Доступная клетка тоже может получить \(0\), если до неё невозможно добраться из начальной точки. В первом случае клетку нельзя посещать вообще, во втором она разрешена, но маршрутов до неё нет.

Проверьте себя

Что нужно записать в запрещённой клетке при подсчёте маршрутов?

Главное за минуту

Главное

  • Запрещённая клетка получает значение \(0\).
  • Маршруты через препятствие не учитываются при вычислении соседних клеток.
  • Если начальная или конечная клетка запрещена, допустимых маршрутов нет.