【Leetcode】63. Unique Paths II（动态规划）

曾经终败给现在 2022-02-27 10:24 185阅读 0赞

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?

![robot_maze.png][]

An obstacle and empty space is marked as `1` and `0` 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

题目大意：

给出一个二维矩阵，其中包含0和1两种状态，0代表可以通过，1则代表无法通过；输出从左上角到右下角的路径个数，注意此时只可以向右或者向下走。

解题思路：

题目与62题类似，只是多出了一个无法通过的状态。按照62题的思路，我们希望计算出到达每个位置的个数，然后动态规划。对本题而言，我们可以看出在标注为1的位置是永远无法到达的，所以在遍历时应该将此处的个数设为0。

同时在初始化第一行第一列时，我们需要注意，因为机器人只允许往下走不允许往上，所以我们在初始化第一行第一列时应该注意，如果出现1则本位置和之后的所有位置都无法到达，即标注其值为0.

**注：此题使用c++会超出int的范围，将变量设为 long long int。**

62题题解：[https://blog.csdn.net/qq\_29600137/article/details/88734291][https_blog.csdn.net_qq_29600137_article_details_88734291]

附C++ faster than 100.00% 代码

class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
            
            if(obstacleGrid[0][0]==1)
                return 0;
            
            long long int n,m;
            n = obstacleGrid.size();
            m = obstacleGrid[0].size();
            long long int map[n][m];
            bool state_row = false;
            for(int i=0;i<m;i++){
                if (obstacleGrid[0][i] == 1 || state_row){
                    map[0][i] = 0;
                    state_row = true;
                    continue;
                }
    			map[0][i] = 1;
    		} 
            
            bool state_line = false;
    		for(int i=0;i<n;i++){
                if (obstacleGrid[i][0] == 1 || state_line){
                    map[i][0] = 0;
                    state_line = true;
                    continue;
                }
    			map[i][0] = 1;
    		}
            
            for(int i=1;i<n;i++){
    			for(int j=1;j<m;j++){
                    
                    if(obstacleGrid[i][j] == 1){
                        map[i][j] = 0;
                        continue;
                    }
                    
                    if(obstacleGrid[i][j-1]!=1 && obstacleGrid[i-1][j]!=1)
    				    map[i][j] = map[i][j-1] + map[i-1][j];
                    else{
                        if(obstacleGrid[i][j-1]==1 && obstacleGrid[i-1][j]!=1)
                            map[i][j] = map[i-1][j];
                        else if(obstacleGrid[i][j-1]!=1 && obstacleGrid[i-1][j]==1){
                            map[i][j] = map[i][j-1];
                        }else{
                            map[i][j] = 0;
                        }
                    }
    			}
    		}
            return map[n-1][m-1];
        }
    };

[robot_maze.png]: https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png
[https_blog.csdn.net_qq_29600137_article_details_88734291]: https://blog.csdn.net/qq_29600137/article/details/88734291