Énoncé

On se donne un champ carré, que l'on découpe pour simplifier en une matrice de N par N cases. Ce champ est magique et quiconque s'y déplace sans respecter les règles est condamné à passer le restant de ses jours à calculer des primitives.
Le but de cet exercice est de se déplacer dans ce champ en ramassant le moins de cailloux possible. Les cases de la matrice représentent le nombre de cailloux à cet endroit du champ. On part du coin supérieur gauche du champ et on cherche à se rendre dans le coin inférieur droit. Les contraintes sont les suivantes :

on ne se déplace que vers le bas ou vers la droite, sans pouvoir remonter on revenir vers la gauche
quand on passe sur une case de la matrice, on ramasse nécessairement tous les cailloux qui s'y trouvent

Entrée

L'entrée du programme est la suivante :

la taille du champ (N), qui sera toujours limitée à 300 maximum
les valeurs de chaque case de la matrice, ligne par ligne, avec un retour à la ligne à la fin. Le champ étant magique, le nombre de cailloux sur une case peut-être négatif. On suppose d'ailleurs avoir initialement une réserve infinie de cailloux sur soi.

Sortie

La sortie sera le nombre de cailloux minimum que l'on doit ramasser (possiblement négatif) pour atteindre la case inférieure droite.

Exemples

Entrée	Sortie
3 1 4 2 2 5 3 3 6 4	14

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. *)

(* fonction pour separer les elements en entree 
Il n'est pas necessaire de comprendre cette fonction pour utiliser le programme !*)
let split_spaces chaine =
    let res = ref [] in
    let temp = ref "" in
    for i = 0 to string_length chaine - 1 do
        if chaine.[i]=` `
        then 
        begin
            res := !res @ [!temp];
            temp := "";
        end
        else
            temp := !temp ^ (sub_string chaine i 1);
    done;
    res := !res @ [!temp];
    let res_int = map int_of_string !res in
    let tab = vect_of_list res_int in
    tab;;

(* On lit la dimension n de la matrice *)
let n = int_of_string (input_line stdin);;

(* On lit les listes d'entiers, d'abord pour les lignes *)
let matrice = init_vect n (fun _ -> split_spaces (input_line stdin));;

let affiche_solution longueur =
   print_int longueur;
   print_newline();;

(* 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. *)

(* fonction pour separer les elements en entree 
Il n'est pas necessaire de comprendre cette fonction pour utiliser le programme !*)
let split_spaces chaine =
    let res = ref [] in
    let temp = ref "" in
    for i = 0 to String.length chaine - 1 do
        if chaine.[i]=' '
        then 
        begin
            res := !res @ [!temp];
            temp := "";
        end
        else
            temp := !temp ^ (String.sub chaine i 1);
    done;
    res := !res @ [!temp];
    let res_int = List.map int_of_string !res in
    let tab = Array.of_list res_int in
    tab;;

(* On lit la dimension n de la matrice *)
let n = int_of_string (input_line stdin)

(* On lit les listes d'entiers, d'abord pour les lignes *)
let matrice = Array.init n (fun _ -> split_spaces (input_line stdin))

let affiche_solution longueur =
   print_int longueur;
   print_newline();;

(* 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 *)