▲

3

▼

🚶‍♂️ 0-1 BFS с двумя очередями: Оптимальное решение задачи минимизации препятствий

leetcoder, 28-11-2024 , 390

Очередная задача: 2290. Minimum Obstacle Removal to Reach Corner.

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

Дана двумерная матрица grid размером m x n, где каждая клетка может быть либо пустой (0), либо препятствием (1), которое можно удалить. Задача заключается в том, чтобы найти минимальное количество препятствий, которые нужно удалить, чтобы пройти из верхнего левого угла (0, 0) в нижний правый угол (m-1, n-1), передвигаясь только по пустым клеткам или удаляя препятствия.

🔑 Идея

Для решения задачи используем модификацию алгоритма поиска в ширину (BFS), который эффективно обрабатывает препятствия. Вместо приоритизации клеток по расстоянию, как в стандартном алгоритме Дейкстры, в 0-1 BFS (именно так эту модификацию принято называть) мы обрабатываем сначала пустые клетки, а затем клетки с препятствиями, что позволяет нам минимизировать количество удаляемых препятствий.

📋 Подробное описание подхода

1. Инициализация: Мы создаем две очереди: front и back. Во front помещаем клетки, которые можно пройти без удаления препятствий, а в back — клетки, для которых потребуется удалить препятствие.
2. Поиск в ширину (BFS):
   • Начинаем с верхнего левого угла и устанавливаем расстояние для этой клетки в 0 (т.е. препятствий еще не удалено).
   • Если клетка пустая (значение 0), мы добавляем её в front. Если клетка — препятствие (значение 1), то в back.
   • В процессе BFS мы сначала обрабатываем клетки из front (где можно пройти без удаления препятствий), а если front пуст, меняем местами front и back, чтобы продолжить обработку клеток с препятствиями.
3. Направления движения: Для каждой клетки мы проверяем все возможные направления (вверх, вниз, влево, вправо) и, если клетка в пределах границ и путь к ней более короткий, обновляем её расстояние.
4. Завершение: Алгоритм завершится, когда мы достигнем правого нижнего угла. Величина в массиве расстояний для этой клетки и будет минимальным количеством удаленных препятствий.

Сложность

• 🚀 Время выполнения:
  • Поиск в ширину: Каждая клетка обрабатывается ровно один раз.
  • Операции с очередями (добавление и удаление) занимают амортизированное время O(1).
  • Всего: Поскольку мы обрабатываем каждую клетку один раз и выполняем операции с деками за постоянное время, время работы алгоритма — O(m * n), где m и n — размеры матрицы.
• 📦 Используемая память:
  • Массив расстояний: Мы храним расстояние для каждой клетки, что требует O(m * n) памяти.
  • Двe очереди: В худшем случае обe очереди могут содержать все клетки, поэтому пространство, необходимое для их хранения, также O(m * n).

Исходный код решения

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

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

        // Distance array initialized to a large value
        let mut dist = vec![vec![i32::MAX; cols]; rows];

        // Two deques: front and back (we'll use Vec as Queue backbone for efficient push and pop)
        let mut front = Vec::new();
        let mut back = Vec::new();
        let mut front_idx = 0;

        // Start from the top-left corner (cellId = (0, 0))
        dist[0][0] = 0;
        front.push((0, 0)); // Add the (row, col) tuple for the starting point

        // Perform BFS
        while !front.is_empty() {
            while front_idx < front.len() {
                // Pop from the front slice (get the (row, col) tuple)
                let (row, col) = front.pop().unwrap();

                for (dr, dc) in &directions {
                    let new_row = row + dr;
                    let new_col = col + dc;

                    // Check if the new position is within bounds
                    if new_row >= 0 && new_row < rows as i32 && new_col >= 0 && new_col < cols as i32 {
                        let new_row = new_row as usize;
                        let new_col = new_col as usize;
                        let new_dist = dist[row as usize][col as usize] + grid[new_row][new_col];

                        // Update distance if a better path is found
                        if new_dist < dist[new_row][new_col] {
                            dist[new_row][new_col] = new_dist;
                            if grid[new_row][new_col] == 0 {
                                // Empty cell: push to the front slice
                                front.push((new_row as i32, new_col as i32));
                            } else {
                                // Obstacle cell: push to the back slice
                                back.push((new_row as i32, new_col as i32));
                            }
                        }
                    }
                }
            }
            // swap front and back
            std::mem::swap(&mut front, &mut back);
        }

        // Return the distance to the bottom-right cell
        dist[rows - 1][cols - 1]
    }
}

Замечание

Легко заметить, что в алгоритме вместо 2 очередей можно использовать 1 дек, в который очередные вершины пушить либо в начало (0), либо в конец (1).