Содержание
Постановка задачи
Вам дана сетка целочисленного массива m x n. В левом верхнем углу изначально находится робот (т.е. grid[0 [0]). Робот пытается переместиться в правый нижний угол (т.е., grid[m — 1][n — 1]). В любой момент времени робот может двигаться только вниз или вправо.
Препятствие и пространство обозначаются в сетке как 1 или 0 соответственно. Путь, по которому движется робот, не может включать ни одного квадрата, являющегося препятствием.
Верните количество возможных уникальных путей, по которым робот может добраться до правого нижнего угла.
Тестовые примеры генерируются таким образом, чтобы ответ был меньше или равен 2 * 10^9.
Постановка задачи взята с сайта: https://leetcode.com/problems/unique-paths-ii
Пример 1:
Input: obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3 x 3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
Пример 2:
Input: obstacleGrid = [[0, 1], [0, 0]]
Output: 1
Ограничения:
- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] is 0 or 1
Объяснение
Эта задача похожа на предыдущую статью нашего блога «Уникальные пути». Она может быть решена с помощью перебора или динамического программирования.
Но единственный случай, который нам нужно рассмотреть, — это препятствия на пути. Если в клетке [i, j] есть препятствие, то мы никак не сможем добраться до следующих клеток:
- [i, j + 1] // правая клетка
- [i + 1, j] // нижняя клетка
Мы можем просто пометить счетчик пути клетки [i, j] как 0. Это означает, что нет возможности достичь этой клетки.
Динамическое программирование
Основываясь на вышеизложенном подходе,
давайте перейдем непосредственно к алгоритму.
- set m = obstacleGrid.size()
n = obstacleGrid[0].size()
// if the top-left cell has an obstacle, the robot cannot be placed and
// start moving across the grid. We return 0 in such a case.
- if obstacleGrid[0][0] == 1
- return 0
// set the number of ways to reach the top-left cell as 1
- obstacleGrid[0][0] = 1
// following loop sets the number of ways to reach any cell in the left-most column.
// if we have an obstacle, mark the number of ways to reach that cell
// and all its bottom-adjacent cells as 0.
- loop for i = 1; i < m; i++
- if obstacleGrid[i][0] == 0
- obstacleGrid[i][0] += obstacleGrid[i - 1][0]
- else
- obstacleGrid[i][0] = 0
- for end
// following loop sets the number of ways to reach any cell in the top-most row.
// if we have an obstacle, mark the number of ways to reach that cell
// and all its right-adjacent cells as 0.
- loop for j = 1; j < n; j++
- if obstacleGrid[0][j] == 0
- obstacleGrid[0][j] += obstacleGrid[0][j - 1]
- else
- obstacleGrid[0][j] = 0
- for end
// add the number of ways to reach any cell in the rest of the matrix
- loop for i = 1; i < m; i++
- loop for j = 1; j < n; j++
- if obstacleGrid[i][j] == 0
- obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
- else
- obstacleGrid[i][j] = 0
- if end
- inner for end
- for end
- return obstacleGrid[m - 1][n - 1]
Временная сложность данного подхода составляет O(M * N), а пространственная сложность — O(1).
Давайте проверим наш алгоритм на C++, Golang и Javascript.
Решение на C++
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
if(obstacleGrid[0][0] == 1) {
return 0;
}
obstacleGrid[0][0] = 1;
for(int i = 1; i < m; i++) {
if(obstacleGrid[i][0] == 0) {
obstacleGrid[i][0] += obstacleGrid[i - 1][0];
} else {
obstacleGrid[i][0] = 0;
}
}
for(int j = 1; j < n; j++) {
if(obstacleGrid[0][j] == 0) {
obstacleGrid[0][j] += obstacleGrid[0][j - 1];
} else {
obstacleGrid[0][j] = 0;
}
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}
return obstacleGrid[m - 1][n - 1];
}
};
Решение на Golang
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
m, n := len(obstacleGrid), len(obstacleGrid[0])
if obstacleGrid[0][0] == 1 {
return 0
}
obstacleGrid[0][0] = 1
for i := 1; i < m; i++ {
if obstacleGrid[i][0] == 0 {
obstacleGrid[i][0] += obstacleGrid[i - 1][0]
} else {
obstacleGrid[i][0] = 0
}
}
for j := 1; j < n; j++ {
if obstacleGrid[0][j] == 0 {
obstacleGrid[0][j] += obstacleGrid[0][j - 1]
} else {
obstacleGrid[0][j] = 0
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if obstacleGrid[i][j] == 0 {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
} else {
obstacleGrid[i][j] = 0
}
}
}
return obstacleGrid[m - 1][n - 1]
}
Решение для Javascript
var uniquePathsWithObstacles = function(obstacleGrid) {
let m = obstacleGrid.length;
let n = obstacleGrid[0].length;
if(obstacleGrid[0][0] == 1) {
return 0;
}
obstacleGrid[0][0] = 1;
for(let i = 1; i < m; i++) {
if(obstacleGrid[i][0] == 0) {
obstacleGrid[i][0] += obstacleGrid[i - 1][0];
} else {
obstacleGrid[i][0] = 0;
}
}
for(let j = 1; j < n; j++) {
if(obstacleGrid[0][j] == 0) {
obstacleGrid[0][j] += obstacleGrid[0][j - 1];
} else {
obstacleGrid[0][j] = 0;
}
}
for(let i = 1; i < m; i++) {
for(let j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}
return obstacleGrid[m - 1][n - 1];
};
Давайте проверим наш алгоритм для примера 1.
Input: obstacleGrid = [
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
]
Step 1: m = obstacleGrid.size()
= 3
n = obstacleGrid[0].size()
= 3
Step 2: if obstacleGrid[0][0] == 1
0 == 1
false
Step 3: obstacleGrid[0][0] = 1
obstacleGrid = [
[1, 0, 0],
[0, 1, 0],
[0, 0, 0]
]
Step 4: loop for i = 1; i < m;
1 < 3
true
if obstacleGrid[i][0] == 0
obstacleGrid[1][0] == 0
true
obstacleGrid[i][0] += obstacleGrid[i - 1][0]
= obstacleGrid[i][0] + obstacleGrid[i - 1][0]
= obstacleGrid[1][0] + obstacleGrid[0][0]
= 0 + 1
= 1
i++
i = 2
for i < m
2 < 3
true
if obstacleGrid[i][0] == 0
obstacleGrid[2][0] == 0
true
obstacleGrid[i][0] += obstacleGrid[i - 1][0]
= obstacleGrid[i][0] + obstacleGrid[i - 1][0]
= obstacleGrid[2][0] + obstacleGrid[1][0]
= 0 + 1
= 1
i++
i = 3
for i < m
3 < 3
false
obstacleGrid = [
[1, 0, 0],
[1, 1, 0],
[1, 0, 0]
]
Step 5: loop for j = 1; j < n;
1 < 3
true
if obstacleGrid[0][j] == 0
obstacleGrid[0][1] == 0
true
obstacleGrid[0][j] += obstacleGrid[0][j - 1]
= obstacleGrid[0][j] + obstacleGrid[0][j - 1]
= obstacleGrid[0][1] + obstacleGrid[0][0]
= 0 + 1
= 1
j++
j = 2
for j < n
2 < 3
true
if obstacleGrid[0][j] == 0
obstacleGrid[0][2] == 0
true
obstacleGrid[0][j] += obstacleGrid[0][j - 1]
= obstacleGrid[0][j] + obstacleGrid[0][j - 1]
= obstacleGrid[0][2] + obstacleGrid[0][1]
= 0 + 1
= 1
j++
j = 3
for j < n
3 < 3
false
obstacleGrid = [
[1, 1, 1],
[1, 1, 0],
[1, 0, 0]
]
Step 6: loop for i = 1; i < m; i++
loop for j = 1; j < n; j++
if obstacleGrid[i][j] == 0
obstacleGrid[1][1] == 0
1 == 0
false
else
obstacleGrid[i][j] = 0
obstacleGrid[1][1] = 0
obstacleGrid = [
[1, 1, 1],
[1, 0, 0],
[1, 0, 0]
]
j++
j = 2
for j < n
2 < 3
true
if obstacleGrid[i][j] == 0
obstacleGrid[1][2] == 0
true
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
= obstacleGrid[1 - 1][2] + obstacleGrid[1][2 - 1]
= obstacleGrid[0][2] + obstacleGrid[1][1]
= 1 + 0
= 1
obstacleGrid = [
[1, 1, 1],
[1, 0, 1],
[1, 0, 0]
]
j++
j = 3
for j < n
3 < 3
false
i++
i = 2
Step 7: loop for i < m
2 < 3
true
loop for j = 1; j < n; j++
if obstacleGrid[i][j] == 0
obstacleGrid[2][1] == 0
true
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
= obstacleGrid[2 - 1][1] + obstacleGrid[2][1 - 1]
= obstacleGrid[1][1] + obstacleGrid[2][0]
= 0 + 1
= 1
obstacleGrid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 0]
]
j++
j = 2
for j < n
2 < 3
true
if obstacleGrid[i][j] == 0
obstacleGrid[2][2] == 0
true
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
= obstacleGrid[2 - 1][2] + obstacleGrid[2][2 - 1]
= obstacleGrid[1][2] + obstacleGrid[2][1]
= 1 + 1
= 2
obstacleGrid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 2]
]
j++
j = 3
for j < n
3 < 3
false
i++
i = 3
Step 8: loop for i < m
3 < 3
false
Step 9: return obstacleGrid[m - 1][n - 1]
obstacleGrid[3 - 1][3 - 1]
obstacleGrid[2][2]
2
We return the answer as 2.