Cet article présente une solution au problème LeetCode 63, qui consiste à compter le nombre de chemins uniques pour attteindre le coin inférieur droit d’une grille en présence d’obstacles. Le robot se déplace uniquement vers la droite ou vers le bas. Les obstacles sont représentés par la valeur 1 dans la grille, tandis que les cases vides sont marquées 0.

Exemple :

Entrée :

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

Sortie : 2

Il y a deux chemins possibles (contourner l’obstacle central).

Stratégie de résolution :

L’approche principale s’inspire du problème classique des chemins uniques (Unique Paths). La différence majeure est la gestion des obstacles : si une case est un obstacle, le nombre de chemins pour l’atteindre est nul. On peut résoudre ce problème par :

• Programmation dynamique itérative : on remplit une matrice dp où dp[i][j] représente le nombre de chemins pour atteindre la case (i-1, j-1). La première ligne et la première colonne sont traitées séparément : si l’obstacle est au début, le nombre total devient 0.
• Récursion avec mémoïsation : on utilise une matrice pour stocker les résultats intermédiaires, évitant ainsi les recacluls. Si une case contient un obstacle, on retourne 0 ; sinon, on additionne les résultats des déplacements depuis le haut et la gauche.

Points d'attention :

• La case de départ peut elle-même être un obstacle ; dans ce cas, le nombre total de chemins est 0.
• Pour éviter les débordements d’entiers (surtout en C++ avec des grilles jusqu’à 100×100), il est recommandé d’utiliser le type long au lieu d’int pour les accumulateurs.

Implémentations :

Version C++ (programmation dynamique) :

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int rows = obstacleGrid.size();
        int cols = obstacleGrid[0].size();
        vector<vector<long>> dp(rows + 1, vector<long>(cols + 1, 0));
        for (int r = 1; r <= rows; ++r) {
            for (int c = 1; c <= cols; ++c) {
                if (obstacleGrid[r-1][c-1] == 1) {
                    dp[r][c] = 0;
                } else if (r == 1 && c == 1) {
                    dp[r][c] = 1;
                } else {
                    dp[r][c] = dp[r-1][c] + dp[r][c-1];
                }
            }
        }
        return (int)dp[rows][cols];
    }
};

Version Java (récursion avec mémoïsation) :

class Solution {
    private int[][] memo;

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        memo = new int[m+1][n+1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return computePaths(m, n, obstacleGrid);
    }

    private int computePaths(int row, int col, int[][] grid) {
        if (row <= 0 || col <= 0) return 0;
        if (row == 1 && col == 1) return 1 - grid[0][0];
        if (memo[row][col] != -1) return memo[row][col];

        if (grid[row-1][col-1] == 1) {
            memo[row][col] = 0;
        } else {
            memo[row][col] = computePaths(row-1, col, grid) + computePaths(row, col-1, grid);
        }
        return memo[row][col];
    }
}

Ces deux apporches renvoient le nombre total de chemins en évitant les obstacles, avec une complexité temporelle O(m×n) et spatiale O(m×n).