[]leetcode]Unique Paths II

简介:

Follow up for "Unique Paths":
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 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

题目大意
寻求最短路径,从左上走到右下,保证每次只能往左走或往下走(不可以斜着走)。其中数字1是障碍,表示“此路不通”,求总共的路线数


思路
   1. 如果没有障碍

val[i][0] = 1
val[0][j] = 1
val[i][j] = val[i-1][j] + val[i][j-1]

2. 有了障碍后
如果obstacle[i][j] = 1
val[i][j] = 1
否则
tmp = obstacle[i-1][j] == 1 ? 0 : val[i-1][j]
tmp = obstacle[i][j-1] == 1 ? tmp : tmp + val[i-1][j-1]
val[i][j] = tmp

参考代码
复制代码
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int row = obstacleGrid.size();
        int col = obstacleGrid[0].size();
        int token = 1;
        int val[row][col];
        for (int j = 0; j < col; ++j)
        {
            if(obstacleGrid[0][j] == 1)
                token = 0;
            val[0][j] = token;
            
        }
        token = 1;
        for (int i = 0; i < row; ++i)
        {
            if(obstacleGrid[i][0] == 1)
                token = 0;
            val[i][0] = token;
        }
        for (int i = 1; i < row; ++i)
        {
            for(int j = 1; j < col; ++j)
            {
                if (obstacleGrid[i][j] == 1)
                    val[i][j] = 0;
                else
                {
                    int tmp = obstacleGrid[i-1][j] == 1 ? 0 :val[i-1][j];
                    tmp = obstacleGrid[i][j-1] == 1 ? tmp : tmp + val[i][j-1];
                    val[i][j] = tmp;
                }
            }
        }
        return val[row-1][col-1];
    }
};
复制代码

 





本文转自jihite博客园博客,原文链接:http://www.cnblogs.com/kaituorensheng/p/3806896.html,如需转载请自行联系原作者


相关文章
|
搜索推荐 机器人 SEO
Leetcode 62. Unique Paths & 63. Unique Paths II
原谅我重新贴一遍题目描述,不是为了凑字数,而是为了让搜索引擎能索引到这篇文章,其实也是算一种简单的SEO。 简单描述下题目,有个机器人要从左上角的格子走到右下角的格子,机器人只能向下或者向右走,总共有多少种可能的路径?
35 0
|
Java
Leetcode 467. Unique Substrings in Wraparound String
大概翻译下题意,有个无限长的字符串s,是由无数个「abcdefghijklmnopqrstuvwxy」组成的。现在给你一个字符串p,求多少个p的非重复子串在s中出现了?
48 0
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
LeetCode 257. Binary Tree Paths
给定一个二叉树,返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。
57 0
LeetCode 257. Binary Tree Paths
|
机器人
LeetCode 63. Unique Paths II
机器人位于m x n网格的左上角(在下图中标记为“开始”)。 机器人只能在任何时间点向下或向右移动。 机器人正试图到达网格的右下角(在下图中标记为“完成”)。 现在考虑是否在网格中添加了一些障碍。 有多少条独特的路径?
97 0
LeetCode 63. Unique Paths II
|
机器人
LeetCode 62. Unique Paths
机器人位于m x n网格的左上角(在上图中标记为“开始”)。 机器人只能在任何时间点向下或向右移动。 机器人正试图到达网格的右下角(在下图中标记为“完成”)。 有多少可能的独特路径?
80 0
LeetCode 62. Unique Paths
|
数据安全/隐私保护 C++ Python
LeetCode 804. Unique Morse Code Words
LeetCode 804. Unique Morse Code Words
77 0
Leetcode-Easy 804. Unique Morse Code Words
Leetcode-Easy 804. Unique Morse Code Words
102 0
Leetcode-Easy 804. Unique Morse Code Words
LeetCode之First Unique Character in a String
LeetCode之First Unique Character in a String
116 0
|
算法 机器人 人工智能