63. Unique Paths II
Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.
Препятствия и свободные пространства отмечены в матрице как 1 и 0 соответственно. Путь, который проходит робот, не может включать клетки, которые являются препятствиями.
Верните количество возможных уникальных путей, по которым робот может добраться до нижнего правого угла.
Тестовые примеры сгенерированы таким образом, что ответ будет не более 2 * 10^9.
Пример:
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
C# решение
сопоставлено/оригиналpublic class Solution {
public int UniquePathsWithObstacles(int[][] obstacleGrid) {
int R = obstacleGrid.Length;
int C = obstacleGrid[0].Length;
if (obstacleGrid[0][0] == 1) {
return 0;
}
obstacleGrid[0][0] = 1;
for (int i = 1; i < R; i++) {
obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0;
}
for (int i = 1; i < C; i++) {
obstacleGrid[0][i] = (obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1) ? 1 : 0;
}
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++) {
if (obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}
return obstacleGrid[R - 1][C - 1];
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int UniquePathsWithObstacles(int[][] obstacleGrid) {
int R = obstacleGrid.size();
int C = obstacleGrid[0].size();
if (obstacleGrid[0][0] == 1) {
return 0;
}
obstacleGrid[0][0] = 1;
for (int i = 1; i < R; i++) {
obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0;
}
for (int i = 1; i < C; i++) {
obstacleGrid[0][i] = (obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1) ? 1 : 0;
}
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++) {
if (obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}
return obstacleGrid[R - 1][C - 1];
}
}Java решение
сопоставлено/оригиналclass Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int R = obstacleGrid.length;
int C = obstacleGrid[0].length;
if (obstacleGrid[0][0] == 1) {
return 0;
}
obstacleGrid[0][0] = 1;
for (int i = 1; i < R; i++) {
obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0;
}
for (int i = 1; i < C; i++) {
obstacleGrid[0][i] = (obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1) ? 1 : 0;
}
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++) {
if (obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}
return obstacleGrid[R - 1][C - 1];
}
}JavaScript решение
сопоставлено/оригиналvar uniquePathsWithObstacles = function (obstacleGrid) {
let R = obstacleGrid.length;
let C = obstacleGrid[0].length;
if (obstacleGrid[0][0] == 1) {
return 0;
}
obstacleGrid[0][0] = 1;
for (let i = 1; i < R; i++) {
obstacleGrid[i][0] = obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1 ? 1 : 0;
}
for (let i = 1; i < C; i++) {
obstacleGrid[0][i] = obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1 ? 1 : 0;
}
for (let i = 1; i < R; i++) {
for (let j = 1; j < C; j++) {
if (obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}
return obstacleGrid[R - 1][C - 1];
};Python решение
сопоставлено/оригиналclass Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
if obstacleGrid[0][0] == 1:
return 0
obstacleGrid[0][0] = 1
for i in range(1, m):
obstacleGrid[i][0] = int(
obstacleGrid[i][0] == 0 and obstacleGrid[i - 1][0] == 1
)
for j in range(1, n):
obstacleGrid[0][j] = int(
obstacleGrid[0][j] == 0 and obstacleGrid[0][j - 1] == 1
)
for i in range(1, m):
for j in range(1, n):
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]Go решение
сопоставлено/оригиналfunc uniquePathsWithObstacles(obstacleGrid [][]int) int {
R := len(obstacleGrid)
C := len(obstacleGrid[0])
if obstacleGrid[0][0] == 1 {
return 0
}
obstacleGrid[0][0] = 1
for i := 1; i < R; i++ {
if obstacleGrid[i][0] == 0 && obstacleGrid[i-1][0] == 1 {
obstacleGrid[i][0] = 1
} else {
obstacleGrid[i][0] = 0
}
}
for i := 1; i < C; i++ {
if obstacleGrid[0][i] == 0 && obstacleGrid[0][i-1] == 1 {
obstacleGrid[0][i] = 1
} else {
obstacleGrid[0][i] = 0
}
}
for i := 1; i < R; i++ {
for j := 1; j < C; j++ {
if obstacleGrid[i][j] == 0 {
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
} else {
obstacleGrid[i][j] = 0
}
}
}
return obstacleGrid[R-1][C-1]
}Algorithm
1️⃣
Если первая ячейка, то есть obstacleGrid[0,0], содержит 1, это означает, что в первой ячейке есть препятствие. Следовательно, робот не сможет сделать ни одного хода, и мы должны вернуть количество возможных путей как 0. Если же obstacleGrid[0,0] изначально равно 0, мы устанавливаем его равным 1 и продолжаем.
2️⃣
Итерация по первой строке. Если ячейка изначально содержит 1, это означает, что текущая ячейка имеет препятствие и не должна учитываться в каком-либо пути. Следовательно, значение этой ячейки устанавливается равным 0. В противном случае, устанавливаем его равным значению предыдущей ячейки, то есть obstacleGrid[i,j] = obstacleGrid[i,j-1]. Повторяем аналогичные действия для первого столбца.
3️⃣
Далее, итерация по массиву начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.