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:

Note:

1 <= grid.length == grid[0].length <= 30 grid[i][j] is either ‘/’, ‘', or ‘ ‘.

#### EXPLANATION:

1.首先将每个方块分成4等分，上下左右4个三角形
2.对每个小三角形进行赋值，123456789。。。。
3.对每个小方框进行合并，如果是’\‘，则说明上面和右面合并，’/’则说明上左合并。’ ‘则表示四个都合并成一个，合并用相同的数字，也就是parent表示
4.然后再对所有的小方块进行一次union，也就是将前后左右的小方块进行union。恢复成相同的数字。这样，同一个区域的就是相同的数字了。
5.遍历小方块，将数字都放入set中，不重复的set中的size就是最后的结果

#### SOLUTION:

``````class Solution {
public int regionsBySlashes(String[] grid) {
int[][][] index = new int[grid.length][grid[0].toCharArray().length][4];
int count = 0;
for(int i = 0;i<grid.length;i++){
char[] chars = grid[i].toCharArray();
for(int j = 0;j<chars.length;j++,count++){
index[i][j][0] = count*4+0;
index[i][j][1] = count*4+1;
index[i][j][2] = count*4+2;
index[i][j][3] = count*4+3;
switch (chars[j]){
case '\\':
index[i][j][2] = index[i][j][0];
index[i][j][3] = index[i][j][1];
break;
case '/':
index[i][j][1] = index[i][j][0];
index[i][j][3] = index[i][j][2];
break;
case ' ':
index[i][j][1] = count*4+0;
index[i][j][2] = count*4+0;
index[i][j][3] = count*4+0;
break;
}
}
}
for(int i = 0;i<index.length;i++){
for(int j = 0;j<index[i].length;j++){
for(int m = 0;m<4;m++){
switch (m){
case 0:
if(i-1>=0)
regionsBySlashesHelper(index,index[i][j][0],index[i-1][j][3]);
break;
case 1:
if(j-1>=0)
regionsBySlashesHelper(index,index[i][j][1],index[i][j-1][2]);
break;
case 2:
if(j+1<index[i].length)
regionsBySlashesHelper(index,index[i][j][2],index[i][j+1][1]);
break;
case 3:
if(i+1<index.length)
regionsBySlashesHelper(index,index[i][j][3],index[i+1][j][0]);
break;
}

}
}
}
HashSet<Integer> result = new HashSet<>();
for(int[][] arr1 : index){
for(int[] arr2: arr1){
for(int a : arr2)
}
}
return result.size();
}
public static void regionsBySlashesHelper(int[][][] index,int x,int y){
for(int i = 0;i<index.length;i++){
for(int j = 0;j<index[i].length;j++){
for(int m = 0;m<4;m++){
if(index[i][j][m]==x) index[i][j][m] = y;
}
}
}

}
}
``````