C++刷leetcode（980. 不同路径 III）【深度优先搜索+回溯】
题目描述：在二维网格 grid 上，有 4 种类型的方格：
1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目，每一个无障碍方格都要通过一次。
示例 1：
输入：[,,]
输出：2
解释：我们有以下两条路径：
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
示例 2：
输入：[,,]
输出：4
解释：我们有以下四条路径：
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)
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)
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)
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)
示例 3：
输入：[,]
输出：0
解释：
没有一条路能完全穿过每一个空的方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。
提示：
1 <= grid.length * grid.length <= 20
class Solution {
public:
void dfs(vector<vector<int> > &grid, int& res, vector<vector<int> >& visit,
int start1, int start2, int sum, int len){
if(grid == -1|| visit == 3)return;
if(grid == 2){
if(sum == len-1)res++;
return;
}
visit = 3;
if(start1 + 1 < grid.size())dfs(grid, res, visit, start1+1, start2, sum, len+1);
if(start1 - 1 >= 0)dfs(grid, res, visit, start1-1, start2, sum, len+1);
if(start2 + 1 < grid.size())dfs(grid, res, visit, start1, start2+1, sum, len+1);
if(start2 - 1 >= 0)dfs(grid, res, visit, start1, start2-1, sum, len+1);
if(grid == 1)return;
else visit = 0;
}
int uniquePathsIII(vector<vector<int>>& grid) {
int res = 0;
int len1 = grid.size(), len2 = grid.size();
vector<vector<int> > visit = grid;
int start1,start2;
int sum = 0;
for(int i = 0; i < len1; i++){
for(int j = 0; j < len2; j++){
if(grid == 1){
start1 = i;
start2 = j;
}
else if(grid == 0) sum++;
}
}
dfs(grid, res, visit, start1, start2, sum, 0);
return res;
}
}; 注意题目描述：“每一个无障碍方格都要通过一次”
页:
[1]