LeetCode: 08.02 迷路的机器人（二维dp）

设想有个机器人坐在一个网格的左上角，网格 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列（右下角）
说明：r 和 c 的值均不超过 100。

分析：

       dfs的做法很明显，但是因为题目里有动态规划的标签，所以这里我也用动态规划做的。要想到达最后一个位置(n - 1, m - 1)，那么就得到达它上边的或者左边的一个位置，这就是状态转移。我们令可到达为“2”，使用原数组即可，标记完之后查询位置(n - 1, m - 1)的状态。然后从终点找一条路径，存放在栈里。也可以直接存放在ans里，最后reverse一下。

class Solution {
public:
    vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
        //如果可到达，设为2，不可到达设为1或0
        vector<vector<int>> ans;
        if(obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0 || obstacleGrid[0][0] == 1) return ans; 
        obstacleGrid[0][0] = 2;
        for(int i = 0; i < obstacleGrid.size(); i++){
            for(int j = 0; j < obstacleGrid[0].size(); j++){
                if(obstacleGrid[i][j] == 2){
                    //right
                    if(j < obstacleGrid[0].size() - 1 && obstacleGrid[i][j + 1] == 0) obstacleGrid[i][j + 1] = 2;
                    //down
                    if(i < obstacleGrid.size() - 1 && obstacleGrid[i + 1][j] == 0) obstacleGrid[i + 1][j] = 2; 
                }
            }
        }
        stack<vector<int>> s;
        int x = obstacleGrid.size() - 1, y = obstacleGrid[0].size() - 1;
        if(obstacleGrid[x][y] == 2){
            while(x != 0 || y != 0){
                s.push(vector<int>{x, y});
                if(x - 1 >= 0 && obstacleGrid[x - 1][y] == 2) x--;
                else if(y - 1 >= 0 && obstacleGrid[x][y - 1] == 2) y--;
            }
            s.push(vector<int>{0, 0});
        }
        while(!s.empty()){
            ans.push_back(s.top());
            s.pop();
        }
        return ans;
    }
};

最后

以上就是温暖流沙为你收集整理的LeetCode: 08.02 迷路的机器人（二维dp）的全部内容，希望文章能够帮你解决LeetCode: 08.02 迷路的机器人（二维dp）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。