1. 题目
在由 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] 是 '/'、'\'、或 ' '。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regions-cut-by-slashes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 并查集
- 将每个格子分成4个部分
- 如果是红线，合并01，23；橙线，合并12，03
- 然后每个块跟相邻的对应块也要合并
class DisjointSet
{
public:
vector<int> father;
DisjointSet(int n)
{
father.resize(n);
for(int i = 0; i < n; ++i)
father[i] = i;//并查集初始化
}
int find(int x)
{
if(x == father[x])
return x;
return father[x] = find(father[x]);
}
void merge(int x, int y)
{
int fx = find(x);
int fy = find(y);
if(fx != fy)
father[fx] = fy;
}
int countUni()//计算有多少个团体
{
int count = 0;
for(int i = 0; i < father.size(); ++i)
if(find(i) == i)
count++;
return count;
}
};
class Solution {
public:
int regionsBySlashes(vector<string>& grid) {
int n = grid.size(), i, j, pos;
DisjointSet uni(4*n*n);//一个位置分成4块，上下左右，共计这么多个单元
char ch;
for(i = 0; i < n; ++i)
{
for(j = 0; j < n; ++j)
{
pos = 4*(i*n+j);//单元格0位
ch = grid[i][j];
if(ch != '/')//为红线或者空白
{
uni.merge(pos+0,pos+1);
uni.merge(pos+2,pos+3);
}
if(ch != '\\')//为橙线线或者空白
{
uni.merge(pos+0,pos+3);
uni.merge(pos+2,pos+1);
}
if(i > 0)//上面合并
uni.merge(pos+0, pos-4*n+2);
if(i < n-1)//下面合并
uni.merge(pos+2, pos+4*n+0);
if(j > 0)//左面合并
uni.merge(pos+3, pos-4+1);
if(j < n-1)//右面合并
uni.merge(pos+1, pos+4+3);
}
}
return uni.countUni();
}
};
16 ms 10.1 MB