Решение разработано в:

Вопрос

В этой статье мы рассмотрим вопрос Leetcode ‘778. Swim in Rising Water». Вопрос с расширенным графиком.

Вопрос:

Вам дана целочисленная матрица n x n grid, где каждое значение grid[i][j] представляет собой высоту над уровнем моря в данной точке (i, j).
Начинается дождь. В момент времени t глубина воды везде равна t. Вы можете переплыть из квадрата в другой 4-направленный соседний квадрат тогда и только тогда, когда высота обоих квадратов по отдельности не больше t. Вы можете проплыть бесконечное расстояние за нулевое время. Конечно, во время плавания вы должны оставаться в границах сетки.
Верните наименьшее время, за которое вы сможете добраться до правого нижнего квадрата (n — 1, n — 1), если начнете с левого верхнего квадрата (0, 0).

Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Объяснение вопроса

Этот вопрос оценивается как трудный. Я бы сказал, что это неточно. Если вы знакомы с алгоритмом Дейкстры, алгоритмом Беллмана-Форда или любым другим алгоритмом поиска пути, этот вопрос должен быть средним. Если вы никогда не сталкивались с этим алгоритмом, то по большей части это будет невозможно.

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

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

Как вы думаете, откуда Google Maps знает кратчайшее расстояние между вашим домом и домом вашего друга? Алгоритмы кратчайшего пути, такие как алгоритм Дейкстры или алгоритм Беллмана-Форда, используются для поиска кратчайшего пути между двумя точками.

Именно это мы и собираемся сделать. Найдем кратчайший путь между [0][0] и правой нижней частью доски за наименьшее время. Где время представлено глубиной воды, которая является значением элемента на доске. То есть, при глубине 10, мы можем пройти все узлы, которые <= 10.

Рекомендуемые знания

1. Теория графов
2. Алгоритм Дейкстры
3. Алгоритмы поиска пути
4. Матрица
5. Обход матрицы
6. Очередь приоритетов
7. Куча

Что мы знаем?

1. Нам дана матрица M x N.
2. Нам нужно начать с [0][0] и закончить на [M][N].
3. Нам нужно найти кратчайший путь между [0][0] и [M][N], определяемый глубиной воды.
4. Глубина воды определяется значением [x][y] матрицы.
5. Мы можем переходить к соседним узлам, только если глубина воды <= глубине узла.
6. [M][N] уникальна и всегда единственна, никогда не дублируется.

Как мы собираемся это сделать:

Мы будем использовать алгоритм Дейкстры для поиска кратчайшего пути между [0][0] и [M][N]. Кратчайший путь определяется как наименьшее количество времени, необходимое для прохождения пути от [0][0] до [M][N]. Где время представлено глубиной воды, которая является значением элемента на доске.

Поэтому мы переформулируем вопрос, вместо этого мы собираемся пройти все узлы матрицы, требующие наименьшего количества времени, пока мы не достигнем [M][N]. До тех пор, пока они находятся в связи с тем, куда мы можем пойти в данный момент, мы будем продолжать обход, пока не достигнем [M][N].

1. Мы создадим очередь приоритетов для хранения всех узлов, которые нам нужно обойти. Как и в алгоритме Дейкстры, мы будем использовать Priority Queue для хранения узлов, которые нам нужно обойти первыми. (Сначала самый дешевый узел)
2. Мы также будем учитывать глобальную переменную time_passed. Это значение будет наибольшим значением глубины воды, которую мы посетили.
3. Поскольку мы знаем, что начинаем с [0][0], мы добавим его в Priority Queue со значением, равным тому, что находится в этом месте (обычно 0, но не стоит делать такое предположение).
4. Затем мы начнем выполнять алгоритм Дейкстры, в котором мы удалим самый «дешевый» элемент из Min-Heap и установим time_passed в значение этого элемента. Мы также добавим координаты элемента в visited Set().
5. Мы также попытаемся добавить узел выше, левее, правее и ниже в Min-Heap, если они находятся в границах матрицы и не посещены. При этом мы задаем приоритет как значение узла. Являясь значением элемента на доске. Таким образом, мы достигли эффекта, когда путешествуем только наименьшее количество времени.
6. Мы повторяем это, пока не достигнем [M][N]. В этот момент мы знаем, какое наибольшее значение глубины воды мы посетили, и это наш ответ.
7. ## Big O Notation:
8. Временная сложность: O(E * (log V)) | Правильно, это немного запутано. Алгоритм Дейкстры — это алгоритм O(ElogV). Где E — количество ребер в графе, а V — количество вершин в графе. Что представляется O(V^2), так как в худшем случае каждая вершина и ее соседи будут добавлены и удалены из Min-Heap несколько раз. Я считаю, что сложность этого алгоритма в реальном времени составляет O( (M x N) * (Log V)). Где M — количество строк, N — количество столбцов, а Log V — количество узлов, которые будут добавлены и удалены из кучи за логарифмическое время. Таким образом, мы можем сократить эту задачу до O(n (log n)).
9. Пространственная сложность: O(M x N)| Так как в худшем случае мы будем хранить всю матрицу в нашей Min-куче или в нашем посещенном множестве.

