C++刷LeetCode（959. 由斜杠划分区域）【深度优先搜索】【问题转化】

糖逗

题目描述：

1. 在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
   
2. 
   
3. （请注意，反斜杠字符是转义的，因此 \ 用 "\" 表示。）。
   
4. 
   
5. 返回区域的数目。
   
6. 
   
7.  
   
8. 
   
9. 示例 1：
   
10. 
    
11. 输入：
    
12. [
    
13.   " /",
    
14.   "/ "
    
15. ]
    
16. 输出：2
    
17. 解释：2x2 网格如下：
    
18. 
    
19. 示例 2：
    
20. 
    
21. 输入：
    
22. [
    
23.   " /",
    
24.   "  "
    
25. ]
    
26. 输出：1
    
27. 解释：2x2 网格如下：
    
28. 
    
29. 示例 3：
    
30. 
    
31. 输入：
    
32. [
    
33.   "\\/",
    
34.   "/\"
    
35. ]
    
36. 输出：4
    
37. 解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\" 表示 /\。）
    
38. 2x2 网格如下：
    
39. 
    
40. 示例 4：
    
41. 
    
42. 输入：
    
43. [
    
44.   "/\",
    
45.   "\\/"
    
46. ]
    
47. 输出：5
    
48. 解释：（回想一下，因为 \ 字符是转义的，所以 "/\" 表示 /\，而 "\\/" 表示 \/。）
    
49. 2x2 网格如下：
    
50. 
    
51. 示例 5：
    
52. 
    
53. 输入：
    
54. [
    
55.   "//",
    
56.   "/ "
    
57. ]
    
58. 输出：3
    
59. 解释：2x2 网格如下：
    
60. 
    
61.  
    
62. 
    
63. 提示：
    
64. 
    
65. 1 <= grid.length == grid[0].length <= 30
    
66. grid[i][j] 是&#160;'/'、'\'、或&#160;' '。
    
67. 
    
68. 来源：力扣（LeetCode）
    
69. 链接：https://leetcode-cn.com/problems/regions-cut-by-slashes
    
70. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. private:
   
3.     vector<vector<int> > dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
   
4.     int len;
   
5. public:
   
6.     void dfs(vector<vector<int> > & store, int i, int j){
   
7.         if(i < 0 || i >= 3*len || j < 0 || j >= 3*len || store[i][j] == 1)return;
   
8.         store[i][j] = 1;
   
9.         for(int k = 0; k < dir.size(); k++){
   
10.             dfs(store, i + dir[k][0], j + dir[k][1]);
    
11.         }
    
12.     }
    
13.     int regionsBySlashes(vector<string>& grid) {
    
14.         //转化输入
    
15.         len = grid.size();
    
16.         vector<vector<int> > store(3*len, vector<int>(3*len, 0));
    
17.         for(int i = 0; i < len; i++){
    
18.             for(int j = 0; j < len; j++){
    
19.                 if(grid[i][j] == '/'){
    
20.                     store[3*i][3*j + 2] = 1;
    
21.                     store[3*i + 1][3*j + 1] = 1;
    
22.                     store[3*i + 2][3*j] = 1;
    
23.                 }else if(grid[i][j] == '\\'){
    
24.                     store[3*i][3*j] = 1;
    
25.                     store[3*i + 1][3*j + 1] = 1;
    
26.                     store[3*i + 2][3*j + 2] = 1;
    
27.                 }
    
28.             }
    
29.         }
    
30.         int res = 0;
    
31.         for(int i = 0; i < 3*len; i++){
    
32.             for(int j = 0; j < 3*len; j++){
    
33.                 if(store[i][j] == 0){
    
34.                     dfs(store, i, j);
    
35.                     res += 1;
    
36.                 }
    
37.             }
    
38.         }
    
39.         return res;
    
40. 
    
41.     }
    
42. };

复制代码

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

糖逗