[数据结构与算法]力扣面试题08.02.:迷路的机器人（可回溯、可动态规划）

一、题目内容

? ? ? ?

?二、题目分析

? ? ? ? 机器人从左上角开始运动，每次只可以向右或者向下运动，不可以经过障碍物，到达右下角为成功。

? ? ? ? 那我们从（0,0）点开始，分别向右向下运动，如果运动的坐标超出的边界或者碰到障碍物或者坐标被访问过，就返回，如果是正常可访问的坐标，就将它放到数组中去，并且给它标记为已访问。

? ? ? ? 接下来我们需要判断，当前访问的点是否是右下角的点，如果是，就结束一切操作，否则继续向下个坐标进发。

class Solution {
    boolean flag=false; 
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
         int m=obstacleGrid.length;
    int n=obstacleGrid[0].length;
        boolean [][]visited=new boolean[m][n];
        List<List<Integer>> list=new ArrayList<>();
        backtrack(list,0,0,obstacleGrid,visited);
        return list;
    }
    public void backtrack(List<List<Integer>> list,int i,int j,int [][]obstacleGrid,boolean[][]visited)
    {
        if(i>=obstacleGrid.length||j>=obstacleGrid[0].length||i<0||j<0||obstacleGrid[i][j]==1||visited[i][j])
        {
            return;
        }
        list.add(Arrays.asList(i, j));
         visited[i][j]=true;
       
        if((i==obstacleGrid.length-1)&&(j==obstacleGrid[0].length-1))
            flag=true;
        if(flag==false)
            backtrack(list,i+1,j,obstacleGrid,visited);
        if(flag==false)
            backtrack(list,i,j+1,obstacleGrid,visited);
        if(flag==false)
            list.remove(list.size()-1);
    }
}

? ? ? ? 这部分是未经优化的代码，可以看到我用了大量的额外空间去标记它的访问情况，但是其实访问过的点可以直接将它设置为1，也就是看做障碍物，这样也可以达到不重复访问的效果。

? ? ? ? 还有一点就是，我重复的使用了诸如obstacleGrid.length之类复杂的语句，可以将它们直接定义为类的属性，简化代码。

? ? ? ? ?另外还有一点需要提一下,在下面这句判断中

 if(i>=obstacleGrid.length||j>=obstacleGrid[0].length||i<0||j<0||obstacleGrid[i][j]==1)
        {
            return;
        }

? ? ?obstacleGrid[i][j]==1这句一定要写在最后面，因为前面的语句只要有一个正确，就会直接进入底下的return，不会执行 ?obstacleGrid[i][j]==1。但是如果将它放在第一个，可能i,j下标越界而错误。

????????? 最后就是为什么最后要写三个if语句，而不是将这三个语句写到一个if里。因为第一个

backtrack(list,i+1,j,obstacleGrid,visited);

?执行完之后，可能已经访问到最后一个点了，flag为true，可以直接退出了，但是如果写在一个if里，那么上面的程序执行完之后，还需要继续执行，显然有问题。

底下是简化后的代码：

class Solution {
    boolean flag=false; 
    int m,n;
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        m=obstacleGrid.length;
        n=obstacleGrid[0].length;
        backtrack(0,0,obstacleGrid);
        return list;
    }
    public void backtrack(int i,int j,int [][]obstacleGrid)
    {
        if(i>=obstacleGrid.length||j>=obstacleGrid[0].length||i<0||j<0||obstacleGrid[i][j]==1){
            return;
        }
        list.add(Arrays.asList(i, j));
        obstacleGrid[i][j]=1;       
        if((i==m-1)&&(j==n-1))
            flag=true;
        if(flag==false)
            backtrack(i+1,j,obstacleGrid);
        if(flag==false)
            backtrack(i,j+1,obstacleGrid);
        if(flag==false)
            list.remove(list.size()-1);
    }
}

????????

? ? ? ? 这个题目我已经全都在原数组操作了，但是内存消耗还是很大，?可以试试用动态规划做，先判断起点到终点是否可达，再倒序求路径。

（这部分非原创）
class Solution {
public:
    vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
        vector<vector<int>> res;
        int rows = obstacleGrid.size();
        int cols = obstacleGrid[0].size();
        // 先排除边缘情况，起点和重点不可达
        if (obstacleGrid[0][0] == 1 || obstacleGrid[rows-1][cols-1] ==1)
        {
            return res;
        }

        // 初始化
        bool d[rows][cols];
        memset(d, 0, sizeof(bool)*rows*cols);
        d[0][0] = 1;
        // 首列
        for (int i = 1; i < rows; ++i)
        {
            d[i][0] = (obstacleGrid[i][0] == 0) && d[i-1][0];
        }
        // 首行
        for (int j = 1; j < cols; ++j)
        {
            d[0][j] = (obstacleGrid[0][j] == 0) && d[0][j-1];
        }

        // 计算
        for (int i = 1; i < rows; ++i)
        {
            for (int j = 1; j < cols; ++j)
            {
                // 这里把两种情况都合并在一起了
                // 先判断是否为0
                // 再判断上一次位置是否可达
                d[i][j] = (obstacleGrid[i][j] == 0) && (d[i-1][j] || d[i][j-1]);
            }
        }

        // 结果
        // 如果不可达，直接返回空结果
        if (!d[rows-1][cols-1])
        {
            return res;
        }
        // 可达，倒序计算
        int i = rows-1;
        int j = cols-1;
        while (i > 0 || j > 0)
        {
            // cout << i << "," << j << endl;
            res.push_back({i, j});
            // 判断上一步是上方的情况是否可达
            if (i > 0 && d[i-1][j])
            {
                --i;
            }
            else
            {
                // 因为最后是可达，所以这里必然有一个可达的, 考虑上一步是左边的情况
                --j;
            }
        }
        // 插入起点
        res.push_back({0,0});
        // 倒序
        reverse(res.begin(), res.end());
        return res;
    }
};

????????

?三、感言

? ? ? ? 动态规划几天没写，怎么手生了呢? ctmd....