Может быть, мой анализ неверен? Возможно, не стесняйтесь, поправьте меня. 😁

Результаты Leetcode:

См. ссылку на представление:

Решение

/**
 * @param {number[][]} grid
 * @return {number}
 */
 var swimInWater = function (grid) {

    // We're going to use Dijkstra's algorithm to complete
    // to get from 0,0 to the end of the grid (Bottom Right).
    // We need to get from top left to bottom right 
    // in the shortest path. (Shortest in terms of the [i][x] value)

    // What this mean's is we will travel to the cheapest possible
    // operation relative the time passed. So at time 0, we can 
    // only travel to other 0 nodes that are in connection. Once it's 1, 
    // we can travel to other 1 nodes that are in connection. And so on and so on.

    // So instead of us manually passing time, we can use the value of the grid
    // to determine the time and the place within the queue. 

    // So, we add to a min-heap the [x,y] coordinates of the item in the grid
    // by the [x][y] value. So a grid item that is within reach and has a value
    // of 0, will be added to the top of the min-heap.


    let   time_passed = 0;                       // Max Priority of [Node] Visited
    const visit_set   = new Set();               // Don't want to visit the same node twice
    const min_heap    = new MinPriorityQueue();  // [i][x] = Priority / Time Passed

    // Min Maxes of grid and directions we can travel to.
    // Don't want to go out of bounds do we. 
    const max_rows   = grid.length - 1;
    const max_cols   = grid[0].length - 1;
    const directions = [
        [1, 0],
        [-1, 0],
        [0, 1],
        [0, -1],
    ];

    // So we firstly start off with the item in the top left corner.
    // Which could be any value. So we enqueue it as the first place to visit.
    min_heap.enqueue([0, 0], grid[0][0]); // Go to 0,0 at the cost of 0

    // While the heap is not empty and we have not reached the end of the grid.
    // Keep adding to the min-heap. 
    while (min_heap.size()) {

        // Pop node of our min heap.
        const node   = min_heap.dequeue();
        const cost   = node.priority;       // Time required to reach this node.
        const [x, y] = node.element;        // Coordinates of this node.

        // So we have not been here yet, mark it
        // We know this because, we never visit the same node twice. 
        visit_set.add(grid[x][y]);

        // So we're not at the target,
        // increment our result if we have increased.
        // As this mean's our shortest path time has increased and
        // thus so is the time passed. 
        time_passed = Math.max(cost, time_passed);

        // Are we at the target (Bottom Right of Grid)?
        // Meaning, we have found the shortest path?
        if (x === max_rows && y === max_cols) return time_passed;

        // Add the directions to the queue
        // if we have not already been there.
        //   ^
        // < x >
        //   v
        for (const direction of directions) {
            let [new_x, new_y]  = direction;
            new_x               += x; // Update x
            new_y               += y; // Update y

            // Is it out of bounds? Or we have visited it before?
            // If so, skip over this direction.
            if (new_x > max_rows || new_y > max_cols || new_x < 0 || new_y < 0 || visit_set.has(grid[new_x][new_y])) continue;

            // Enqueue the new node. Where the priority is the cost of the path.
            // Meaning, that once the time has become {x} we can visit it next. 
            min_heap.enqueue([new_x, new_y], grid[new_x][new_y]);
        }
    }    
};