Labyrinthe

On considère une grille carrée de taille n×n (par exemple 4×4) qui représente un labyrinthe.

• La case de départ est en haut à gauche (case d'indice $(\mathrm{0,0})$).
• L'objectif est d'atteindre la sortie en bas à droite (case d'indice $(n-1,n-1)$).
• Il est possible de se déplacer d'une seule case dans quatre directions : droite, gauche, haut et bas.
• Dans la grille, certaines cases sont libres (1) et d'autres sont des murs (0) sur lesquels on ne peut pas aller.
• En OCaml, on représente le labyrinthe par un type int array array.

Le but est d'écrire une fonction qui renvoie tous les chemins possibles pour franchir le labyrinthe.

1. 1

   Indice

   Vérifier les limites de la matrice et l'état de la cellule.
   Écrire une fonction is_valid_cell : int array array -> int * int -> bool qui renvoie true si les coordonnées (x, y) sont dans le labyrinthe et correspondent à une cellule libre.
2. 2

   Indice

   Comparer les coordonnées des cases pour restreindre les déplacements dx et dy.
   Écrire une fonction is_legal_move : (int * int) -> (int * int) -> bool qui renvoie true si le déplacement entre deux cellules adjacentes est légal.
3. 3

   Indice

   Parcourir la séquence de positions pour valider les extrémités et la continuité.
   Écrire une fonction validate_path : int array array -> (int * int) list -> bool qui renvoie true si un chemin est valide, c'est-à-dire qu'il commence en (0, 0), se termine en (n-1, n-1) et ne contient que des cellules libres reliées par des déplacements légaux.
4. 4

   Indice

   Explorer récursivement les voisins inférieurs et droits pour collecter les chemins complets.
   Écrire une fonction solve_maze : int array array -> (int * int) list list qui renvoie la liste de tous les chemins possibles pour aller de la case (0, 0) à la case (n-1, n-1) en respectant les règles de validité et de déplacement.

NB : vous pouvez tester votre code sur le labyrinthe suivant :

  let m2 = [|
  [|1; 1; 1; 1; 1; 1; 1; 0; 0; 1; 1; 1; 1; 1; 1; 0|];
  [|0; 0; 0; 0; 0; 0; 1; 0; 0; 1; 0; 0; 0; 0; 1; 0|];
  [|0; 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1; 0; 1; 0|];
  [|0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; 0; 1; 0; 1; 0|];
  [|0; 0; 0; 0; 1; 1; 0; 1; 1; 1; 1; 1; 1; 0; 1; 0|];
  [|0; 0; 0; 0; 1; 0; 0; 1; 0; 0; 0; 0; 0; 0; 1; 0|];
  [|0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 0|];
  [|0; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; 0; 1; 0; 0|];
  [|0; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; 0; 1; 1; 1|];
  [|0; 0; 0; 0; 0; 0; 1; 1; 1; 0; 0; 0; 0; 0; 0; 1|];
  [|0; 0; 0; 0; 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1|];
  [|0; 0; 0; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; 0; 0|];
  [|0; 0; 0; 0; 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 0|];
  [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 0|];
  [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 1|];
  [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1|]
|];;