Unique Paths II（C++不同路径 II）

短命女 2022-10-11 03:59 163阅读 0赞

（1）动态规划

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

发表评论取消回复

表情：

评论列表（有 0 条评论，163人围观）

还没有评论，来说两句吧...

相关阅读

相关 Unique Paths II（C++不同路径 II）

（1）动态规划 class Solution { public: int uniquePathsWithObstacles(vector

短命女/ 2022年10月11日 03:59/ 0 赞/ 164 阅读

相关 Unique Paths（C++不同路径）

（1）动态规划 class Solution { public: int uniquePaths(int m, int n) {

╰半橙微兮°/ 2022年10月11日 03:56/ 0 赞/ 144 阅读

相关 LeetCode63——Unique Paths II

LeetCode63——Unique Paths II 跟[LeetCode62——Unique Paths][LeetCode62_Unique Paths]不同的是，这里

曾经终败给现在/ 2022年08月09日 16:49/ 0 赞/ 160 阅读

相关 leetcode 63. Unique Paths II

Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. Ho

心已赠人/ 2022年07月30日 13:59/ 0 赞/ 122 阅读

相关 LeetCode-62. Unique Paths/63. Unique Paths II

62. Unique Paths Problem: > A robot is located at the top-left corner of a m x n gri

怼烎@/ 2022年07月27日 11:57/ 0 赞/ 173 阅读

相关 [Leetcode][python]Unique Paths/Unique Paths II

Unique Paths 题目大意机器人从起点到终点有多少条不同的路径，只能向右或者向下走。解题思路动态规划由于只能有向下向右，只有从\[1\]

左手的ㄟ右手/ 2022年06月07日 07:13/ 0 赞/ 401 阅读

相关 LeetCode 63.Unique Paths II (不同路径 II)

题目描述：一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（

比眉伴天荒/ 2022年05月10日 05:36/ 0 赞/ 197 阅读

相关 LeetCode 62.Unique Paths (不同路径)

题目描述: 一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图

青旅半醒/ 2022年05月10日 05:30/ 0 赞/ 191 阅读

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

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram

曾经终败给现在/ 2022年02月27日 10:24/ 0 赞/ 191 阅读

相关 LeetCode:63. Unique Paths II 机器人所有可行路径

试题 A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the di

系统管理员/ 2021年06月24日 16:12/ 0 赞/ 353 阅读