959. Regions Cut By Slashes

Question

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:

Solution:

Imgur

Method 1: union-find

this trick of this question is how can we connect all cells. so we divide all cells into 4 parts and slash will only effect the connection bwtween all triangles.

According to the question, there are 3 conditions:

empty, means all triangles are all connected.
normal slash, union(0, 1), union(2, 3).

reverse slash, union(0, 3), union(1, 2).

class Solution {
private int[] uf;
private int len;
public int regionsBySlashes(String[] grid) {
    this.len = grid.length;
    this.uf = new int[len * 4 * len];
    for(int i = 0; i < len * len * 4; i++) uf[i] = i;
    for(int i = 0; i < len; i++){
        for(int j = 0; j < len; j++){
            char c = grid[i].charAt(j);
            int index = i * 4 * len + 4 * j;
            switch(c){
                case ' ':
                    union(index, index + 1);
                    union(index + 1, index + 2);
                    union(index + 2, index + 3);
                    break;
                case '/':
                    union(index, index + 3);
                    union(index + 1, index + 2);
                    break;
                case '\\':
                    union(index, index + 1);
                    union(index + 2, index + 3);
                    break;
            }
            if(i + 1 < len) union(index + 2, index + 4 * len);
            if(j + 1 < len) union(index + 1, index + 4 + 3);
        }
    }
    int res = 0;
    for(int i = 0; i < len * len * 4; i++){
        if(uf[i] == i) res++;
    }
    return res;
}
private int find(int i){
    if(i != uf[i])
        uf[i] = find(uf[i]);
    return uf[i];
}
private void union(int i, int j){
    int p = find(i);
    int q = find(j);
    uf[p] = q;
}
}