LeetCode: FloodFill Rust

Question

Olá, estou implementando alguns exemplos de leetcode no Rust. https://leetcode.com/problems/flood-fill/

(parece ser a mesma pergunta que LeetCode: FloodFill C # )

A entrada é uma matriz, uma posição e sua nova cor. O resultado é a 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.

Eu uso q.pop_front()para preencher as células vizinhas primeiro. É VecDequea melhor estrutura de dados para isso?

Eu faço muito cast entre i32e usizeporque quero poder verificar se o índice está fora dos limites subtraindo 1. Existe uma maneira melhor?

É if (0..image.len()).contains(x1)melhor do que if x1>=0 && x1<image.len()para a verificação 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 também preciso de alguma otimização de memória.

Answer 1

Formatação

Presumo que a indentação seja um erro de copiar e colar ao remover o clichê struct Solutionexigido por LeetCode.

Execute cargo fmtem seu código para estar em conformidade com as diretrizes de formatação padrão do Rust.

Interface

O LeetCode fez uma escolha ruim ao usar Vec<Vec<i32>>para representar uma matriz bidimensional, que geralmente é ineficiente, pois armazena elementos em várias alocações segmentadas, incorre em custos indiretos duplos e falha em manter a estrutura adequada (contra matrizes irregulares). Não podemos fazer nada contra isso, então vou ignorar pelo resto do post.

Da mesma forma, i32não é ideal para representação de cores - um tipo dedicado (por exemplo, struct Color(i32);) é claramente superior. No mínimo, podemos melhorar de alguma forma a legibilidade usando um alias de tipo e usá-lo consistentemente para cores no código:

type Color = i32;

i32 vs. usize

Geralmente, é preferível armazenar e calcular índices em usize, que é o tipo natural para esse propósito. Uma maneira de evitar a subtração 1é usando usize::MAXe wrapping_add.

Para converter a partir dos i32valores que a função recebe, try_fromé preferível as, pois o último trunca silenciosamente os valores inválidos. unwrappode ser usado aqui, pois é para LeetCode; no código do mundo real, o erro deve ser tratado de acordo.

É if (0..image.len()).contains(x1)melhor do que if x1>=0 && x1<image.len()para a verificação de alcance?

Eu diria que sim. Indica a intenção com mais clareza.

Simplificando o fluxo de controle

Em vez de envolver tudo em uma ifexpressão, verifique image[sr][sc] == new_colore retorne mais cedo.

while let

Este:

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

é apenas uma forma complicada de dizer

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

---

Veja como modifiquei sua implementação:

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
}