# 面试题 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.

```cpp
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;
    }
};
```