LeetCode: FloodFill Rust

Question

Hola, estoy implementando algunos ejemplos de leetcode en Rust. https://leetcode.com/problems/flood-fill/

(parece ser la misma pregunta que LeetCode: FloodFill C # )

La entrada es una matriz, una posición y su nuevo color. La salida es la matriz modificada

// Input: 
// image = [[1,1,1],[1,1,0],[1,0,1]]
// sr = 1, sc = 1, newColor = 2
// Output: [[2,2,2],[2,2,0],[2,0,1]]
// Explanation: 
// From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected 
// by a path of the same color as the starting pixel are colored with the new color.
// Note the bottom corner is not colored 2, because it is not 4-directionally connected
// to the starting pixel.

Yo suelo q.pop_front()llenar primero las celdas vecinas. ¿Es VecDequela mejor estructura de datos para esta cola?

Hago muchas conversiones desde el medio i32y usizequiero poder verificar si el índice está fuera de los límites restando 1. ¿Hay una manera mejor?

¿Es if (0..image.len()).contains(x1)mejor que if x1>=0 && x1<image.len()para la verificación de alcance?

use std::collections::VecDeque;

  fn flood_fill(mut image: Vec<Vec<i32>>, sr: i32, sc: i32, new_color: i32) -> Vec<Vec<i32>> {

      let mut q:VecDeque<(i32,i32)> = VecDeque::new();
      q.push_back((sr,sc));

      let c0 = image[sr as usize][sc as usize];
      if c0 != new_color {
          while ! q.is_empty() {
              if let Some((sr,sc))=q.pop_front() {  
                  if image[sr as usize][sc as usize] == c0 {
                      image[sr as usize][sc as usize] = new_color;
                      for delta in vec![(-1,0),(1,0),(0,-1),(0,1)] {
                          let new_r:i32 = sr+delta.0;
                          let new_c:i32 = sc+delta.1;
                          if (0..image.len() as i32).contains( &new_r ) && (0..image[0].len() as i32).contains( &new_c){
                              q.push_back((new_r,new_c));
                          }
                      }
                  }
              }
          }
      }
      image
  }

#[cfg(test)]
mod test{
#[test]
    fn test_lc_default(){
        assert_eq!(super::flood_fill(vec![vec![1 as i32 ,1,1],vec![1,1 as i32,0],vec![1,0,1]],1, 1, 2),vec![vec![2,2,2],vec![2,2,0],vec![2,0,1]]) ;
    }
}

Parece que también podría usar algo de optimización de memoria.

Answer 1

Formateo

Supongo que la sangría es un error de copiar y pegar al eliminar el texto estándar struct Solutionexigido por LeetCode.

Ejecute cargo fmtsu código para cumplir con las pautas de formato estándar de Rust.

Interfaz

LeetCode tomó una mala elección al usar Vec<Vec<i32>>para representar una matriz bidimensional, que generalmente es ineficiente ya que almacena elementos en múltiples asignaciones segmentadas, incurre en costos dobles de indirección y no mantiene la estructura adecuada (contra matrices irregulares). Sin embargo, no podemos hacer nada en contra de esto, así que lo ignoraré durante el resto de la publicación.

Del mismo modo, i32no es ideal para la representación del color: un tipo dedicado (por ejemplo, struct Color(i32);) es claramente superior. Como mínimo, de alguna manera podemos mejorar la legibilidad mediante el uso de un alias de tipo y usarlo de manera consistente para los colores en el código:

type Color = i32;

i32 vs. usize

Generalmente, se prefiere almacenar y calcular índices en usize, que es el tipo natural para este propósito. Una forma de evitar restar 1es usando usize::MAXy wrapping_add.

Se prefiere convertir a partir de los i32valores que recibe la función , ya que esta última trunca silenciosamente los valores no válidos. se puede usar aquí ya que es para LeetCode; en código del mundo real, el error debe manejarse en consecuencia.try_fromasunwrap

¿Es if (0..image.len()).contains(x1)mejor que if x1>=0 && x1<image.len()para la verificación de alcance?

Yo diría que sí. Indica la intención con mayor claridad.

Simplificando el flujo de control

En lugar de envolver todo en una ifexpresión, verifique image[sr][sc] == new_colory regrese temprano.

while let

Esta:

while !cells.is_empty() {
    if let Some((sr, sc)) = cells.pop_front() {

es solo una forma complicada de decir

while let Some((sr, sc)) = cells.pop_front() {

---

Así es como modifiqué su implementación:

type Color = i32;

pub fn flood_fill(
    mut image: Vec<Vec<Color>>,
    sr: i32,
    sc: i32,
    new_color: Color,
) -> Vec<Vec<Color>> {
    use std::collections::VecDeque;
    use std::convert::TryFrom;

    let sr = usize::try_from(sr).unwrap();
    let sc = usize::try_from(sc).unwrap();

    let initial_color = image[sr][sc];

    if initial_color == new_color {
        return image;
    }

    let height = image.len();
    let width = image[0].len();

    let mut cells: VecDeque<(usize, usize)> = VecDeque::new();
    cells.push_back((sr, sc));

    while let Some((sr, sc)) = cells.pop_front() {
        let cell = &mut image[sr][sc];

        if *cell != initial_color {
            continue;
        }

        *cell = new_color;

        const OFFSETS: &[(usize, usize)] = &[(0, usize::MAX), (usize::MAX, 0), (0, 1), (1, 0)];

        for (delta_r, delta_c) in OFFSETS.iter().copied() {
            let new_r = sr.wrapping_add(delta_r);
            let new_c = sc.wrapping_add(delta_c);

            if new_r < height && new_c < width {
                cells.push_back((new_r, new_c));
            }
        }
    }

    image
}