面试题 08.02 Robot in a Grid.md

Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are "off limits" such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.

"off limits" and empty grid are represented by 1 and 0 respectively.

Return a valid path, consisting of row number and column number of grids in the path.

Examples:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: [[0,0],[0,1],[0,2],[1,2],[2,2]]

Solution

c++

class Solution {
public:
    vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
        int r = obstacleGrid.size(), c = obstacleGrid[0].size();
        vector<vector<bool>> dp(r+1, vector<bool>(c+1, false));
        vector<vector<int>> result;

        if (r != 0 && c != 0 && (obstacleGrid[0][0] == 1 || obstacleGrid[r-1][c-1] == 1))
            return {};

        dp[1][1] = true;

        for (int i = 1; i <= r; i++)
            for (int j = 1; j <= c; j++)
                if (i != 1 || j != 1)
                    dp[i][j] = obstacleGrid[i-1][j-1] == 0 && (dp[i][j-1] || dp[i-1][j]);

        if (!dp[r][c]) return {};
            
        result.push_back({r-1, c-1});
        while (true){
            if (r == 1 && c == 1) break;
            if (c >= 2 && dp[r][c-1]) c--;
            else r--;
            result.push_back({r-1, c-1});
        }
        reverse(result.begin(), result.end());

        return result;
    }
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：8.7 MB, 在所有 C++ 提交中击败了87.23%的用户