<hr style=” border:solid; width:100px; height:1px;” color=#000000 size=1”>
前言
算法之并查集
一，959. 由斜杠划分区域
在由 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] 是 ‘/’、’'、或 ‘ ‘。
二， 解题思路
求区域的个数，就要联想到并查集的的性质count集合的个数 问题
将每个小方块分为4块，
合并方法规则有 : 左右，上下合并不影响其它的方块的区域
三， 代码
void init(int * union_find, int size)
{
for (int i = 0; i < size; ++i)
{
union_find[i] = i;
}
}
int getfriend(int * union_find, int v)
{
if (union_find[v] == v)
{
return v;
}
return union_find[v] = getfriend(&union_find[0], union_find[v]);
}
void _union(int* union_find, int index_v0, int index_v1, int *count)
{
// return;
int v0 = getfriend(&union_find[0], index_v0);
int v1 = getfriend(&union_find[0], index_v1);
if (v0 != v1)
{
--(*count);
if (v0 < v1)
{
union_find[v1] = v0;
union_find[index_v1] = v0;
}
else if (v0 > v1)
{
union_find[v0] = v1;
union_find[index_v0] = v1;
}
else
{
printf("[error] v0 , v1\n");
}
}
}
void show(int * union_find, int size)
{
printf("[");
for (int i = 0; i < size; ++i)
{
printf("%d, ", union_find[i]);
}
printf("]\n");
}
int regionsBySlashes(char ** grid, int gridSize)
{
//[" /","/ ","/ ", "/", "/"] 41
int size = 4 * (gridSize * gridSize);
int union_find[size];
init(&union_find[0], size);
int count = size;
for (int i = 0; i < gridSize; ++i)
{
const char * p = grid[i];
int cur_len = strlen(p);
int index = 0;
while (*p != '\0')
{
int index_v0 = (i * 4*gridSize) + (index * 4);
int index_v1 = index_v0 + 1;
int index_v2 = index_v1 + 1;
int index_v3 = index_v2 + 1;
// printf("i = %d, count %d, index = %d\n", i, count, index_v0);
if (*p == ' ')
{
//合并0,1, 2，3的小的区域
_union(&union_find, index_v0, index_v1, &count);
_union(&union_find, index_v0, index_v2, &count);
_union(&union_find, index_v0, index_v3, &count);
}
else if (*p == '/')
{
//合并0,3区域
_union(&union_find, index_v0, index_v3, &count);
//合并1,2区域
_union(&union_find, index_v1, index_v2, &count);
// show(&union_find[0], size);
}
else if (*p == '\\')
{
//合并 0,1区域
_union(&union_find, index_v0, index_v1, &count);
//合并2,3区域
_union(&union_find, index_v2, index_v3, &count);
}
else
{
printf("[error]%c\n", *p);
}
++p;
++index;
//判断是否
if (index < cur_len)
{
// 1 --> 3 union
int index_2_v3 = index_v3+4;
// 当前小方块中1三角形和下一个小方块中3三角形合并
_union(&union_find, index_v1, index_2_v3, &count);
// show(&union_find[0], size);
}
if (i < (gridSize-1))
{
// 2 --> 0
int index_xia_v0 = index_v0 + (gridSize*4);
// printf("index_v0 = %d, index_xia_v0 = %d\n", index_v0, index_xia_v0);
_union(&union_find, index_v2, index_xia_v0, &count);
// show(&union_find[0], size);
}
}
}
return count;
}
总结
时间复杂度$O(N^2)$ 空间复杂度$O(N^2)$
源码地址:https://github.com/chensongpoixs/cleet_code
