Course4all
Join us on telegram
Home/dsa/Union Find/Regions Cut By Slashes

Regions Cut By Slashes

Master this topic with zero to advance depth.

Regions Cut By Slashes

An n×nn \times 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. Return the number of regions.

Visualization (4 per cell)

Divide each 1x1 cell into 4 triangles:

/\ / 0\ <3 1> \ 2/ \/
  • '/' connects 0-3 and 1-2.
  • '\' connects 0-1 and 2-3.
  • ' ' connects 0-1-2-3.
Hard

Examples

Input: grid = [" /","/ "]
Output: 2
Approach 1

Level II: BFS (Grid Expansion)

Intuition

Scale the N×NN \times N grid into a 3N×3N3N \times 3N binary grid. Map '/' and '\' to sets of 1s in the 3x3 block. Then, use standard BFS or DFS to count connected components of 0s. This is more memory-intensive but conceptually simpler than triangle mapping.

⏱ O(N^2).💾 O(N^2).
java
class Solution {
    public int regionsBySlashes(String[] grid) {
        int n = grid.length, res = 0;
        int[][] g = new int[n * 3][n * 3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i].charAt(j) == '/') { g[i*3][j*3+2] = g[i*3+1][j*3+1] = g[i*3+2][j*3] = 1; }
                else if (grid[i].charAt(j) == '\\') { g[i*3][j*3] = g[i*3+1][j*3+1] = g[i*3+2][j*3+2] = 1; }
            }
        }
        for (int i = 0; i < n * 3; i++) for (int j = 0; j < n * 3; j++) if (g[i][j] == 0) { res++; dfs(g, i, j); }
        return res;
    }
    private void dfs(int[][] g, int r, int c) {
        if (r < 0 || c < 0 || r >= g.length || c >= g.length || g[r][c] != 0) return;
        g[r][c] = 2; dfs(g, r+1, c); dfs(g, r-1, c); dfs(g, r, c+1); dfs(g, r, c-1);
    }
}
Approach 2

Level III: Union-Find (Internal Grid Mapping)

Intuition

Represent each cell by 4 distinct nodes. Union neighboring triangles within the same cell based on the character ('/', '\', or ' '). Then, union adjacent triangles of neighboring cells. The final component count is the number of regions.

⏱ O(N^2 \cdot \alpha(N^2)).💾 O(N^2).
java
class Solution {
    public int regionsBySlashes(String[] grid) {
        int n = grid.length, count = 4 * n * n;
        int[] p = new int[count]; for(int i=0; i<count; i++) p[i]=i;
        for(int r=0; r<n; r++) {
            for(int c=0; c<n; c++) {
                int root = 4 * (r * n + c);
                char ch = grid[r].charAt(c);
                if (ch != '/') { count = union(p, root+0, root+1, count); count = union(p, root+2, root+3, count); }
                if (ch != '\\') { count = union(p, root+0, root+3, count); count = union(p, root+1, root+2, count); }
                if (r > 0) count = union(p, root+0, 4*((r-1)*n+c)+2, count);
                if (c > 0) count = union(p, root+3, 4*(r*n+(c-1))+1, count);
            }
        }
        return count;
    }
    int find(int[] p, int i) { return p[i]==i ? i : (p[i]=find(p, p[i])); }
    int union(int[] p, int i, int j, int c) {
        int r1=find(p,i), r2=find(p,j);
        if(r1!=r2) { p[r1]=r2; return c-1; } return c;
    }
}
← Previous QuestionCouples Holding Hands
Next Question →Minimize Malware Spread