题目链接：https://leetcode-cn.com/problems/regions-cut-by-slashes/
令我思考很久的一道题，最后还是学着官方题解做出来的([1])。思考过程中也想过并查集，然而并没有想到题解中的做法；想到过求一个图中环路的个数，然而不会。
题目
在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
（请注意，反斜杠字符是转义的，因此 \ 用 “\\” 表示。）。
返回区域的数目。
分析
将单元格进一步细分，便于并查集操作。
每个单元格对角点互连，即可分成四个小三角形（图1），根据本格中的字符是
/还是\，合并不同的小三角形。
图1. 单元格划分
格内合并
- 当本格字符为空格时，所有小三角形处于同一个区域中，全部合并；
- 当本格字符为
/时，合并0号和3号，合并1号和2号，且这两个区域不互通；- 当本格字符为
\时，合并0号和1号，合并3号和2号，且这两个区域不互通。格间合并
- 格间合并是指单元格之间的小三角形合并。无论本单元格中的字符是什么，当前单元格的1号三角形和右边单元格的3号永远处于同一个区域，当前单元格的2号和下边单元格的0号永远处于同一个区域。同理考虑左边和上边单元格。
- 我们要遍历所有的单元格，故格间合并只需要顾及左右两侧邻居之一、上下两侧邻居之一即可；例如对于每个单元格只考虑与其右边单元格和下边单元格的合并，每个单元格都如此，则所有单元格都能正常完成合并。
最终操作
- 遍历每个单元格，按照字符进行格内合并；如果右边和下边有邻居就进行格间合并。这样最后剩下的独立并查集个数就是最终划分得到的区域数。
- 这种方式的关键在于格间合并，无论格内字符是什么，格间的联通总能使得离散的区域聚到一起。
模拟
考虑对于示例4：
- 输入：
["/\\","\\/"]- 输出：
5网格如下：
图2. 网格 我们从左上到右下进行遍历。
首先第一个单元格进行格内合并：
Step1 第一个单元格的格间合并，从此图中就不难看出格间合并的规律与格内字符无关。
Step2 第二个单元格的格内合并：
Step3 格间合并，此时它已经没有右邻居：
Step4 第三、第四个单元格分别格内、格间合并，最终得到的各个独立集合如下：
Final
AC代码
将上面的模拟转化成代码，其关键在于单元格和小三角形的表示。我们将二维的网格拉直，则一个坐标
(x, y)的单元格位于一维数组中的n * x + y处；每个单元格分为4个小三角形，故一个单元格占据4个数组空间。最终，坐标
(x, y)的单元格位于4 * (n * x + y)到4 * (n * x + y) + 3的下标位置。则最终的一维数组即并查集需要开辟的大小为
4 * n * n。
class UnionFind {
private:
int f[10000];
int cnt;
public:
UnionFind(int n)
{
for (int i = 0; i < 4 * n * n; i++)
{
f[i] = i;
}
cnt = 4 * n * n;
}
int getCnt() { return cnt; }
int find(int n)
{
if (f[n] == n)
return n;
f[n] = find(f[n]);
return f[n];
}
void Union(int a, int b)
{
int ra = find(a);
int rb = find(b);
if (ra == rb)
return ;
else if (ra < rb)
f[rb] = ra;
else if (ra > rb)
f[ra] = rb;
// cout << "Union " << a << " with " << b << endl;
cnt--;
return ;
}
};
class Solution {
public:
int regionsBySlashes(vector<string>& grid) {
int n = grid.size();
UnionFind uf(n);
for (int x = 0; x < n; x++)
{
for (int y = 0; y < n; y++)
{
int base = 4 * (x * n + y); // 0,4,8,...
/* 格内合并 */
if (grid[x][y] == ' ')
{
uf.Union(base, base + 1);
uf.Union(base, base + 2);
uf.Union(base, base + 3);
}
else if (grid[x][y] == '/')
{
uf.Union(base, base + 3);
uf.Union(base + 1, base + 2);
}
else if (grid[x][y] == '\\')
{
uf.Union(base, base + 1);
uf.Union(base + 2, base + 3);
}
/* 格间合并 */
if (y < n - 1) // 还有右邻居
uf.Union(base + 1, base + 7); // 己方1，右邻居3
if (x < n - 1) // 还有下邻居
uf.Union(base + 2, base + 4 * n); // 己方2，下邻居0
}
}
return uf.getCnt();
}
};
表现还不错，叉会儿腰。
参考资料
[1] 力扣官方题解.由斜杠划分区域[EB/OL].2021-01-24
