Regions Cut by Slashes — DSA · Engineering Playbook

Problem#

A grid of strings contains ' ', '/', and '\\'. Each character is a cell of an n x n grid; slashes split cells into pieces. Return the total number of distinct regions formed.

Examples#

[" /","/ "] → 2.
[" /"," "] → 1.
["\\/","/\\"] → 5.

Constraints#

1 <= n <= 30.

Hints#

Hint

Split each cell into 4 triangles (top, right, bottom, left). Union triangles within a cell based on the character; union across neighboring cells on shared edges.

Approach#

Each cell (r, c) becomes 4 DSU nodes: T, R, B, L. Indexed as (r * n + c) * 4 + k. Within a cell: ' ' unions all four; '/' unions T with L, B with R; '\\' unions T with R, B with L. Across cells: B of (r, c) with T of (r+1, c); R of (r, c) with L of (r, c+1). Count distinct roots.

Solution#

class Solution {
    vector<int> parent;
    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
    void unite(int a, int b) { parent[find(a)] = find(b); }
public:
    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        parent.resize(4 * n * n);
        iota(parent.begin(), parent.end(), 0);
        auto id = [&](int r, int c, int k) { return (r * n + c) * 4 + k; };
        // k: 0=T, 1=R, 2=B, 3=L
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                char ch = grid[r][c];
                if (ch == ' ') {
                    unite(id(r,c,0), id(r,c,1));
                    unite(id(r,c,1), id(r,c,2));
                    unite(id(r,c,2), id(r,c,3));
                } else if (ch == '/') {
                    unite(id(r,c,0), id(r,c,3));
                    unite(id(r,c,1), id(r,c,2));
                } else { // '\\'
                    unite(id(r,c,0), id(r,c,1));
                    unite(id(r,c,2), id(r,c,3));
                }
                if (r + 1 < n) unite(id(r,c,2), id(r+1,c,0));
                if (c + 1 < n) unite(id(r,c,1), id(r,c+1,3));
            }
        }
        unordered_set<int> roots;
        for (int i = 0; i < (int)parent.size(); ++i) roots.insert(find(i));
        return roots.size();
    }
};

func regionsBySlashes(grid []string) int {
    n := len(grid)
    parent := make([]int, 4*n*n)
    for i := range parent {
        parent[i] = i
    }
    var find func(x int) int
    find = func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
    unite := func(a, b int) {
        parent[find(a)] = find(b)
    }
    id := func(r, c, k int) int { return (r*n+c)*4 + k }
    // k: 0=T, 1=R, 2=B, 3=L
    for r := 0; r < n; r++ {
        for c := 0; c < n; c++ {
            ch := grid[r][c]
            switch ch {
            case ' ':
                unite(id(r, c, 0), id(r, c, 1))
                unite(id(r, c, 1), id(r, c, 2))
                unite(id(r, c, 2), id(r, c, 3))
            case '/':
                unite(id(r, c, 0), id(r, c, 3))
                unite(id(r, c, 1), id(r, c, 2))
            default: // '\\'
                unite(id(r, c, 0), id(r, c, 1))
                unite(id(r, c, 2), id(r, c, 3))
            }
            if r+1 < n {
                unite(id(r, c, 2), id(r+1, c, 0))
            }
            if c+1 < n {
                unite(id(r, c, 1), id(r, c+1, 3))
            }
        }
    }
    roots := map[int]bool{}
    for i := 0; i < len(parent); i++ {
        roots[find(i)] = true
    }
    return len(roots)
}

