Regions cut by slashes

Array Hash Table Depth-First Search Breadth-First Search Union-Find Matrix

77.5% acceptance

Feb 25, 2026

3983

872

An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a '/', '\', or blank space ' '. These characters divide the square into contiguous regions. Given the grid grid represented as a string array, return the number of regions. Note that backslash characters are escaped, so a '\' is represented as '\\'.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn regions_by_slashes(grid: Vec<String>) -> i32 {
    let n = grid.len();
    // Each cell has 4 triangles: 0=top, 1=right, 2=bottom, 3=left
    let total = n * n * 4;
    let mut parent: Vec<usize> = (0..total).collect();
    fn find(p: &mut Vec<usize>, x: usize) -> usize {
      if p[x] != x { p[x] = find(p, p[x]); }
      p[x]
    }
    fn union(p: &mut Vec<usize>, x: usize, y: usize) {
      let px = find(p, x); let py = find(p, y);
      if px != py { p[px] = py; }
    }
    let idx = |r: usize, c: usize, t: usize| (r * n + c) * 4 + t;
    let grid: Vec<Vec<u8>> = grid.iter().map(|r| r.bytes().collect()).collect();
    for r in 0..n {
      for c in 0..n {
        match grid[r][c] {
          b'/' => {
            union(&mut parent, idx(r,c,0), idx(r,c,3));
            union(&mut parent, idx(r,c,1), idx(r,c,2));
          }
          b'\\' => {
            union(&mut parent, idx(r,c,0), idx(r,c,1));
            union(&mut parent, idx(r,c,2), idx(r,c,3));
          }
          _ => {
            union(&mut parent, idx(r,c,0), idx(r,c,1));
            union(&mut parent, idx(r,c,1), idx(r,c,2));
            union(&mut parent, idx(r,c,2), idx(r,c,3));
          }
        }
        // Connect with right neighbor
        if c + 1 < n { union(&mut parent, idx(r,c,1), idx(r,c+1,3)); }
        // Connect with bottom neighbor
        if r + 1 < n { union(&mut parent, idx(r,c,2), idx(r+1,c,0)); }
      }
    }
    let mut roots = std::collections::HashSet::new();
    for i in 0..total { roots.insert(find(&mut parent, i)); }
    roots.len() as i32
  }
}