Le robot et les cases interdites — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 5)

Le robot et les cases interdites

Chemins de valeur optimale · niveau 2

Énoncé

Le petit robot du chapitre (déplacements N, E, NE) ne peut pas se poser sur certaines cases : un tableau booléen $X$ indique les obstacles.

Modifier la récurrence en utilisant la valeur $- \infty$ .
Comment savoir s'il existe au moins un chemin de $(0, 0)$ à $(L - 1, C - 1)$ ?
Programmer, et tester sur la grille $G = 951162273384$ (ligne $0$ en bas) avec deux jeux d'obstacles : les cases $(1, 1)$ , $(1, 2)$ , $(2, 0)$ , puis les cases $(0, 1)$ , $(1, 0)$ , $(1, 1)$ .

Corrigé

Base. $m (0, 0) = g (0, 0)$ si $(0, 0)$ n'est pas interdite, $- \infty$ sinon.

Hérédité. Pour $(l, c) \neq = (0, 0)$ : $m (l, c) = - \infty$ si $(l, c)$ est interdite ; sinon $m (l, c) = max {m (l - 1, c), m (l, c - 1), m (l - 1, c - 1)} + g (l, c)$ , où les cases hors grille sont omises et où le résultat reste $- \infty$ si tous les prédécesseurs valent $- \infty$ (case inaccessible).

Il existe un chemin si et seulement si $m (L - 1, C - 1) > - \infty$ .
On calcule ligne par ligne :


static int[][] calculerM(int[][] G, boolean[][] X) {
    int L = G.length, C = G[0].length;
    int[][] M = new int[L][C];
    for (int l = 0; l < L; l++)
        for (int c = 0; c < C; c++) {
            if (X[l][c]) { M[l][c] = MOINS_INFINI; continue; }    // case interdite
            if (l == 0 && c == 0) { M[0][0] = G[0][0]; continue; } // base
            int p = MOINS_INFINI;                                  // meilleur prédécesseur
            if (l > 0) p = Math.max(p, M[l - 1][c]);
            if (c > 0) p = Math.max(p, M[l][c - 1]);
            if (l > 0 && c > 0) p = Math.max(p, M[l - 1][c - 1]);
            M[l][c] = (p <= MOINS_INFINI / 2) ? MOINS_INFINI : p + G[l][c];
        }
    return M;
}

Avec le premier jeu d'obstacles, le robot contourne par la droite ; avec le second, la case $(0, 0)$ est enfermée :


ligne 2 : [-oo, 7, 9, 21]
ligne 1 : [6, -oo, -oo, 18]
ligne 0 : [1, 3, 6, 10]
valeur maximum 21
ligne 2 : [-oo, -oo, -oo, -oo]
ligne 1 : [-oo, -oo, -oo, -oo]
ligne 0 : [1, -oo, -oo, -oo]
aucun chemin

La complexité reste $Θ (L C)$ .