Sortie d'un labyrinthe

Récursivité et retour sur trace · niveau 3 (difficile)

Énoncé

Un labyrinthe est une matrice de booléens (true = mur). Écrire accessible laby qui teste si l'on peut aller du coin (0,0) au coin (n-1,m-1) par déplacements orthogonaux.

Corrigé

let accessible laby =
  let n = Array.length laby and m = Array.length laby.(0) in
  let vu = Array.make_matrix n m false in
  let rec explore i j =
    if i < 0 || i >= n || j < 0 || j >= m then false
    else if laby.(i).(j) || vu.(i).(j) then false
    else if i = n - 1 && j = m - 1 then true
    else begin
      vu.(i).(j) <- true;
      explore (i + 1) j || explore (i - 1) j
      || explore i (j + 1) || explore i (j - 1)
    end
  in
  explore 0 0

On explore en profondeur, en marquant les cases visitées (vu) pour ne pas tourner en rond : c'est ici l'état mutable du backtracking. On renvoie true dès qu'on atteint la sortie (le || élague les autres directions). Inutile de « démarquer » : pour la simple accessibilité, une case déjà explorée sans succès le restera. (Marquer évite une récursion infinie entre deux cases voisines.)

Énoncé

Corrigé

Exercices semblables