LeetCode: FloodFill Rust

Question

Salve, sto implementando alcuni esempi di leetcode in Rust. https://leetcode.com/problems/flood-fill/

(sembra essere la stessa domanda di LeetCode: FloodFill C # )

L'input è una matrice, una posizione e il suo nuovo colore. L'output è la matrice modificata

// 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.

Io uso q.pop_front()per riempire prima le celle vicine. La VecDequemigliore struttura dati per questa coda?

Faccio un sacco di casting tra i32e usizeperché voglio essere in grado di controllare se l'indice è fuori dai limiti sottraendo 1. C'è un modo migliore?

È if (0..image.len()).contains(x1)meglio che if x1>=0 && x1<image.len()per il controllo della portata?

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]]) ;
    }
}

Sembra che potrei usare anche un po 'di ottimizzazione della memoria.

Answer 1

Formattazione

Presumo che il rientro sia un errore di copia-incolla durante la rimozione del boilerplate struct Solutionrichiesto da LeetCode.

Esegui cargo fmtil tuo codice per conformarti alle linee guida di formattazione Rust standard.

Interfaccia

LeetCode ha fatto una scelta sbagliata utilizzando Vec<Vec<i32>>per rappresentare un array bidimensionale, che è generalmente inefficiente in quanto memorizza elementi in più allocazioni segmentate, incorre in doppi costi indiretti e non riesce a mantenere una struttura corretta (contro array frastagliati). Non possiamo fare nulla contro questo, però, quindi lo ignorerò per il resto del post.

Allo stesso modo, i32non è l'ideale per la rappresentazione del colore: un tipo dedicato (ad esempio struct Color(i32);) è chiaramente superiore. Per lo meno, possiamo in qualche modo migliorare la leggibilità usando un alias di tipo e usarlo in modo coerente per i colori nel codice:

type Color = i32;

i32 vs. usize

In generale, è preferibile archiviare e calcolare gli indici in usize, che è il tipo naturale per questo scopo. Un modo per evitare la sottrazione 1è usare usize::MAXe wrapping_add.

È preferibile convertire dai i32valori ricevuti dalla funzione , poiché quest'ultima tronca silenziosamente i valori non validi. può essere usato qui poiché è per LeetCode; nel codice del mondo reale, l'errore dovrebbe essere gestito di conseguenza.try_fromasunwrap

È if (0..image.len()).contains(x1)meglio che if x1>=0 && x1<image.len()per il controllo della portata?

Direi di si. Indica l'intento più chiaramente.

Semplificazione del flusso di controllo

Invece di racchiudere tutto in ifun'espressione, controlla image[sr][sc] == new_colore torna presto.

while let

Questo:

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

è solo un modo contorto di dire

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

---

Ecco come ho modificato la tua implementazione:

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
}