главная новое лучшее написать
▲
3
▼

🌊 BFS для назначения высот на карте воды и суши с максимизацией высот
leetcoder, изменено 28-01-2025 , 462

В нашей новой задаче - 1765. Map of Highest Peak продолжим закреплять работу с семейством простых графовых алгоритмов.

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

Вам дана матрица isWater размером m×n, где:

Требуется назначить высоты каждой клетке таким образом, чтобы:

  1. Высота каждой клетки была неотрицательной.
  2. Высота любой клетки с водой была равна 0.
  3. Абсолютная разница высот у соседних клеток не превышала 1.
  4. Максимальная высота в назначенной карте была как можно больше.

💡 Идея

Мы используем поиск в ширину с несколькими источниками (multi-source BFS), начиная с клеток воды (высота 0).
На каждом шаге ближайшие клетки суши получают высоту на 1 больше текущей.
Этот метод гарантирует, что все клетки суши получают наилучшую из возможных высот, что приводит к максимизации самой высокой высоты в матрице.

🛠 Подробности подхода

  1. Инициализация:
    • Создаём очередь и добавляем в неё все клетки воды, помечая их высотой 0.
    • Все клетки суши помечаем как UNVISITED.
  2. BFS для расчёта высот:
    • Извлекаем клетку из очереди.
    • Для всех соседей проверяем, находятся ли они в пределах матрицы и не были ли посещены.
    • Если соседняя клетка не посещена, обновляем её высоту и добавляем в очередь.
  3. Возврат результата:
    • После завершения BFS возвращаем матрицу с рассчитанными высотами.

⏱ Асимптотика

📜 Исходный код

use std::collections::VecDeque;

// Manages BFS logic, including queue operations and height map updates.
struct BFSStrategy<'a> {
    queue: &'a mut VecDeque<(usize, usize)>,
    height_map: &'a mut Vec<Vec<i32>>,
    rows: i32, cols: i32,
}

impl Solution {
    pub fn highest_peak(is_water: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let m = is_water.len();
        let n = is_water[0].len();

        let mut height_map = vec![vec![BFSStrategy::UNVISITED; n]; m];
        let mut queue = VecDeque::new();

        // Add water cells to the queue and initialize their height to 0.
        for row in 0..m {
            for col in 0..n {
                if is_water[row][col] == 1 {
                    height_map[row][col] = 0;
                    queue.push_back((row, col));
                }
            }
        }

        let mut bfs = BFSStrategy {
            queue: &mut queue,
            height_map: &mut height_map,
            rows: m as i32, cols: n as i32,
        };

        // Perform BFS to compute heights for all cells.
        while let Some((row, col)) = bfs.queue.pop_front() {
            let current_height = bfs.height_map[row][col];
            bfs.enqueue(row as i32 + 1, col as i32, current_height + 1);
            bfs.enqueue(row as i32 - 1, col as i32, current_height + 1);
            bfs.enqueue(row as i32, col as i32 + 1, current_height + 1);
            bfs.enqueue(row as i32, col as i32 - 1, current_height + 1);
        }

        height_map
    }
}

impl<'a> BFSStrategy<'a> {
    /// Adds a cell to the queue if it's valid and unvisited.
    fn enqueue(&mut self, row: i32, col: i32, height: i32) {
        if (0..self.rows).contains(&row) && (0..self.cols).contains(&col) {
            let row = row as usize;
            let col = col as usize;
            if self.height_map[row][col] == Self::UNVISITED {
                self.height_map[row][col] = height;
                self.queue.push_back((row, col));
            }
        }
    }

    const UNVISITED: i32 = -1; // Marks cells that haven't been processed.
}

Tags:  #rust #algorithms #maps #bfs