题目
设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。
网格中的障碍物和空位置分别用 1 和 0 来表示。
返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。
示例 1:
输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: [[0,0],[0,1],[0,2],[1,2],[2,2]] 解释: 输入中标粗的位置即为输出表示的路径，即 0行0列（左上角） -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列（右下角）
解题
乍一看这题，想起了leetcode-63：不同路径 II这道题，题目背景是一样的
但是此题，需要求一条路径，因此采用动态规划不太合适，可以采用记忆化递归+深度优先搜索+回溯
方法一：记忆化递归+回溯
由于只要找到一个路径，因此回溯具有返回值bool
由于初始加入{0,0}，对于结果，如果返回true,则为path，否则为{}
if(i==m-1&&j==n-1&&obstacleGrid[i][j]==0) 一定要补充obstacleGrid[i][j]==0,因为如果终点是障碍的，显然是不行的
由于，每个格子(i,j)可能会重复访问到，之前访问过，就说明这条路线不通。因此当(i,j)朝2个方向遍历完后，没有返回true，那么就visited[i][j]=true;标记已访问,可以大大减少时间复杂度。
写法一：
class Solution { public: vector<vector<int>> path; bool backtracing(vector<vector<int>>& obstacleGrid,vector<vector<int>>& dirs,int m,int n,int i,int j,vector<vector<bool>>& visited){ if(i==m-1&&j==n-1&&obstacleGrid[i][j]==0){ return true; } else if(i>=m||j>=n) return false; for(vector<int>& dir:dirs){ if(obstacleGrid[i][j]||visited[i][j]) break; i+=dir[0]; j+=dir[1]; path.push_back({i,j}); if(backtracing(obstacleGrid,dirs,m,n,i,j,visited)) return true; i-=dir[0]; j-=dir[1]; path.pop_back(); } visited[i][j]=true;//记忆化 return false; } vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) { int m=obstacleGrid.size(); int n=obstacleGrid[0].size(); vector<vector<int>> dirs={{1,0},{0,1}}; path.push_back({0,0}); vector<vector<bool>> visited(m,vector<bool>(n,false)); if(backtracing(obstacleGrid,dirs,m,n,0,0,visited)) return path; else return {}; } };
写法二：
更加简洁的写法,每次递归，都先处理，当前对应的(i,j) 。
而上面一种写法是提前将下一次递归的内容加入到path中去。
class Solution { public: vector<vector<int>> path; bool backtracing(vector<vector<int>>& obstacleGrid,int m,int n,int i,int j,vector<vector<bool>>& visited){ if(i>=m||j>=n||obstacleGrid[i][j]||visited[i][j]) return false; path.push_back({i,j}); if(i==m-1&&j==n-1||backtracing(obstacleGrid,m,n,i+1,j,visited)||backtracing(obstacleGrid,m,n,i,j+1,visited)) return true; path.pop_back(); visited[i][j]=true; return false; } vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) { int m=obstacleGrid.size(); int n=obstacleGrid[0].size(); vector<vector<bool>> visited(m,vector<bool>(n,false)); backtracing(obstacleGrid,m,n,0,0,visited); return path; } };
