# Regions Cut By Slashes

In a N x N `grid` composed of 1 x 1 squares, each 1 x 1 square consists of a `/`, `\`, or blank space.  These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a `\` is represented as `"\\"`.)

Return the number of regions.

1.

**Example 1:**

```
Input:
[
  " /",
  "/ "
]
Output: 2
Explanation: The 2x2 grid is as follows:

```

**Example 2:**

```
Input:
[
  " /",
  "  "
]
Output: 1
Explanation: The 2x2 grid is as follows:

```

**Example 3:**

```
Input:
[
  "\\/",
  "/\\"
]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
The 2x2 grid is as follows:

```

**Example 4:**

```
Input:
[
  "/\\",
  "\\/"
]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)
The 2x2 grid is as follows:

```

**Example 5:**

```
Input:
[
  "//",
  "/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:

```

**Note:**

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

```java
class Solution {
    // DFS Solution with a 3*3 trick
    // 2*2 may hide free space
    public int regionsBySlashes(String[] grid) {
        int n = 3 * grid.length;
        int[][] matrix = new int[n][n];
        // Showing slashes with diagonal 1s in 3*3 matrix
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length(); j++) {
                if (grid[i].charAt(j) == '\\') {
                    for (int x = 3 * i, y = 3 * j; x < 3 * i + 3 && y < 3 * j + 3; x++, y++)
                        matrix[x][y] = 1;
                } else if (grid[i].charAt(j) == '/') {
                    for (int x = 3 * i + 2, y = 3 * j; x >= 3 * i && y < 3 * j + 3; x--, y++)
                        matrix[x][y] = 1;
                }
            }
        }
        // Marking components of 0 (free space)
        // We will use our own matrix as visited ,
        // Convert 0 -> 1 when visited
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    ans++;
                    DFS(matrix, i, j, n);
                }
            }
        }
        return ans;
    }

    int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

    public void DFS(int[][] matrix, int x, int y, int n) {
        matrix[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int newX = x + dir[i][0], newY = y + dir[i][1];
            if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX][newY] == 0)
                DFS(matrix, newX, newY, n);
        }
    }
    
    // DSU Solution (Combined with path compression and Union by rank)
    public int regionsBySlashes(String[] grid) {
        int n = grid.length + 1;
        int[] parent = new int[n * n];
        int[] rank = new int[n * n];
        for (int i = 0; i < n * n; i++)
            parent[i] = i;
        Arrays.fill(rank, 1);
        // Making border connections as they are connected by default
        // Upper row
        for (int i = 0; i < n - 2; i++)
            union(parent, rank, i, i + 1);
        // Left column
        for (int i = 0; i < n * n - n; i += n)
            union(parent, rank, i, i + n);
        // Right column
        for (int i = n - 1; i < n * n - n; i += n)
            union(parent, rank, i, i + n);
        // Bottom row
        for (int i = n * n - 1; i > n * n - n; i--)
            union(parent, rank, i, i - 1);
        // Making connections and the cycles formed are the extra region formed by cuts
        int ans = 1;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length(); j++) {
                if (grid[i].charAt(j) == '\\') {
                    int p1 = i * n + j;
                    int p2 = (i + 1) * n + (j + 1);
                    if (union(parent, rank, p1, p2))
                        ans++;
                } else if (grid[i].charAt(j) == '/') {
                    int p1 = (i + 1) * n + j;
                    int p2 = (i) * n + (j + 1);
                    if (union(parent, rank, p1, p2))
                        ans++;
                }
            }
        }
        return ans;
    }

    public int find(int[] parent, int x) {
        if (x != parent[x])
            parent[x] = find(parent, parent[x]);
        return parent[x];
    }

    // This function unionize as well as tells us whether a cycle is formed
    public boolean union(int[] parent, int[] rank, int x, int y) {
        int p1 = find(parent, x);
        int p2 = find(parent, y);
        if (p1 != p2) {
            if (rank[p1] > rank[p2])
                parent[p2] = p1;
            else if (rank[p2] > rank[p1])
                parent[p1] = p2;
            else {
                parent[p1] = p2;
                rank[p1]++;
            }
            return false;
        } else
            return true;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/regions-cut-by-slashes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.