面试题 08.02

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.

Example 1:

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

r, c <= 100

Solutions

1. dfs with memoization

2. dynamic programming with backtracking

3. Record tansitions(this state comes from which) at the time when updating the dp table.

4. Then after the dp table is filled, backtracking from the final state(right-bottom) to the initial state(0, 0), the traversing path is a valid answer.

class Solution {
public:
    enum Direction {RIGHT = 1, DOWN = 2};
    vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(); if (!m) return {};
        int n = obstacleGrid[0].size();
        if (obstacleGrid[0][0] == 1) return {};
        // dynamic programming with dp transitions recorded
        vector<vector<int>> dp(m, vector<int>(n));
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j])
                    dp[i][j] = 0;
                else if (i > 0 && dp[i - 1][j])
                    dp[i][j] = DOWN;
                else if (j > 0 && dp[i][j - 1])
                    dp[i][j] = RIGHT;
            }
        }

        int i = m - 1, j = n - 1;
        vector<vector<int>> res;
        // backtracking from the bottom right point, find a valid path.
        if (dp[i][j] != 0) {
            while (j >= 0) {
                res.push_back({i, j});
                (dp[i][j] == RIGHT ? j : i)--;
            }
            reverse(res.begin(), res.end());
        }
        return res;
    }
};