C++刷leetcode（980. 不同路径 III）【深度优先搜索+回溯】

糖逗

题目描述：

1. 在二维网格 grid 上，有 4 种类型的方格：
   
2. 
   
3. 1 表示起始方格。且只有一个起始方格。
   
4. 2 表示结束方格，且只有一个结束方格。
   
5. 0 表示我们可以走过的空方格。
   
6. -1 表示我们无法跨越的障碍。
   
7. 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目，每一个无障碍方格都要通过一次。
   
8. 
   
9.  
   
10. 
    
11. 示例 1：
    
12. 
    
13. 输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
    
14. 输出：2
    
15. 解释：我们有以下两条路径：
    
16. 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
    
17. 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
    
18. 示例 2：
    
19. 
    
20. 输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
    
21. 输出：4
    
22. 解释：我们有以下四条路径：
    
23. 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
    
24. 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
    
25. 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
    
26. 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
    
27. 示例 3：
    
28. 
    
29. 输入：[[0,1],[2,0]]
    
30. 输出：0
    
31. 解释：
    
32. 没有一条路能完全穿过每一个空的方格一次。
    
33. 请注意，起始和结束方格可以位于网格中的任意位置。
    
34.  
    
35. 
    
36. 提示：
    
37. 
    
38. 1 <= grid.length * grid[0].length <= 20
    

复制代码

1. class Solution {
   
2. public:
   
3.     void dfs(vector<vector<int> > &grid, int& res, vector<vector<int> >& visit,
   
4.     int start1, int start2, int sum, int len){
   
5.         if(grid[start1][start2] == -1|| visit[start1][start2] == 3)return;
   
6.         if(grid[start1][start2] == 2){
   
7.             if(sum == len-1)res++;
   
8.             return;
   
9.         }
   
10.         visit[start1][start2] = 3;
    
11.         if(start1 + 1 < grid.size())dfs(grid, res, visit, start1+1, start2, sum, len+1);
    
12.         if(start1 - 1 >= 0)dfs(grid, res, visit, start1-1, start2, sum, len+1);
    
13.         if(start2 + 1 < grid[0].size())dfs(grid, res, visit, start1, start2+1, sum, len+1);
    
14.         if(start2 - 1 >= 0)dfs(grid, res, visit, start1, start2-1, sum, len+1);
    
15.         if(grid[start1][start2] == 1)return;
    
16.         else visit[start1][start2] = 0;
    
17.     }
    
18.     int uniquePathsIII(vector<vector<int>>& grid) {
    
19.         int res = 0;
    
20.         int len1 = grid.size(), len2 = grid[0].size();
    
21.         vector<vector<int> > visit = grid;
    
22.         int start1,start2;
    
23.         int sum = 0;
    
24.         for(int i = 0; i < len1; i++){
    
25.             for(int j = 0; j < len2; j++){
    
26.                 if(grid[i][j] == 1){
    
27.                     start1 = i;
    
28.                     start2 = j;
    
29.                 }
    
30.                 else if(grid[i][j] == 0) sum++;
    
31.             }
    
32.         }
    
33.         dfs(grid, res, visit, start1, start2, sum, 0);
    
34.         return res;
    
35.     }
    
36. };

复制代码

糖逗

注意题目描述：“每一个无障碍方格都要通过一次”