LeetCode:959. Regions Cut By Slashes由斜杠划分区域(C语言）

快来打我* 2023-01-10 14:47 84阅读 0赞

**题目描述：**  
在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\\ 或空格构成。这些字符会将方块划分为一些共边的区域。

（请注意，反斜杠字符是转义的，因此 \\ 用 “\\” 表示。）。

返回区域的数目。

示例 1：

输入：  
\[  
" /",  
"/ "  
\]  
输出：2  
解释：2x2 网格如下：  
![在这里插入图片描述][77de6391e26d735259b692fd416dd50a.png_pic_center]

示例 2：

输入：  
\[  
" /",  
" "  
\]  
输出：1  
解释：2x2 网格如下：  
![在这里插入图片描述][c2d082409a3f21805916767d13119888.png_pic_center]

示例 3：

输入：  
\[  
“\\/”,  
“/\\”  
\]  
输出：4  
解释：（回想一下，因为 \\ 字符是转义的，所以 “\\/” 表示 /，而 “/\\” 表示 /\\。）  
2x2 网格如下：  
![在这里插入图片描述][aa9c81109afdd0d9fa15b9ba45bbfda4.png_pic_center]

示例 4：

输入：  
\[  
“/\\”,  
“\\/”  
\]  
输出：5  
解释：（回想一下，因为 \\ 字符是转义的，所以 “/\\” 表示 /\\，而 “\\/” 表示 /。）  
2x2 网格如下：  
![在这里插入图片描述][34ef7330f08825c9a4fbe8887d2fca5e.png_pic_center]

示例 5：

输入：  
\[  
“//”,  
"/ "  
\]  
输出：3  
解释：2x2 网格如下：  
![在这里插入图片描述][424424f4e1284458280bab0adfe8fe83.png_pic_center]

提示：

1 <= grid.length == grid[0].length <= 30
    grid[i][j] 是 '/'、'\'、或 ' '。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/regions-cut-by-slashes  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

void swap(int* a, int* b) { 
        int tmp = *a;
        *a = *b, *b = tmp;
    }
    
    struct DisjointSetUnion { 
        int *f, *size;
        int n, setCount;
    };
    
    void initDSU(struct DisjointSetUnion* obj, int n) { 
        obj->f = malloc(sizeof(int) * n);
        obj->size = malloc(sizeof(int) * n);
        obj->n = n;
        obj->setCount = n;
        for (int i = 0; i < n; i++) { 
            obj->f[i] = i;
            obj->size[i] = 1;
        }
    }
    
    int find(struct DisjointSetUnion* obj, int x) { 
        return obj->f[x] == x ? x : (obj->f[x] = find(obj, obj->f[x]));
    }
    
    int unionSet(struct DisjointSetUnion* obj, int x, int y) { 
        int fx = find(obj, x), fy = find(obj, y);
        if (fx == fy) { 
            return false;
        }
        if (obj->size[fx] < obj->size[fy]) { 
            swap(&fx, &fy);
        }
        obj->size[fx] += obj->size[fy];
        obj->f[fy] = fx;
        obj->setCount--;
        return true;
    }
    
    struct HashTable { 
        int val;
        UT_hash_handle hh;
    };
    
    int regionsBySlashes(char** grid, int gridSize) { 
        int n = gridSize;
        struct DisjointSetUnion* uf = malloc(sizeof(struct DisjointSetUnion));
        initDSU(uf, n * n * 4);
    
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < n; j++) { 
                int idx = i * n + j;
                if (i < n - 1) { 
                    int bottom = idx + n;
                    unionSet(uf, idx * 4 + 2, bottom * 4);
                }
                if (j < n - 1) { 
                    int right = idx + 1;
                    unionSet(uf, idx * 4 + 1, right * 4 + 3);
                }
                if (grid[i][j] == '/') { 
                    unionSet(uf, idx * 4, idx * 4 + 3);
                    unionSet(uf, idx * 4 + 1, idx * 4 + 2);
                } else if (grid[i][j] == '\\') { 
                    unionSet(uf, idx * 4, idx * 4 + 1);
                    unionSet(uf, idx * 4 + 2, idx * 4 + 3);
                } else { 
                    unionSet(uf, idx * 4, idx * 4 + 1);
                    unionSet(uf, idx * 4 + 1, idx * 4 + 2);
                    unionSet(uf, idx * 4 + 2, idx * 4 + 3);
                }
            }
        }
    
        struct HashTable* fathers = NULL;
        for (int i = 0; i < n * n * 4; i++) { 
            int fa = find(uf, i);
            struct HashTable* tmp;
            HASH_FIND_INT(fathers, &fa, tmp);
            if (tmp == NULL) { 
                tmp = malloc(sizeof(struct HashTable));
                tmp->val = fa;
                HASH_ADD_INT(fathers, val, tmp);
            }
        }
        return HASH_COUNT(fathers);
    }

**运行结果：**  
![在这里插入图片描述][2021012510110441.png_pic_center]  
**Notes:**  
参考官方文档：[https://leetcode-cn.com/problems/regions-cut-by-slashes/solution/you-xie-gang-hua-fen-qu-yu-by-leetcode-s-ztob/][https_leetcode-cn.com_problems_regions-cut-by-slashes_solution_you-xie-gang-hua-fen-qu-yu-by-leetcode-s-ztob]

[77de6391e26d735259b692fd416dd50a.png_pic_center]: /images/20221119/c6553bd4f2314e25bf43cd88028363f1.png
[c2d082409a3f21805916767d13119888.png_pic_center]: /images/20221119/8b595c9b302f4b9a84b32dbbbdd6f363.png
[aa9c81109afdd0d9fa15b9ba45bbfda4.png_pic_center]: /images/20221119/6738c69ce15949a0b6dcc28d7a8c4922.png
[34ef7330f08825c9a4fbe8887d2fca5e.png_pic_center]: https://img-blog.csdnimg.cn/img_convert/34ef7330f08825c9a4fbe8887d2fca5e.png#pic_center
[424424f4e1284458280bab0adfe8fe83.png_pic_center]: https://img-blog.csdnimg.cn/img_convert/424424f4e1284458280bab0adfe8fe83.png#pic_center
[2021012510110441.png_pic_center]: https://img-blog.csdnimg.cn/2021012510110441.png#pic_center
[https_leetcode-cn.com_problems_regions-cut-by-slashes_solution_you-xie-gang-hua-fen-qu-yu-by-leetcode-s-ztob]: https://leetcode-cn.com/problems/regions-cut-by-slashes/solution/you-xie-gang-hua-fen-qu-yu-by-leetcode-s-ztob/