1034. Coloring A Border

Given a 2-dimensional grid of integers, each value in the grid represents the color of the grid square at that location.

Two squares belong to the same connected component if and only if they have the same color and are next to each other in any of the 4 directions.

The border of a connected component is all the squares in the connected component that are either 4-directionally adjacent to a square not in the component, or on the boundary of the grid (the first or last row or column).

Given a square at location (r0, c0) in the grid and a color, color the border of the connected component of that square with the given color, and return the final grid.

 

Example 1:

Input: grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3
Output: [[3, 3], [3, 2]]

Example 2:

Input: grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3
Output: [[1, 3, 3], [2, 3, 3]]

Example 3:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2
Output: [[2, 2, 2], [2, 1, 2], [2, 2, 2]]

 

Note:

  1. 1 <= grid.length <= 50
  2. 1 <= grid[0].length <= 50
  3. 1 <= grid[i][j] <= 1000
  4. 0 <= r0 < grid.length
  5. 0 <= c0 < grid[0].length
  6. 1 <= color <= 1000

Rust Solution

struct Solution;

impl Solution {
    fn color_border(mut grid: Vec<Vec<i32>>, r0: i32, c0: i32, color: i32) -> Vec<Vec<i32>> {
        let n = grid.len();
        let m = grid[0].len();
        let r0 = r0 as usize;
        let c0 = c0 as usize;
        let c_color = grid[r0][c0];
        let b_color = color;
        let mut visited: Vec<Vec<bool>> = vec![vec![false; m]; n];
        Self::dfs(r0, c0, &mut visited, &mut grid, b_color, c_color, n, m);
        grid
    }
    fn dfs(
        i: usize,
        j: usize,
        visited: &mut [Vec<bool>],
        grid: &mut [Vec<i32>],
        b_color: i32,
        c_color: i32,
        n: usize,
        m: usize,
    ) {
        visited[i][j] = true;
        let top = if i == 0 {
            true
        } else {
            if grid[i - 1][j] != c_color {
                !visited[i - 1][j]
            } else {
                if !visited[i - 1][j] {
                    Self::dfs(i - 1, j, visited, grid, b_color, c_color, n, m);
                }
                false
            }
        };
        let left = if j == 0 {
            true
        } else {
            if grid[i][j - 1] != c_color {
                !visited[i][j - 1]
            } else {
                if !visited[i][j - 1] {
                    Self::dfs(i, j - 1, visited, grid, b_color, c_color, n, m);
                }
                false
            }
        };
        let down = if i + 1 == n {
            true
        } else {
            if grid[i + 1][j] != c_color {
                !visited[i + 1][j]
            } else {
                if !visited[i + 1][j] {
                    Self::dfs(i + 1, j, visited, grid, b_color, c_color, n, m);
                }
                false
            }
        };
        let right = if j + 1 == m {
            true
        } else {
            if grid[i][j + 1] != c_color {
                !visited[i][j + 1]
            } else {
                if !visited[i][j + 1] {
                    Self::dfs(i, j + 1, visited, grid, b_color, c_color, n, m);
                }
                false
            }
        };
        if top || left || down || right {
            grid[i][j] = b_color;
        }
    }
}

#[test]
fn test() {
    let grid = vec_vec_i32![[1, 1], [1, 2]];
    let r0 = 0;
    let c0 = 0;
    let color = 3;
    let res = vec_vec_i32![[3, 3], [3, 2]];
    assert_eq!(Solution::color_border(grid, r0, c0, color), res);
    let grid = vec_vec_i32![[1, 2, 2], [2, 3, 2]];
    let r0 = 0;
    let c0 = 1;
    let color = 3;
    let res = vec_vec_i32![[1, 3, 3], [2, 3, 3]];
    assert_eq!(Solution::color_border(grid, r0, c0, color), res);
    let grid = vec_vec_i32![[1, 1, 1], [1, 1, 1], [1, 1, 1]];
    let r0 = 1;
    let c0 = 1;
    let color = 2;
    let res = vec_vec_i32![[2, 2, 2], [2, 1, 2], [2, 2, 2]];
    assert_eq!(Solution::color_border(grid, r0, c0, color), res);
}

Having problems with this solution? Click here to submit an issue on github.