from typing import List

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        n = len(grid)
        parent = list(range(4 * n * n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def unite(a: int, b: int) -> None:
            parent[find(a)] = find(b)

        def idx(r: int, c: int, k: int) -> int:
            return (r * n + c) * 4 + k

        # k: 0=T, 1=R, 2=B, 3=L
        for r in range(n):
            for c in range(n):
                ch = grid[r][c]
                if ch == ' ':
                    unite(idx(r, c, 0), idx(r, c, 1))
                    unite(idx(r, c, 1), idx(r, c, 2))
                    unite(idx(r, c, 2), idx(r, c, 3))
                elif ch == '/':
                    unite(idx(r, c, 0), idx(r, c, 3))
                    unite(idx(r, c, 1), idx(r, c, 2))
                else:  # '\\'
                    unite(idx(r, c, 0), idx(r, c, 1))
                    unite(idx(r, c, 2), idx(r, c, 3))
                if r + 1 < n:
                    unite(idx(r, c, 2), idx(r + 1, c, 0))
                if c + 1 < n:
                    unite(idx(r, c, 1), idx(r, c + 1, 3))

        roots = set()
        for i in range(len(parent)):
            roots.add(find(i))
        return len(roots)

function regionsBySlashes(grid) {
    const n = grid.length;
    const parent = new Array(4 * n * n);
    for (let i = 0; i < parent.length; i++) parent[i] = i;
    const find = (x) => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    const unite = (a, b) => { parent[find(a)] = find(b); };
    const id = (r, c, k) => (r * n + c) * 4 + k;
    // k: 0=T, 1=R, 2=B, 3=L
    for (let r = 0; r < n; r++) {
        for (let c = 0; c < n; c++) {
            const ch = grid[r][c];
            if (ch === ' ') {
                unite(id(r, c, 0), id(r, c, 1));
                unite(id(r, c, 1), id(r, c, 2));
                unite(id(r, c, 2), id(r, c, 3));
            } else if (ch === '/') {
                unite(id(r, c, 0), id(r, c, 3));
                unite(id(r, c, 1), id(r, c, 2));
            } else { // '\\'
                unite(id(r, c, 0), id(r, c, 1));
                unite(id(r, c, 2), id(r, c, 3));
            }
            if (r + 1 < n) unite(id(r, c, 2), id(r + 1, c, 0));
            if (c + 1 < n) unite(id(r, c, 1), id(r, c + 1, 3));
        }
    }
    const roots = new Set();
    for (let i = 0; i < parent.length; i++) roots.add(find(i));
    return roots.size;
}

class Solution {
    private int[] parent;
    private int n;

    public int regionsBySlashes(String[] grid) {
        n = grid.length;
        parent = new int[4 * n * n];
        for (int i = 0; i < parent.length; i++) parent[i] = i;
        // k: 0=T, 1=R, 2=B, 3=L
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                char ch = grid[r].charAt(c);
                if (ch == ' ') {
                    unite(id(r, c, 0), id(r, c, 1));
                    unite(id(r, c, 1), id(r, c, 2));
                    unite(id(r, c, 2), id(r, c, 3));
                } else if (ch == '/') {
                    unite(id(r, c, 0), id(r, c, 3));
                    unite(id(r, c, 1), id(r, c, 2));
                } else { // '\\'
                    unite(id(r, c, 0), id(r, c, 1));
                    unite(id(r, c, 2), id(r, c, 3));
                }
                if (r + 1 < n) unite(id(r, c, 2), id(r + 1, c, 0));
                if (c + 1 < n) unite(id(r, c, 1), id(r, c + 1, 3));
            }
        }
        Set<Integer> roots = new HashSet<>();
        for (int i = 0; i < parent.length; i++) roots.add(find(i));
        return roots.size();
    }

    private int id(int r, int c, int k) { return (r * n + c) * 4 + k; }

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    private void unite(int a, int b) { parent[find(a)] = find(b); }
}

function regionsBySlashes(grid: string[]): number {
    const n = grid.length;
    const parent: number[] = new Array<number>(4 * n * n);
    for (let i = 0; i < parent.length; i++) parent[i] = i;
    const find = (x: number): number => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    const unite = (a: number, b: number): void => { parent[find(a)] = find(b); };
    const id = (r: number, c: number, k: number): number => (r * n + c) * 4 + k;
    // k: 0=T, 1=R, 2=B, 3=L
    for (let r = 0; r < n; r++) {
        for (let c = 0; c < n; c++) {
            const ch = grid[r][c];
            if (ch === ' ') {
                unite(id(r, c, 0), id(r, c, 1));
                unite(id(r, c, 1), id(r, c, 2));
                unite(id(r, c, 2), id(r, c, 3));
            } else if (ch === '/') {
                unite(id(r, c, 0), id(r, c, 3));
                unite(id(r, c, 1), id(r, c, 2));
            } else { // '\\'
                unite(id(r, c, 0), id(r, c, 1));
                unite(id(r, c, 2), id(r, c, 3));
            }
            if (r + 1 < n) unite(id(r, c, 2), id(r + 1, c, 0));
            if (c + 1 < n) unite(id(r, c, 1), id(r, c + 1, 3));
        }
    }
    const roots = new Set<number>();
    for (let i = 0; i < parent.length; i++) roots.add(find(i));
    return roots.size;
}

Editorial#

Subdividing each cell into 4 triangles is the canonical trick — slashes can be modeled exactly by which adjacent triangles they connect. The unions across cells respect grid adjacency. After all unions, distinct DSU roots correspond exactly to distinct regions.

Complexity#

Time: O(N^2 * α).
Space: O(N^2).

Concept revision#

Number of Islands