C++刷LeetCode（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.length <= 30
grid 是 '/'、'\'、或 ' '。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regions-cut-by-slashes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
private:
vector<vector<int> > dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int len;
public:
void dfs(vector<vector<int> > & store, int i, int j){
if(i < 0 || i >= 3*len || j < 0 || j >= 3*len || store == 1)return;
store = 1;
for(int k = 0; k < dir.size(); k++){
dfs(store, i + dir, j + dir);
}
}
int regionsBySlashes(vector<string>& grid) {
//转化输入
len = grid.size();
vector<vector<int> > store(3*len, vector<int>(3*len, 0));
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
if(grid == '/'){
store = 1;
store = 1;
store = 1;
}else if(grid == '\\'){
store = 1;
store = 1;
store = 1;
}
}
}
int res = 0;
for(int i = 0; i < 3*len; i++){
for(int j = 0; j < 3*len; j++){
if(store == 0){
dfs(store, i, j);
res += 1;
}
}
}
return res;
}
};
参考链接：https://leetcode-cn.com/problems/regions-cut-by-slashes/solution/tu-jie-suan-fa-san-chong-xiang-xi-jie-fa-by-godwei/ {:10_248:}
页:
[1]