Подсчёт количества путей робота на сетке

Представьте себе робота, находящегося в левом верхнем углу сетки с координатами (X, Y). Робот может перемещаться в двух направлениях: вправо и вниз. Сколько существует маршрутов, проходящих от точки (0, 0) до точки (X, Y)?

Дополнительно:

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

Решение

Нам нужно подсчитать количество вариантов прохождения дистанции с Х шагов вправо и Y шагов вниз (X + Y шагов).

Чтобы создать путь, мы делаем Х шагов вправо так, чтобы общее количество перемещений оставалось фиксированным (X + Y). Таким образом, количество путей должно совпадать с количеством способов выбрать Х элементов из X + Y, то есть биномиальным коэффициентом. Биномиальный коэффициент из n по r имеет вид:

formula1

Для нашей задачи выражение будет следующим:

formula2

Даже если вы незнакомы с комбинаторикой, то все равно можете найти решение этой задачи самостоятельно.

Представим путь как строку длиной X + Y, состоящую из X символов R и Y символов D. Мы знаем, что из X + Y неповторяющихся символов мы можем составить (X + Y)! строк. Но в нашем случае используется X символов R и Y символов D. Символы R могут быть расставлены X! способами (то же самое мы можем сделать и с символами D). Таким образом, необходимо убрать лишние строки X! и Y!. В итоге мы получим то же самое выражение:

formula3

Дополнительно

Найдите маршрут (на карте есть места, через которые не может пройти робот).

Если мы изобразим нашу карту, то единственный способ попасть в квадрат (X, Y) — оказаться в одном из смежных квадратов: (X-1, Y) или (X, Y-1). Следовательно, необходимо найти путь к любому из этих квадратов ((X-1, Y) или (X, Y-1)).

Как это осуществить? Чтобы найти путь в квадрат (X-1, Y) или (X, Y-1), мы должны оказаться в одной из смежных ячеек. То есть нам необходимо найти путь к квадрату, смежному с (X-1, Y) ((X-2, Y) и (X-1, Y-1)) или (X, Y-1) ((X-1, Y-1) и (X, Y-2)). Обратите внимание: в наших рассуждениях точка (X-1, Y-1) упоминается дважды, мы еще вернемся к этому факту.

Давайте попробуем найти путь от исходного квадрата, двигаясь в обратном направлении, — начинаем с последней ячейки и пытаемся найти путь к каждому смежному квадрату. Далее приведен рекурсивный код, реализующий наш алгоритм.

Помните, что маршруты дублируются? Чтобы найти все пути к (X, Y), мы находим все пути к (X-1, Y) и (X, Y-1). Затем мы смотрим на координаты смежных квадратов: (X-2, Y), (X-1, Y-1), (X-1, Y-1) и (X, Y-2). Квадрат (X-1, Y-1) появляется дважды. Давайте будем запоминать посещенные квадраты, чтобы не тратить на них время.

Это можно сделать с помощью следующего алгоритма динамического программирования:

Это простое изменение сделает наш код более быстрым.

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»