当前位置 博文首页 > Inmaturity_7的博客：算法练习帖--56--由斜杠划分区域(Java)
在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
（请注意，反斜杠字符是转义的，因此 \ 用 “\” 表示。）。
返回区域的数目。
（题目来源：力扣（LeetCode））
示例 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] 是 '/'、'\'、或 ' '。
1. 并查集（官方题解）
package com.lxf.uf;
public class RegionsBySlashes {
public int regionsBySlashes(String[] grid) {
//获取网格长
int length=grid.length;
//因为是正方形所以宽也是length,而且由4*length*length小正方形组成
int size=4*length*length;
//初始化并查集对象
UnionFind uf = new UnionFind(size);
for (int i = 0; i < length; i++) {
//转字符串为字符数组
char[] chars = grid[i].toCharArray();
for (int j = 0; j < chars.length; j++) {
//将二维网格转换为一维网格
int index=4*(i*length+j);
//获取当前字符
char c=chars[j];
//单元格内合并
if(c=='/'){
//合并0,3
uf.union(index,index+3);
//合并1,2
uf.union(index+1,index+2);
}else if(c=='\\'){
//合并0,1
//合并2,3
uf.union(index,index+1);
uf.union(index+2,index+3);
}else{
//合并0,1,2,3
uf.union(index,index+1);
uf.union(index+1,index+2);
uf.union(index+2,index+3);
}
//单元格间合并
if(j+1<length){
//合并当前正方形1和下一个正方形的3
uf.union(index+1,index+7);
}
if(i+1<length){
//合并当前正方形2和下一个正方形的0
uf.union(index+2,index+4*length);
}
}
}
return uf.getCount();
}
class UnionFind{
int count;
int[] parent;
int[] rank;
public int getCount() {
return count;
}
/**
* 初始化方法
* @param length
*/
public UnionFind(int length) {
parent=new int[length];
rank=new int[length];
count=length;
for (int i = 0; i < length; i++) {
parent[i]=i;
}
}
/**
* 查找父亲结点方法
* @param index
* @return
*/
public int find(int index){
while (index!=parent[index]){
parent[index]=parent[parent[index]];
index=parent[index];
}
return index;
}
/**
* 合并方法
* @param index1 要合并的第一个集合下标
* @param index2 要合并的第二个集合下标
*/
public void union(int index1,int index2){
//找到对应的父结点
int root1=find(index1);
int root2=find(index2);
if(root1==root2) return;
//按秩合并
if(rank[root1]>rank[root2]){
parent[root2]=root1;
}else if(rank[root1]<rank[root2]){
parent[root1]=root2;
}else{
parent[root2]=root1;
rank[root1]++;
}
count--;
}
}
}
在写BFS和DFS的之前看一段大佬的解析就豁然开朗了：每个小格分解为 3 * 3 方格，BFS和DFS求连通分量思路。
2. BFS
package com.lxf.test;
public class RegionsBySlashes {
public static void main(String[] args) {
}
private static int tupleL;
public static int regionsBySlashes(String[] grid) {
//获取网格长
int l=grid.length;
tupleL=3*l;
//新建3*3*length*length小正方形数组
int[][] tuple = new int[tupleL][tupleL];
for (int i = 0; i < l; i++) {
//转字符串为字符数组
char[] chars = grid[i].toCharArray();
for (int j = 0; j < chars.length; j++) {
//获取当前字符
char c=chars[j];
//根据字符给数组附上初始值：0是空出来的小正方型，是可以连通的；1是斜线，阻隔小正方型的。
//或者比作第200道题目：0是小岛，1是水域（我这反过来是因为数组初始值就是0）
if(c=='/'){
//将9个小正方形按/划开
tuple[i*3][j*3+2]=1;
tuple[i*3+1][j*3+1]=1;
tuple[i*3+2][j*3]=1;
}else if(c=='\\'){
//将9个小正方形按\划开
tuple[i*3][j*3]=1;
tuple[i*3+1][j*3+1]=1;
tuple[i*3+2][j*3+2]=1;
}
}
}
//DFS求连通量
int count=0;
for (int i = 0; i < l*3; i++) {
for (int j = 0; j < l*3; j++) {
if(tuple[i][j]==
