63. Unique Paths II

LeetCode medium original: C# #array #csharp #leetcode #matrix #medium #string #tree #two-pointers

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.

Препятствия и свободные пространства отмечены в матрице как 1 и 0 соответственно. Путь, который проходит робот, не может включать клетки, которые являются препятствиями.

return количество возможных уникальных путей, по которым робот может добраться до нижнего правого угла.

Тестовые Exempleы сгенерированы таким образом, что ответ будет не более 2 * 10^9.

Exemple:

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# solution

correspondant/original

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++ solution

brouillon automatique, à relire avant soumission

#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 solution

correspondant/original

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 solution

correspondant/original

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 solution

correspondant/original

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 solution

correspondant/original

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️⃣

Далее, итерация по tableauу начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.