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]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

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


版权声明:本文博客原创文章,博客,未经同意,不得转载。






本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/4713938.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中出现了?
49 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网格的左上角(在下图中标记为“开始”)。 机器人只能在任何时间点向下或向右移动。 机器人正试图到达网格的右下角(在下图中标记为“完成”)。 现在考虑是否在网格中添加了一些障碍。 有多少条独特的路径?
98 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
79 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
|
算法 机器人 人工智能