0

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

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

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

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

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-компанию»

Рекурсия и динамика