Multi source flood fill

Array Breadth-First Search Matrix

56.0% acceptance

May 13, 2026

You are given two integers n and m representing the number of rows and columns of a grid, respectively. You are also given a 2D integer array sources, where sources[i] = [ri, ci, colori] indicates that the cell (ri, ci) is initially colored with colori. All other cells are initially uncolored and represented as 0. At each time step, every currently colored cell spreads its color to all adjacent uncolored cells in the four directions: up, down, left, and right. All spreads happen simultaneously. If multiple colors reach the same uncolored cell at the same time step, the cell takes the color with the maximum value. The process continues until no more cells can be colored. Return a 2D integer array representing the final state of the grid, where each cell contains its final color.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn color_grid(n: i32, m: i32, sources: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = n as usize;
    let m = m as usize;
    let mut grid = vec![vec![0i32; m]; n];
    let mut dist = vec![vec![-1i32; m]; n];
    let mut cur: Vec<(usize, usize)> = Vec::new();
    for s in &sources {
      let r = s[0] as usize;
      let c = s[1] as usize;
      let col = s[2];
      grid[r][c] = grid[r][c].max(col);
      if dist[r][c] == -1 {
        dist[r][c] = 0;
        cur.push((r, c));
      }
    }
    let dirs: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
    while !cur.is_empty() {
      let mut next_layer: Vec<(usize, usize)> = Vec::new();
      for &(r, c) in &cur {
        let cur_d = dist[r][c];
        let cur_col = grid[r][c];
        for &(dr, dc) in &dirs {
          let nr = r as i32 + dr;
          let nc = c as i32 + dc;
          if nr < 0 || nc < 0 || nr >= n as i32 || nc >= m as i32 { continue; }
          let nr = nr as usize;
          let nc = nc as usize;
          if dist[nr][nc] == -1 {
            dist[nr][nc] = cur_d + 1;
            grid[nr][nc] = cur_col;
            next_layer.push((nr, nc));
          } else if dist[nr][nc] == cur_d + 1 {
            if cur_col > grid[nr][nc] {
              grid[nr][nc] = cur_col;
            }
          }
        }
      }
      cur = next_layer;
    }
    grid
  }
}