Skip to content

Instantly share code, notes, and snippets.

@ChunMinChang
Created September 14, 2020 00:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ChunMinChang/a851138142bd69b1cc7e3b01c0eb90c3 to your computer and use it in GitHub Desktop.
Save ChunMinChang/a851138142bd69b1cc7e3b01c0eb90c3 to your computer and use it in GitHub Desktop.
Fill the region formed by same-color cell with a new color
#[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