⏳🚪 Алгоритм Дейкстры для скорейшего прохождения матрицы

leetcoder, 29-11-2024 ,

388

Сегодня нам предстоит решить задачу 2577. Minimum Time to Visit a Cell In a Grid.

📝 Описание задачи

Дана матрица grid размером m x n, где каждая ячейка (row, col) содержит время открытия ворот, ведущих в эту ячейку. До этого времени в ячейку попасть нельзя.
Вы начинаете в ячейке (0, 0) с временем 0 и можете двигаться на 1 ячейку за секунду в любом из 4 направлений (вверх, вниз, влево, вправо).
Важно: стоять на месте запрещено — вы должны перемещаться на каждое движение.
Цель — найти минимальное время, чтобы добраться до ячейки (m-1, n-1). Если это невозможно, вернуть -1.

💡 Идея

Задача сводится к поиску кратчайшего пути с учётом времени открытия ворот в каждой ячейке. Можно представить задачу как динамический граф, где вершины — это пары (время, ячейка), а рёбра — это возможные переходы между ячейками. Вместо того чтобы хранить весь граф, мы динамически вычисляем возможные переходы из посещаемых вершин. Вершины будем перебирать в порядке времён достижимости ячейки (как в алгоритме Дейкстры).

🔑 Подход к решению

🧑‍💻 Графовая модель:
- Ячейки матрицы — вершины графа.
- Рёбра между вершинами имеют вес 1.
- Время в каждой ячейке ограничивает, когда в неё можно попасть. То есть, для ячейки (i, j) нужно дождаться времени grid[i][j], чтобы войти в неё.
🚀 Использование Дейкстры:
- Для поиска минимального времени до ячейки (m-1, n-1) используем алгоритм Дейкстры.
- Вместо хранения всего графа, мы динамически пересчитываем возможные пути в каждой итерации, всегда выбирая ячейку с минимальным временем.
⏳ Учёт времени открытия ворот:
- Если время перемещения в ячейку меньше, чем время открытия ворот (current_time + 1 < grid[row][col]), то необходимо подождать, чтобы попасть внутрь.
- С учётом невозможности стоять на месте, оптимальным решением является циклическое «шагание» назад-вперёд — это позволяет добиться нужного времени при переходе в ячейку.
- Для вычисления оптимального времени ожидания используется следующая формула, которая позволяет эффективно вычислять необходимое время с учётом чётности (Такая оптимизация помогает точно рассчитать время без лишних вычислений, избегая ненужных задержек):
  
  nextTime = grid[row][col] + ((grid[row][col] - (current_time + 1)) % 2)
🔄 Обход соседей:
- Для каждой соседней ячейки проверяем, возможно ли в неё попасть. Если новое время прихода меньше ранее известного, обновляем его и добавляем ячейку в очередь.
⚠️ Крайне случаи:
- Если из стартовой ячейки нельзя выйти (например, если все соседи закрыты), возвращаем -1.

📊 Сложность

Время: O(m × n × log(m × n))
- каждая ячейка обрабатывается один раз, операции с очередью выполняются за логарифмическое время.
Память: O(m × n)
- для хранения очереди и отметок посещённых ячеек.

Исходный код

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
    pub fn minimum_time(grid: Vec<Vec<i32>>) -> i32 {
        let rows = grid.len();
        let cols = grid[0].len();

        // Check edge case: if the starting cell is unreachable
        if grid[0][1] > 1 && grid[1][0] > 1 {
            return -1;
        }

        // Directions for moving: up, down, left, and right
        let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)];

        // Priority queue for Dijkstra's algorithm
        let mut pq = BinaryHeap::new();
        // Minimum time to reach each cell
        let mut time = vec![vec![i32::MAX; cols]; rows];

        // Start from the top-left corner with time 0
        time[0][0] = 0;
        pq.push(Reverse((0, 0, 0))); // (time, row, col)

        while let Some(Reverse((current_time, row, col))) = pq.pop() {
            // If we reach the bottom-right corner, return the time
            if row == rows - 1 && col == cols - 1 {
                return current_time;
            }

            // Skip if this time is outdated (not the minimum time for this cell)
            if current_time > time[row][col] {
                continue;
            }

            // Explore all adjacent cells
            for &(dr, dc) in &directions {
                let next_row = row as i32 + dr;
                let next_col = col as i32 + dc;

                if next_row >= 0 && next_row < rows as i32 && next_col >= 0 && next_col < cols as i32 {
                    let next_row = next_row as usize;
                    let next_col = next_col as usize;

                    // Calculate the minimum time to enter the next cell
                    let mut next_time = current_time + 1;
                    if next_time < grid[next_row][next_col] {
                        next_time = grid[next_row][next_col] + ((grid[next_row][next_col] ^ next_time) & 1);
                    }

                    // Update if a faster route to the next cell is found
                    if next_time < time[next_row][next_col] {
                        time[next_row][next_col] = next_time;
                        pq.push(Reverse((next_time, next_row, next_col)));
                    }
                }
            }
        }

        // If the bottom-right corner is unreachable, return -1
        -1
    }
}

💾 Полезное замечание:

В языках программирования, где матрица grid приходит изменяемым массивом, можно обойтись без дополнительной таблицы time. Вместо этого метки достижимости можно хранить непосредственно в самой таблице grid после посещения ячейки.