Ocaml

type laby = {p:int; q:int; v:bool array array};;
let monLaby = {p=0; q=0; v=Array.make_matrix 0 0 false};;
let start = (0,0);;

let deja_vu = Array.make_matrix monLaby.p monLaby.q 0;;
let parent = Array.make_matrix monLaby.p monLaby.q (0,0);;
let distance = Array.make_matrix monLaby.p monLaby.q (-1);;
let file = start::[];;

let rec operation = function (* remplace la boucle while, de paramètre file *)
|(i,j)::q -> (* l'existence de (i,j) implique que la liste est non vide *)
	let f = (* f est la valeur de file après le passage dans le if *)
		if i>0 && monLaby.v.(i).(j) && deja_vu.(i-1).(j)=0
		then	begin 
			distance.(i-1).(j) <- distance.(i-1).(j)+1;  
			deja_vu.(i-1).(j) <- 1; 
			parent.(i-1).(j) <- (i,j); 
			q@[(i-1,j)]  
			end
		else q
	in 
	deja_vu.(i).(j) <- 2;
	operation f; (* on boucle sur f *)
|_ -> ();; (* condition d'arrêt *)

operation file;; (* utilise la fonction récursive sur file *)

open Graphics;;
(*toutes les fonctions pour laby*)
type laby = { p: int; q: int; h: bool array array; v: bool array array};;
let constr_laby a b =  { p= a; q= b; h=Array.make_matrix a b false; v=Array.make_matrix a b false};;
type 'a set = Vois of int ref * 'a array;;
let creer_frontiere n x = let tab = Array.make n x in Vois(ref 0, tab);;
let ajout_elem (Vois(a, tab)) x = tab.(!a) <- x; a:=!a+1;;
let suppr_elem (Vois(a, tab)) x = for i=x to !a do tab.(i) <- tab.(i+1) done; a:=!a-1;;
let choix_elem (Vois(a, tab)) = Random.self_init(); let t = Random.int (!a) in tab.(t);;
let est_vide (Vois(a, tab)) = if !a==0 then true else false;;
let set_remove_all (Vois(a,tab)) f = let j=ref 0 in for i=0 to !a-1 do 	if f tab.(!j) then suppr_elem (Vois(a, tab)) !j else j:=!j+1 done;;  
let constr_I p q = Array.make_matrix p q false;;
let neighbours_outside laby en_I (i,j)= (if i>0 && not en_I.(i-1).(j) then [i-1,j] else [])@(if i<(laby.p-1) && not en_I.(i+1).(j) then [i+1, j] else [])@(if j>0 && not en_I.(i).(j-1) then [i, j-1] else [])@(if j<(laby.q-1) && not en_I.(i).(j+1) then [i, j+1] else []);;
let rand x = Random.self_init(); Random.int x;;
(*fin des fonctions*)


(*initialization du laby*)
let tailleLabyp=45;;
let tailleLabyq=30;;
let monLaby = constr_laby tailleLabyp tailleLabyq;;
let frontiere = creer_frontiere (monLaby.p*monLaby.q) (0,0);;
let ens_I = constr_I monLaby.p monLaby.q;;
(*fin d'initialization*)
(*choix au hasard d'une premiere case*)
let i=rand monLaby.p;;
let j=rand monLaby.q;;
ens_I.(i).(j)<-true;;
ajout_elem frontiere (i,j);; 
(*fin de choix de premiere case*)
(*boucle principale -> creation du laby*)
while not (est_vide frontiere) do
	let (x,y) = choix_elem frontiere in
	let listvois = neighbours_outside monLaby ens_I (x,y) in 
	let longeur= List.length listvois in
	let (a,b) = List.nth listvois (rand longeur) in 
	ens_I.(a).(b)<-true;
	if x=a then 
		(if b>y then monLaby.h.(a).(b)<-true else monLaby.h.(a).(b+1)<-true) 
	else (
		if x>a then monLaby.v.(a+1).(b)<-true else monLaby.v.(a).(b)<-true);
	ajout_elem frontiere (a, b);
	set_remove_all frontiere (fun e -> neighbours_outside monLaby ens_I e = [])	
done;;
(*fin de la boucle principale*)


(*choix de l'entree et du sortie*)
let stop = ref (0, 0);;
let start = ref (0, 0);;
let cote = rand 2 in if cote mod 2 = 0 then (start:=(0, rand monLaby.q); stop:=(monLaby.p-1, (rand monLaby.q))) else (start:=(0, rand monLaby.q); stop:=(monLaby.p-1, rand monLaby.q));;
(*fin de choix de l'entree et sortie*)

(*dessin du laby*)
let taille_carre=15 in 
let margin=10 in
open_graph "";
resize_window ((taille_carre*monLaby.p)+2*margin) ((taille_carre*monLaby.q)+2*margin);
draw_rect margin margin (taille_carre*monLaby.p) (taille_carre*monLaby.q);
(*dessine les lignes horizontaux*)
for i=1 to (monLaby.q-1) do
	moveto margin (margin+i*taille_carre);
	for j=0 to (monLaby.p-1) do
		if (monLaby.h.(j).(i)=false) then
			rlineto taille_carre 0 
		else rmoveto taille_carre 0; 
	done;
done;
(*dessine les lignes verticaux*)
for i=1 to (monLaby.p-1) do
	moveto (margin+i*taille_carre) margin;
	for j=0 to (monLaby.q-1) do
		if (monLaby.v.(i).(j)=false) then
			rlineto 0 taille_carre 
		else rmoveto 0 taille_carre; 
	done;
done;
set_color green;
(*dessine la case start*)
let e1 = fst !start in let e2 = snd !start in 
fill_rect (e1*taille_carre+margin+taille_carre/4) (e2*taille_carre+margin+taille_carre/4) (taille_carre/2) (taille_carre/2);
(*dessine la case stop*)
let s1 = fst !stop in let s2 = snd !stop in 
fill_rect (s1*taille_carre+margin+taille_carre/4) (s2*taille_carre+margin+taille_carre/4) (taille_carre/2) (taille_carre/2);;

(*solution de laby*)
LE MORCEAU QUE J'AI DEJA POSTE ET DONT JE VAIS M'OCCUPER A L'INSTANT 
(*fin de solution du laby*)
read_line();;
close_graph();;
(*fin du dessin du laby*)

type colorGraph = Blanc|Gris|Noir;; 
let color = Array.make_matrix monLaby.p monLaby.q Blanc;; 
let parent = Array.make_matrix monLaby.p monLaby.q (0,0);; 
let distance = Array.make_matrix monLaby.p monLaby.q (-1);; 
let debut = !start::[];; 

color.(fst !start).(snd !start)<- Gris;; (*case du debut est deja vu*) 
distance.(fst !start).(snd !start)<-0;; (*elle est a distance 0 du debut*) 
parent.(fst !start).(snd !start)<-(fst !start, snd !start);; (*et elle est son parent*) 


let rec traitement_case voisins q i j = match voisins with 
(a, b)::r ->  
   distance.(a).(b) <- distance.(i).(j)+1;   
   color.(a).(b) <- Gris;  
   parent.(a).(b) <- (i,j); 
   traitement_case r q i j;  
|_ -> ();;  

let rec solution = function  
|(i,j)::q ->  
 let f =  
  (let v= ((if (i>0 && monLaby.v.(i).(j) && (color.(i-1).(j)= Blanc)) then [i-1, j] else [])@(if (i<(monLaby.p-1) &&  monLaby.v.(i+1).(j) && (color.(i+1).(j)= Blanc)) then [i+1, j] else [])@(if ((j>0) && (monLaby.h.(i).(j)) && (color.(i).(j-1)= Blanc)) then [i, j-1] else [])@(if (j<(monLaby.q-1) && monLaby.h.(i).(j+1) && (color.(i).(j+1)= Blanc)) then [i, j+1] else [])) in 
  traitement_case v q i j; 
  q@v 
  ) 
 in  
 color.(i).(j) <- Noir; 
 solution f;  
|_ -> ();;  

solution debut;;