【回溯】不同路径Ⅲ，来看看如何处理！
【回溯】不同路径Ⅲ，来看看如何处理！
980. 不同路径 III
在二维网格 grid 上，有 4 种类型的方格：
1表示起始方格。且只有一个起始方格。2表示结束方格，且只有一个结束方格。0表示我们可以走过的空方格。-1表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目 。
每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
示例 1：
输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-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：
输入：[[1,0,0,0],[0,0,0,0],[0,0,0,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],[2,0]]
输出：0
解释：
没有一条路能完全穿过每一个空的方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。提示：
1 <= grid.length * grid[0].length <= 20
解题思路：深度优先遍历
其实这道困难题用暴力搜索就能解决了，思路很简单，我们可以 先遍历一下原二维网格，然后用一个全局变量 step 记录下网格中的 0 和 2 的个数，因为题目要求每一个无障碍方格都要通过一次，所以最后计算出的路径，必须是包含了所有的 0 和一个 2 的路径，所以可以用该变量来判断！此外我们可以在遍历网格过程中顺便将入口也就是 1 的坐标记录下来，然后后面直接将坐标传给递归函数去进行深度优先遍历即可！
剩下的操作无非就是完成我们的递归函数，还是用深度优先遍历的方法来遍历这些可能的路径，只不过判断条件变了，其他的都是大同小异的！
递归函数中无非就是三步走：
函数头的设计：
首先少不了的就是题目给的网格 grid。
此外因为我们需要判断当前位置是否越界，所以需要有当前位置在网格中的坐标，所以需要 x 和 y 来表示，而我们一开始在主函数中传入的参数就是遍历找到的入口坐标！
最后我们还要搞个变量 cur 来记录的路径长度，方便和 step 进行判断！
void dfs(vector<vector<int>>& grid, int x, int y, int cur);递归函数出口：
因为这道题要求一条路径中不能重复通过同一个方格，所以我们需要一个 全局的布尔类型二维数组 used 来标记当前位置是否已经走过，这样子往下的路径就能知道哪些该走哪些不该走！
然后主要就是判断以下内容，如果出现其中一个不符合的话，则直接 return false 即可：
- 当前在网格中的坐标是不是越界了
- 当前元素是否已经走过了
- 当前元素是否为
-1
此外我们还需要判断一下是否当前元素就是出口元素，是的话判断一下路径的长度是否和目标长度 step 一致，只有两者都符合才进行结果集的累加！
// 递归函数出口
if(x < 0 || x == grid.size() || y < 0 || y == grid[x].size() || used[x][y] == true || grid[x][y] == -1)
return;
if(grid[x][y] == 2 && step == cur)
{
ret++;
return;
}函数体的内容：
- 函数体要做的事情无非就是进行处理当前元素、递归、回溯操作：
- 对于这道题来说就是标记进行当前元素已经走过，也就是将
used[x][y] = true即可！ - 递归处理的话，就是上下左右去递归即可，也不需要关心是否走到重复的位置，因为在递归出口处我们已经进行了限制！
- 对于回溯操作的话，这里需要将
used[x][y] = false，然后就不需要处理其它问题了，因为其它变量对其它层没有影响，是局部的！
- 对于这道题来说就是标记进行当前元素已经走过，也就是将
class Solution {
private:
int ret; // 存放结果集
int step; // 存放原网格中0和2的个数总和
bool used[20][20]; // 标记当前位置是否已经走过，true表示走过
public:
int uniquePathsIII(vector<vector<int>>& grid) {
// 遍历原网格记录下入口的坐标，还有累加一下step变量
int x = 0;
int y = 0;
for(int i = 0; i < grid.size(); ++i)
{
for(int j = 0; j < grid[i].size(); ++j)
{
if(grid[i][j] == 0 || grid[i][j] == 2)
step++;
if(grid[i][j] == 1)
{
x = i;
y = j;
}
}
}
// 交给递归函数去处理即可
dfs(grid, x, y, 0);
return ret;
}
void dfs(vector<vector<int>>& grid, int x, int y, int cur)
{
// 递归函数出口
if(x < 0 || x == grid.size() || y < 0 || y == grid[x].size() || used[x][y] == true || grid[x][y] == -1)
return;
if(grid[x][y] == 2 && step == cur)
{
ret++;
return;
}
used[x][y] = true;
dfs(grid, x + 1, y, cur + 1);
dfs(grid, x - 1, y, cur + 1);
dfs(grid, x, y + 1, cur + 1);
dfs(grid, x, y - 1, cur + 1);
used[x][y] = false;
}
};腾讯云开发者
