63. Unique Paths II
Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.
Препятствия и свободные пространства отмечены в матрице как 1 и 0 соответственно. Путь, который проходит робот, не может включать клетки, которые являются препятствиями.
return количество возможных уникальных путей, по которым робот может добраться до нижнего правого угла.
Тестовые 示例ы сгенерированы таким образом, что ответ будет не более 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++ 解法
自动草稿，提交前请检查#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 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях.
😎
Vacancies for this task
活跃职位 with overlapping task tags are 已显示.