🎈算法那些事专栏说明:这是一个记录刷题日常的专栏,每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目,在这立下Flag🚩
🏠个人主页:Jammingpro
📕专栏链接:算法那些事
🎯每日学习一点点,技术累计看得见
题目
题目描述
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
执行示例
示例 1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1.向右 -> 向右 -> 向下 -> 向下
2.向下 -> 向下 -> 向右 -> 向右
示例 2:
输入:obstacleGrid = [[0,1],[0,0]]
输出:1
提示
m==obstacleGrid.length
n ==obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1
题解
这一题是LeetCode.62不同路径的进阶题。由于机器人只能向下或向右走,所以到达第0行和第0列各个方格的方法数均为1。若不考虑障碍物的情况下,到达第i行第j列的方法数为map[i][j]=map[i][j-1]+map[i-1][j],因为可以从上面一行向下走1步到达,也可以从左侧向右走1步到达。如下图所示↓↓↓
但这题是有障碍物的。如果第i行第j列有障碍物,则到达该方格的方法数为0,即map[i][j]=0,其余步骤均与LeetCode.62不同路径相同,即计算到达第i行第j列的方法数,可通过map[i][j]=map[i][j-1]+map[i-1][j]
计算得到。下面我们来实现一下代码↓↓↓
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>>map(m, vector<int>(n));
for(int i = 0; i < m; i++)
{
if(obstacleGrid[i][0] == 1) break;
map[i][0] = 1;
}
for(int i = 0; i < n; i++)
{
if(obstacleGrid[0][i] == 1) break;
map[0][i] = 1;
}
for(int i = 1; i < m; i++)
for(int j = 1; j < n; j++)
if(obstacleGrid[i][j] == 1) map[i][j] = 0;
else map[i][j] = map[i - 1][j] + map[i][j - 1];
return map[m - 1][n - 1];
}
};
我们可以通过多开辟1行1列,并将map[0][1]初始化为1的方式,避免了两个循环初始化第0行第0列元素。↓↓↓
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>>map(m + 1,vector<int>(n + 1));
map[0][1] = 1;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
if(obstacleGrid[i - 1][j - 1] == 1)
map[i][j] = 0;
else
map[i][j] = map[i - 1][j] + map[i][j - 1];
return map[m][n];
}
};
本文存在不足,欢迎留言或私信批评、指正。希望我的解决方法能够对你有所帮助~~
今日打卡完成,点亮小星星☆→★