[LeetCode] 63. Unique Paths II

正午 2020-01-07 PM 16℃ 0条

这题是62 的变种, 输入一个 m 行 n 列的二维数组,其中为1 的表示遇到障碍,不能通行,求机器人从左上角走到右下角有几种走法

解题思路还是动态规划,并没太大变化,唯一不同的是 遇到任何1 的点 dpi = 0

下面的代码有个小问题,paths 里存的是 long , 主要是 leetcode 存 int 会报错,其实并没错。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<long>> paths(m, vector<long>(n, 0));
        if(obstacleGrid[0][0]==1){
            return 0;
        }
        for(int i=0; i< m ; i++){
            if (obstacleGrid[i][0]==1){
                break;
            }
            paths[i][0] = 1;
        }
        for(int j=0; j< n; j++){
            if(obstacleGrid[0][j]==1){
                break;
            }
            paths[0][j] = 1;
        }
        for(int i=1; i < m; i++ ){
            for(int j=1; j < n; j++){
                if (obstacleGrid[i][j] != 1){
                    paths[i][j] = paths[i][j-1] + paths[i-1][j];
                }
                
            }
        }
        return paths[m-1][n-1];
    }
};
标签: LeetCode

非特殊说明,本博所有文章均为博主原创。

评论