# Regions Cut By Slashes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/regions-cut-by-slashes)
Canonical: https://scaleengineer.com/dsa/problems/regions-cut-by-slashes
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Hash Table, Matrix
---
## Problem
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 `'\\'`.

**Example 1:**

![](https://assets.glich.co/dsa/regions-cut-by-slashes/image0.png) 

**Input:** grid = [" /","/ "]
**Output:** 2

**Example 2:**

![](https://assets.glich.co/dsa/regions-cut-by-slashes/image1.png) 

**Input:** grid = [" /","  "]
**Output:** 1

**Example 3:**

![](https://assets.glich.co/dsa/regions-cut-by-slashes/image2.png) 

**Input:** grid = ["/\\","\\/"]
**Output:** 5
**Explanation:** Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.

**Constraints:**

* `n == grid.length == grid[i].length`
* `1 <= n <= 30`
* `grid[i][j]` is either `'/'`, `'\'`, or `' '`.

# Approaches
## Upscaling Grid and DFS/BFS
This approach solves the problem by transforming the input grid into a higher-resolution grid. Each `1x1` cell of the original grid is 'upscaled' to a `3x3` subgrid of pixels. The slashes (`'/'` and `'\'`) are drawn as 'walls' or 'barriers' (e.g., represented by 0s) in these subgrids, while the rest of the space remains open (e.g., represented by 1s). 

After this transformation, the problem is reduced to a standard 'number of islands' or 'connected components' problem on the new `3n x 3n` grid. We can then traverse this grid using Depth-First Search (DFS) or Breadth-First Search (BFS) to count the number of contiguous areas of open space.
**Time:** O(N^2). Building the `3N x 3N` grid takes O(N^2) time. The subsequent DFS/BFS traversal also takes O((3N)^2) = O(N^2) time as each cell in the upscaled grid is visited at most once. · **Space:** O(N^2), where N is the side length of the input grid. This is for storing the `3N x 3N` upscaled grid and for the recursion stack depth in the worst case.
**Pros:** The concept is highly intuitive and visual.; It transforms the problem into a well-known pattern (counting connected components), making it easier to implement for those familiar with it.
**Cons:** Requires more memory due to the `3n x 3n` grid, leading to higher constant factors in space complexity.; The time complexity also has a higher constant factor (`9n^2` vs `4n^2` operations) compared to the Union-Find approach.
### Explanation
The core idea is to make the connections between regions explicit by using a finer grid. A `1x1` cell is not granular enough to represent the connections properly, but a `3x3` subgrid is. For example, a `'/'` in cell `(i,j)` divides it into two regions. In the `3x3` model, this is represented by a diagonal line of 0s, which separates two areas of 1s. These areas of 1s can then connect to adjacent `3x3` subgrids, correctly modeling how regions merge across cell boundaries.

Once the `3n x 3n` grid is constructed, we iterate through it. Whenever we find a `1` that we haven't visited yet, we've discovered a new region. We increment our region counter and then use DFS to find and mark all parts of that same region, so we don't count it again. This process continues until the entire grid has been checked.

```java
class Solution {
    public int regionsBySlashes(String[] grid) {
        int n = grid.length;
        int[][] upscaledGrid = new int[3 * n][3 * n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);
                if (c == '/') {
                    upscaledGrid[3 * i][3 * j + 2] = 1;
                    upscaledGrid[3 * i + 1][3 * j + 1] = 1;
                    upscaledGrid[3 * i + 2][3 * j] = 1;
                } else if (c == '\\') {
                    upscaledGrid[3 * i][3 * j] = 1;
                    upscaledGrid[3 * i + 1][3 * j + 1] = 1;
                    upscaledGrid[3 * i + 2][3 * j + 2] = 1;
                }
            }
        }

        int regions = 0;
        for (int i = 0; i < 3 * n; i++) {
            for (int j = 0; j < 3 * n; j++) {
                if (upscaledGrid[i][j] == 0) {
                    regions++;
                    dfs(upscaledGrid, i, j, 3 * n);
                }
            }
        }
        return regions;
    }

    private void dfs(int[][] grid, int r, int c, int size) {
        if (r < 0 || r >= size || c < 0 || c >= size || grid[r][c] == 1) {
            return;
        }
        grid[r][c] = 1; // Mark as visited
        dfs(grid, r + 1, c, size);
        dfs(grid, r - 1, c, size);
        dfs(grid, r, c + 1, size);
        dfs(grid, r, c - 1, size);
    }
}
```
### Algorithm
- Create a new `3n x 3n` integer grid, let's call it `upscaledGrid`, and initialize all its cells to 1, representing open space.
- Iterate through the input `n x n` grid. For each cell `grid[i][j]`:
  - If the character is `'/'`, it forms a barrier from top-right to bottom-left. In the `3x3` subgrid corresponding to `(i,j)`, set the pixels `(3i, 3j+2)`, `(3i+1, 3j+1)`, and `(3i+2, 3j)` to 0 (barrier).
  - If the character is `'\'`, it forms a barrier from top-left to bottom-right. Set the pixels `(3i, 3j)`, `(3i+1, 3j+1)`, and `(3i+2, 3j+2)` to 0.
  - If the character is a space `' '`, the `3x3` subgrid remains all 1s.
- Initialize a counter `regionCount` to 0.
- Iterate through every cell `(r, c)` of the `3n x 3n` `upscaledGrid`.
- If `upscaledGrid[r][c]` is 1 (an unvisited part of a region):
  - Increment `regionCount`.
  - Start a graph traversal (like Depth-First Search or Breadth-First Search) from `(r, c)`.
  - The traversal should visit all reachable cells with a value of 1 and mark them as visited (e.g., by changing their value to 0) to avoid recounting them.
- After iterating through the entire `upscaledGrid`, `regionCount` will hold the total number of regions. Return `regionCount`.

## Union-Find on Sub-regions
A more efficient approach uses a Union-Find data structure. The main idea is to model the problem as finding the number of connected components among a set of small, fundamental regions. We can decompose each `1x1` cell into 4 triangular sub-regions (top, right, bottom, left).

We then use the Union-Find algorithm to group these sub-regions. Initially, each of the `4 * n * n` sub-regions is in its own set. We iterate through the grid, and for each cell, we perform `union` operations. First, we unite the sub-regions within the cell based on the slash type. A space `' '` unites all 4 sub-regions, while `'/'` and `'\'` each create two pairs of united sub-regions. Second, we unite adjacent sub-regions across cell boundaries (e.g., the bottom of one cell with the top of the cell below it). The final number of disjoint sets remaining is the number of regions.
**Time:** O(N^2 * α(N^2)), where α is the extremely slow-growing Inverse Ackermann function. For all practical purposes, the complexity is nearly linear, effectively O(N^2). · **Space:** O(N^2). The DSU data structure requires a parent array of size `4 * N * N`.
**Pros:** More efficient in terms of both time and space complexity due to smaller constant factors.; Provides an elegant and scalable solution using a standard, powerful data structure.
**Cons:** The mapping of grid cells and their sub-regions to indices in the Union-Find data structure can be abstract and harder to visualize than the upscaling method.; Implementation of the Union-Find data structure adds a bit of overhead if not already available.
### Explanation
The Union-Find (DSU) data structure is perfectly suited for this problem because it efficiently tracks sets of connected elements. By breaking down each cell into 4 sub-regions, we create a consistent model for connections. The character in a cell (`'/'`, `'\'`, `' '`) determines the internal connectivity, while the grid structure determines the external connectivity between cells.

The DSU is initialized with `4 * n * n` elements, each representing a sub-region. The `count` of disjoint sets starts at `4 * n * n`. As we iterate and perform `union` operations, this `count` decreases whenever two distinct regions are merged. After processing all intra-cell and inter-cell connections, the final `count` gives the number of contiguous regions in the entire grid.

```java
class Solution {
    class DSU {
        int[] parent;
        int count;

        public DSU(int n) {
            parent = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]);
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
                count--;
            }
        }
    }

    public int regionsBySlashes(String[] grid) {
        int n = grid.length;
        DSU dsu = new DSU(4 * n * n);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int root = 4 * (i * n + j);
                // 0: top, 1: right, 2: bottom, 3: left
                char val = grid[i].charAt(j);

                // Intra-cell connections
                if (val == '/') {
                    dsu.union(root + 0, root + 3); // top-left
                    dsu.union(root + 1, root + 2); // right-bottom
                } else if (val == '\\') {
                    dsu.union(root + 0, root + 1); // top-right
                    dsu.union(root + 2, root + 3); // bottom-left
                } else { // ' '
                    dsu.union(root + 0, root + 1);
                    dsu.union(root + 1, root + 2);
                    dsu.union(root + 2, root + 3);
                }

                // Inter-cell connections
                // Connect to cell below
                if (i + 1 < n) {
                    int bottomRoot = 4 * ((i + 1) * n + j);
                    dsu.union(root + 2, bottomRoot + 0); // current bottom to next top
                }
                // Connect to cell to the right
                if (j + 1 < n) {
                    int rightRoot = 4 * (i * n + j + 1);
                    dsu.union(root + 1, rightRoot + 3); // current right to next left
                }
            }
        }
        return dsu.count;
    }
}
```
### Algorithm
- Divide each `1x1` cell of the grid into 4 smaller triangular sub-regions: 0 (top), 1 (right), 2 (bottom), and 3 (left).
- This gives a total of `4 * n * n` sub-regions. Initialize a Union-Find (or Disjoint Set Union - DSU) data structure for this many elements. The initial number of disjoint sets (regions) is `4 * n * n`.
- Map each sub-region `k` in cell `(i, j)` to a unique integer index, for example, `(i * n + j) * 4 + k`.
- Iterate through each cell `(i, j)` of the input grid and perform union operations:
  - **Intra-cell unions:** Based on the character in `grid[i][j]`, merge the sub-regions within that cell.
    - If `'/'`: Union the top (0) with left (3), and right (1) with bottom (2).
    - If `'\'`: Union the top (0) with right (1), and bottom (2) with left (3).
    - If `' '`: Union all four sub-regions together, e.g., `union(0,1)`, `union(1,2)`, `union(2,3)`.
  - **Inter-cell unions:** Merge sub-regions that are adjacent across cell boundaries.
    - If `i < n-1`, union the bottom sub-region (2) of cell `(i, j)` with the top sub-region (0) of cell `(i+1, j)`.
    - If `j < n-1`, union the right sub-region (1) of cell `(i, j)` with the left sub-region (3) of cell `(i, j+1)`.
- Each time the `union` operation successfully merges two previously disconnected sets, the total count of regions decreases by one.
- The final number of disjoint sets in the DSU structure is the answer.

# Solutions
### Java

```java
class Solution { private int [] p ; private int size ; public int regionsBySlashes ( String [] grid ) { int n = grid . length ; size = n * n * 4 ; p = new int [ size ]; for ( int i = 0 ; i < p . length ; ++ i ) { p [ i ] = i ; } for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int k = i * n + j ; if ( i < n - 1 ) { union ( 4 * k + 2 , ( k + n ) * 4 ); } if ( j < n - 1 ) { union ( 4 * k + 1 , ( k + 1 ) * 4 + 3 ); } char v = grid [ i ]. charAt ( j ); if ( v == '/' ) { union ( 4 * k , 4 * k + 3 ); union ( 4 * k + 1 , 4 * k + 2 ); } else if ( v == '\\' ) { union ( 4 * k , 4 * k + 1 ); union ( 4 * k + 2 , 4 * k + 3 ); } else { union ( 4 * k , 4 * k + 1 ); union ( 4 * k + 1 , 4 * k + 2 ); union ( 4 * k + 2 , 4 * k + 3 ); } } } return size ; } private int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } private void union ( int a , int b ) { int pa = find ( a ); int pb = find ( b ); if ( pa == pb ) { return ; } p [ pa ] = pb ; -- size ; } }
```

### JavaScript

```javascript
/** * @param {string[]} grid * @return {number} */ function regionsBySlashes(
  grid,
) {
  const find = (x) => {
    if (p[x] !== x) {
      p[x] = find(p[x]);
    }
    return p[x];
  };
  const union = (a, b) => {
    const pa = find(a);
    const pb = find(b);
    if (pa !== pb) {
      p[pa] = pb;
      size--;
    }
  };
  const n = grid.length;
  let size = n * n * 4;
  const p = Array.from({ length: size }, (_, i) => i);
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const k = i * n + j;
      if (i < n - 1) {
        union(4 * k + 2, (k + n) * 4);
      }
      if (j < n - 1) {
        union(4 * k + 1, (k + 1) * 4 + 3);
      }
      if (grid[i][j] === " / ") {
        union(4 * k, 4 * k + 3);
        union(4 * k + 1, 4 * k + 2);
      } else if (grid[i][j] === " \\ ") {
        union(4 * k, 4 * k + 1);
        union(4 * k + 2, 4 * k + 3);
      } else {
        union(4 * k, 4 * k + 1);
        union(4 * k + 1, 4 * k + 2);
        union(4 * k + 2, 4 * k + 3);
      }
    }
  }
  return size;
}

```

### CPP

```cpp
class Solution { public: vector < int > p ; int size ; int regionsBySlashes ( vector < string >& grid ) { int n = grid . size (); size = n * n * 4 ; p . resize ( size ); for ( int i = 0 ; i < size ; ++ i ) p [ i ] = i ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int k = i * n + j ; if ( i < n - 1 ) merge ( 4 * k + 2 , ( k + n ) * 4 ); if ( j < n - 1 ) merge ( 4 * k + 1 , ( k + 1 ) * 4 + 3 ); char v = grid [ i ][ j ]; if ( v == '/' ) { merge ( 4 * k , 4 * k + 3 ); merge ( 4 * k + 1 , 4 * k + 2 ); } else if ( v == '\\' ) { merge ( 4 * k , 4 * k + 1 ); merge ( 4 * k + 2 , 4 * k + 3 ); } else { merge ( 4 * k , 4 * k + 1 ); merge ( 4 * k + 1 , 4 * k + 2 ); merge ( 4 * k + 2 , 4 * k + 3 ); } } } return size ; } void merge ( int a , int b ) { int pa = find ( a ); int pb = find ( b ); if ( pa == pb ) return ; p [ pa ] = pb ; -- size ; } int find ( int x ) { if ( p [ x ] != x ) p [ x ] = find ( p [ x ]); return p [ x ]; } };
```

### Python

```python
class Solution : def regionsBySlashes ( self , grid : List [ str ]) -> int : def find ( x ): if p [ x ] != x : p [ x ] = find ( p [ x ]) return p [ x ] def union ( a , b ): pa , pb = find ( a ), find ( b ) if pa != pb : p [ pa ] = pb nonlocal size size -= 1 n = len ( grid ) size = n * n * 4 p = list ( range ( size )) for i , row in enumerate ( grid ): for j , v in enumerate ( row ): k = i * n + j if i < n - 1 : union ( 4 * k + 2 , ( k + n ) * 4 ) if j < n - 1 : union ( 4 * k + 1 , ( k + 1 ) * 4 + 3 ) if v == '/' : union ( 4 * k , 4 * k + 3 ) union ( 4 * k + 1 , 4 * k + 2 ) elif v == ' \\ ' : union ( 4 * k , 4 * k + 1 ) union ( 4 * k + 2 , 4 * k + 3 ) else : union ( 4 * k , 4 * k + 1 ) union ( 4 * k + 1 , 4 * k + 2 ) union ( 4 * k + 2 , 4 * k + 3 ) return size
```