Énoncé

Link est dans un donjon de glace. Il entre dans une salle, mais le sol est gelé ! Comment arrivera-t'il à traverser la pièce pour progresser dans le donjon?

Link peut se déplace dans les quatre directions. S'il marche sur de la glace, il glisse jusqu'à rencontrer un mur ou du sol. Si il s'arrête contre un mur alors qu'il est sur de la glace, il peut décider de glisser dans une autre direction. Les bords du donjon sont tous des murs et ne sont pas reinseignés en entrée.

Il y peut aussi y avoir des trous dans le sol. Si Link tombe dans un trou, c'est game over.

Entrée

L'entrée comporte sur une première ligne les dimensions de la salle: hauteur h puis largeur w. Puis il y a h lignes comportant chacune w symboles indicant la composition de la salle.

La pièce est composée de quatre éléments: Murs (W), Terre(E), Glace (I), Trou(H). L'entrée de la pièce est notée A et la sortie est notée B. A et B sont toujours en terre. Link commence sur la case A et doit donc terminer sur la case B.

Sortie

La sortie est le nombre minimum de cases que Link doit parcourir à partir de A pour arriver jusqu'à B.

Exemples

Entrée	Sortie
5 3 I A I I W I I B I I I I W I I	8
7 7 W B W W I I I I I I I H I I W I I I I I I I W I I I I W I I I I I I I W I E E E I W W I E A E I W	18

Squelette CamlLight

 (* Ce fichier contient tout ce qu il faut pour lire les donnees en entree les mettre dans des variables, et afficher votre resultat final en sortie. *)

let split_spaces chaine =
    let res = ref [] in
    for i = 0 to string_length chaine - 1 do
    if chaine.[i]<>` `
        then 
        begin
            res := !res @ [chaine.[i]];
        end
    done;
    !res;;

let string_index line = 
   let i = ref 0 in
   while (!i < (string_length line)) && (line.[!i] <> ` `) do
      i := !i + 1
   done;
   !i ;;

let line_to_tuple line =
   let spaceIndex = string_index line in
   let x = int_of_string (sub_string line 0 spaceIndex) in
   let y = int_of_string (sub_string line (spaceIndex + 1) ((string_length line) - spaceIndex - 1)) in
   (x, y);;

(* fonction pour afficher votre solution *)
let affiche_solution moves = 
   print_int moves;
   print_newline();;

(* On lit les dimensions h et w de la matrice *)
let h,w = line_to_tuple(input_line stdin);;

(* On cree la matrice qui represente la piece puis on la remplit *)
let piece = make_matrix h w `E` ;;

for i = 0 to h - 1 do
   let line = vect_of_list (split_spaces (input_line stdin)) in 
   for j = 0 to w - 1 do
      piece.(i).(j) <- line.(j)
   done;
done;;

(* Mettez apres ceci le corps de votre programme *)
(* N'oubliez pas de terminer par un appel a affiche_solution !*)

(* Debut de votre programme *)


(* Fin de votre programme *)

Squelette OCaml

(* Ce fichier contient tout ce qu'il faut pour lire les donnees en entree, les 
mettre dans des variables, et afficher votre resultat final en sortie. *)

let split_spaces chaine =
  let res = ref [] in
  for i = 0 to String.length chaine - 1 do
    if chaine.[i]<>' '
    then 
      begin
         res := !res @ [chaine.[i]];
      end
  done;
  !res;;

let line_to_tuple line =
   let spaceIndex = String.index line ' ' in
   let x = int_of_string (String.sub line 0 spaceIndex) in
   let y = int_of_string (String.sub line (spaceIndex + 1) ((String.length line) - spaceIndex - 1)) in
   (x, y);;

(* fonction pour afficher votre solution *)
let affiche_solution moves = 
   print_int moves;
   print_newline();;

(* On lit les dimensions h et w de la matrice *)
let h,w = line_to_tuple(input_line stdin);;

(* On cree la matrice qui represente la piece puis on la remplit *)
let piece = Array.make_matrix h w 'E';;

for i = 0 to h - 1 do
   let line = Array.of_list (split_spaces (input_line stdin)) in 
   for j = 0 to w - 1 do
      piece.(i).(j) <- line.(j)
   done;
done;;

(* Mettez apres ceci le corps de votre programme *)
(* N'oubliez pas de terminer par un appel a affiche_solution !*)

(* Debut de votre programme *)


(* Fin de votre programme *)