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.

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 ' '.

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;
    }
}