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[0].length <= 30
grid[i][j] 是 '/'、'\'、或 ' '。

来源：力扣（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[i][j] == 1)return;
        store[i][j] = 1;
        for(int k = 0; k < dir.size(); k++){
            dfs(store, i + dir[k][0], j + dir[k][1]);
        }
    }
    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[i][j] == '/'){
                    store[3*i][3*j + 2] = 1;
                    store[3*i + 1][3*j + 1] = 1;
                    store[3*i + 2][3*j] = 1;
                }else if(grid[i][j] == '\\'){
                    store[3*i][3*j] = 1;
                    store[3*i + 1][3*j + 1] = 1;
                    store[3*i + 2][3*j + 2] = 1;
                }
            }
        }
        int res = 0;
        for(int i = 0; i < 3*len; i++){
            for(int j = 0; j < 3*len; j++){
                if(store[i][j] == 0){
                    dfs(store, i, j);
                    res += 1;
                }
            }
        }
        return res;

    }
};

参考链接：https://leetcode-cn.com/problems ... i-jie-fa-by-godwei/

糖逗