Created
September 14, 2020 00:22
-
-
Save ChunMinChang/a851138142bd69b1cc7e3b01c0eb90c3 to your computer and use it in GitHub Desktop.
Fill the region formed by same-color cell with a new color
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#[derive(Clone, Debug, PartialEq)] | |
enum Color { | |
R, | |
Y, | |
G, | |
} | |
#[derive(Clone, PartialEq)] | |
enum Direction { | |
Up, | |
Right, | |
Down, | |
Left, | |
} | |
#[derive(Clone, Copy, Debug, PartialEq)] | |
struct Coordinate { | |
row: usize, | |
col: usize, | |
} | |
impl Coordinate { | |
fn new(row: usize, col: usize) -> Self { | |
Self { row, col } | |
} | |
fn get_neighbor(&self, dir: Direction, border: (usize, usize)) -> Option<Self> { | |
let (row, col, overflow) = match dir { | |
Direction::Up => { | |
let (row, overflow) = self.row.overflowing_sub(1); | |
(row, self.col, overflow) | |
} | |
Direction::Right => { | |
let (col, overflow) = self.col.overflowing_add(1); | |
(self.row, col, overflow) | |
} | |
Direction::Down => { | |
let (row, overflow) = self.row.overflowing_add(1); | |
(row, self.col, overflow) | |
} | |
Direction::Left => { | |
let (col, overflow) = self.col.overflowing_sub(1); | |
(self.row, col, overflow) | |
} | |
}; | |
if overflow || row >= border.0 || col >= border.1 { | |
None | |
} else { | |
Some(Self { row, col }) | |
} | |
} | |
} | |
fn fill_region(m: &mut [Vec<Color>], pos: &Coordinate, color: Color) { | |
use crate::Direction::*; | |
use std::collections::VecDeque; | |
assert!(!m.is_empty() && !m[0].is_empty()); | |
assert!(pos.row < m.len() && pos.col < m[0].len()); | |
if m[pos.row][pos.col] == color { | |
return; | |
} | |
let current_color = m[pos.row][pos.col].clone(); | |
let mut queue = VecDeque::new(); | |
queue.push_back(*pos); | |
m[pos.row][pos.col] = color.clone(); | |
const DIRS: [Direction; 4] = [Up, Right, Down, Left]; | |
while !queue.is_empty() { | |
let p = queue.pop_front().unwrap(); | |
for dir in DIRS.iter() { | |
if let Some(neighbor) = p.get_neighbor(dir.clone(), (m.len(), m[0].len())) { | |
if m[neighbor.row][neighbor.col] == current_color { | |
queue.push_back(neighbor); | |
m[neighbor.row][neighbor.col] = color.clone(); | |
} | |
} | |
} | |
} | |
} | |
fn main() { | |
use crate::Color::*; | |
let mut map = vec![ | |
vec![R, R, G, G, R], | |
vec![R, G, R, G, R], | |
vec![G, G, R, R, R], | |
vec![R, R, R, G, G], | |
vec![R, R, G, R, R], | |
]; | |
let start = Coordinate::new(2, 2); | |
fill_region(&mut map[..], &start, Y); | |
println!("{:?}", map); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment