LeetCode959. 由斜杠划分区域(搜索)(并查集)
LeetCode959. 由斜杠划分区域(搜索)(并查集)
题目
在由 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 gridi 是 '/'、''、或 ' '。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/regions-cut-by-slashes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
将1x1方块转换成3x3方块，根据对角线填充1，其余填充0。 如果用搜索遍历循环的次数必须为4不能为8，所以如果把1x1方块转换成2x2方块，本来连通的区域会不连通 然后用DFS或BFS遍历： 该数字为0则搜索遍历
class Solution {
public:
vector<vector<int>> arr;
void DFS(int i, int j) {
arr[i][j] = 1;
if (j - 1 >= 0 && arr[i][j - 1] != 1) {
DFS(i, j - 1);
}
if (i + 1 < arr.size() && arr[i + 1][j] != 1) {
DFS(i + 1, j);
}
if (j + 1 < arr.size() && arr[i][j + 1] != 1) {
DFS(i, j + 1);
}
if (i - 1 >= 0 && arr[i - 1][j] != 1) {
DFS(i - 1, j);
}
}
int regionsBySlashes(vector<string>& grid) {
int num = 0;
vector<vector<int>> brr(grid.size() * 3, vector<int>(grid.size() * 3, 0));
arr = brr;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid.size(); j++) {
if (grid[i][j] == '/') {
arr[i * 3][j * 3 + 2] = arr[i * 3 + 1][j * 3 + 1] = arr[i * 3 + 2][j * 3] = 1;
}
if (grid[i][j] == '\\') {
arr[i * 3][j * 3] = arr[i * 3 + 1][j * 3 + 1] = arr[i * 3 + 2][j * 3 + 2] = 1;
}
}
}
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < arr.size(); j++) {
cout<<arr[i][j]<<" ";
if (arr[i][j] == 0) {
num++;
DFS(i, j);
}
}
cout<<endl;
}
return num;
}
};思路借鉴： 作者：MiloMusiala 链接：https://leetcode-cn.com/problems/regions-cut-by-slashes/solution/c-dong-hua-zhuan-huan-cheng-dao-yu-ge-sh-guve/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
腾讯云开发者
