Карта дня, май, перетяжка
Карта дня, май, перетяжка
Карта дня, май, перетяжка

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

Аватар Типичный программист
Отредактировано

27К открытий30К показов
Подсчёт количества путей робота на сетке

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

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

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

Решение

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

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

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

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

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

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

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

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

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

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

Если мы изобразим нашу карту, то единственный способ попасть в квадрат (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) упоминается дважды, мы еще вернемся к этому факту.

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

			public boolean getPath(int x, int y, ArrayList<Point> path) {
    Point p = new Point(x, y);
    path.add(p);
    if (x == 0 && y == 0) {
        return true;                  // найти путь
    }
    bolean success = false;
    if (x >= 1 && isFree(x – 1, y)) {    // Пытаемся идти вправо
        success = getpath(x – 1, y, path);  // Свободно! Можно идти вправо
    }
    if ( !success && y >= 1 && isFree(x, y - 1)) {   // Пытаемся идти вниз
        success = getPath(x, y – 1, path);    // Свободно! Можно идти вниз
    }
    if (!success) {
        path.remove(p);  // Неверный путь! Прекратить движение этим маршрутом
    }
        return success;
}
		

Помните, что маршруты дублируются? Чтобы найти все пути к (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) появляется дважды. Давайте будем запоминать посещенные квадраты, чтобы не тратить на них время.

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

			public Boolean getPath(int x, int y, ArrayList<Point> path,
Hashtable<Point, Boolean> cache){
        Point p = new Point(x, y);
        if (cache.containsKey(p)) { // Мы уже посещали эту ячейку
            return cache.get(p);
        }
        path.add(p);
        if (x == 0 && y == 0) {
            return true;  // Найден путь
        }
        boolean success = false;
        if (x >= 1 && isFree(X - 1, Y)) { //Пытаемся идти вправо
            success = getPath(x - 1, y, path, cache); // Свободно! Можно идти вправо
        }
        if (!success && y >= 1 && isFree(x, y - 1)) { // Пытаемся идти вниз
            success = getPath(x, y - 1, path, cache); // Свободно! Можно идти вниз
        } 
        if (!success) {
            path.remove(p); //Неверный путь! Прекратить движение этим маршрутом
        }  
        cache.put(p, success); // Вычисляем результат
        return success;
}
		

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

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

Следите за новыми постами
Следите за новыми постами по любимым темам
27К открытий30К показов