leetcode-63. Unique Paths II 不同路徑2

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as  1  and   respectively in the grid. Note: m and n will be at most 100. Example 1: Input: [   [0,0,0],   [0,1,0],   [0,0,0] ] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right

一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中标記為“Start” ）。 機器人每次隻能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中标記為“Finish”）。 現在考慮網格中有障礙物。那麼從左上角到右下角将會有多少條不同的路徑？ 網格中的障礙物和空位置分别用  1  和   來表示。 說明：m 和 n 的值均不超過 100。 示例 1: 輸入: [   [0,0,0],   [0,1,0],   [0,0,0] ] 輸出: 2 解釋: 3x3 網格的正中間有一個障礙物。 從左上角到右下角一共有 2 條不同的路徑： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右

思路：和上一題類似。隻不過處理障礙物時 隻需要把目前可能路徑置為0就行，其他和上一題一樣。dp就完了，注意的是可以申請個二維數組，也可以申請一個一維數組。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid.size()==0 || obstacleGrid[0].size()==0 || obstacleGrid[0][0]==1)
            return 0;
        vector<vector<int>> dp(obstacleGrid.size(),vector<int>  (obstacleGrid[0].size(),0));
        for(int i=0;i<obstacleGrid.size();++i)
        {
            for(int j=0;j<obstacleGrid[0].size();++j)
            {
                if(obstacleGrid[i][j]==1) dp[i][j]=0;
                else if(i==0 && j==0) dp[i][j]=1;
                else if(i==0 && j>0) dp[i][j]=dp[i][j-1];
                else if(i>1 && j==0) dp[i][j]=dp[i-1][j];
                else dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp.back().back();
    }
};