63. 不同路径 II
2024-09-04 10:27:18
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1
和 0
来表示。
说明:m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有2
条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[].size(); vector<vector<int>> dfs = vector<vector<int>>(m+,vector<int>(n+,));
if (obstacleGrid[][] == )
dfs[][] = ;
for (int i = ; i <= m; i++) {
for (int j = ; j <= n; j++) {
if (obstacleGrid[i-][j-] == ) {
dfs[i][j] += dfs[i-][j];
dfs[i][j] += dfs[i][j-];
}
}
}
return dfs[m][n];
}
};
最新文章
- 笔记本电脑关闭小键盘(即打字按P出现星号键)
- Connect教程系列--响应式布局(一)
- linux_c学习笔记之curl的使用一
- HDU 4349 Xiao Ming&#39;s Hope
- 在Windows 7上安装MongoDB 2.6.7
- HW7.18
- centos6.5下Python IDE开发环境搭建
- 算法导论学习-prim算法
- AddForce给物体添加刚体效果并且脚本增加一个力(按空格实现)
- Android 流媒体系列(一)
- jsp截取字符串
- ORA-00020的思考
- 成不了天才,但为何也没成";人材";?(转)
- gulp+browser-sync使用方法
- 201521123066 《Java程序设计》第三周学习总结
- 【开发技术】 B/S、C/S的区别
- 开源)嗨,Java,你可以生成金山词霸的二维码分享海报吗?
- 配置多版本jdk
- kubernetes核心概念
- P1025 数的划分 dfs dp