959. 由斜杠划分区域
Difficulty: 中等
在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
（请注意，反斜杠字符是转义的，因此 \ 用 "\\" 表示。）。
返回区域的数目。
示例 1：
输入：
[
" /",
"/ "
]
输出：2
解释：2x2 网格如下：
示例 2：
输入：
[
" /",
" "
]
输出：1
解释：2x2 网格如下：
示例 3：
输入：
[
"\\/",
"/\\"
]
输出：4
解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
2x2 网格如下：
示例 4：
输入：
[
"/\\",
"\\/"
]
输出：5
解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
2x2 网格如下：
示例 5：
输入：
[
"//",
"/ "
]
输出：3
解释：2x2 网格如下：
提示：
1 <= grid.length == grid[0].length <= 30-
grid[i][j]是'/'、'\'、或' '。
Solution
思路：题意是说可以通过''和'/'或空格对一个NN的正方形进行分割。看了题解知道可以等价转化为判断连通图，那么可以直接使用并查集。NN的正方形由N*N个小正方形组成，每个小正方形沿对角线可以分成四份三角形。我们要做的就是判断这四份三角形是否连通（可能被‘/’或''给分割了）。注意，每个相邻的小正方形与隔壁小正方形是连通的。
Language: java
class Solution {
public int regionsBySlashes(String[] grid) {
int len = grid.length;
UnionFind uf = new UnionFind(4*len*len);
/*
* 将小正方形分为四份，编号顺序为上右下左，依次是i,i+1,i+2,i+3
* 遍历小正方形，根据'\'或'/'或' '合并并查集
*/
for(int i=0; i<len; i++){
int ii = i * len * 4;
for(int j=0; j<len; j++){
switch(grid[i].charAt(j)){
case ' ':
uf.merge(ii+j*4,ii+j*4+1,ii+j*4+2,ii+j*4+3);
break;
case '\\':
uf.merge(ii+j*4, ii+j*4+1);
uf.merge(ii+j*4+2, ii+j*4+3);
break;
case '/':
uf.merge(ii+j*4, ii+j*4+3);
uf.merge(ii+j*4+1,ii+j*4+2);
break;
}
/*
* 每个三角形都与邻边的小正方形相通
*/
if(j != 0) uf.merge(ii+(j-1)*4+1, ii+j*4+3);
if(i != 0) uf.merge(ii-len*4+j*4+2, ii+j*4);
}
}
Set<Integer> set = new HashSet<>();
for(int i=0; i<4*len*len; i++){
set.add(uf.find(i));
}
return set.size();
}
class UnionFind{
int[] parent;
public UnionFind(int n){
parent = new int[n];
for(int i=0; i<n; i++) parent[i] = i;
}
public int find(int i){
return i == parent[i] ? i : (parent[i] = find(parent[i]));
}
public void merge(int i, int j){
parent[find(j)] = find(i);
}
public void merge(int...nums){
for(int i=1; i<nums.length; i++){
merge(nums[0], nums[i]);
}
}
}
}
PS:为啥最近的题都是并查集！？！？