Énoncé

Tous les jours, Charlotte part de chez elle pour se rendre sur son lieu de travail, elle utilise une voiture électrique et dispose tous les matins de la même charge initiale.
Trouvant le trajet monotone, elle décide chaque matin d'emprunter une route différente.
Charlotte dispose d'une carte, et connait la charge de sa voiture en électricité.
Elle ne peut donc ni se perdre, ni tomber en panne avant d'arriver à destination.

L'objectif de ce problème est de déterminer, connaissant la carte des routes et l'autonomie du véhicule, pendant combien de jours Charlotte pourra emprunter un nouveau trajet de chez elle à son lieu de travail.
La carte routière est donnée sous la forme d'une matrice d'adjacence M de taille N*N (avec N <= 300) :

N représente le nombre de croisements.
Pour tout couple de croisements (i, j) tel que i ∈ [1, N] et j ∈ [1, N] :
- M(i, i) = 0.
- M(i, j) = 0 s'il n'existe pas de route reliant directement i à j.
- M(i, j) = 1 s'il existe une route reliant directement i à j.

On supposera que la voiture de Charlotte consomme une unité électrique pour se rendre d'une intersection à l'autre.
On supposera aussi que Charlotte habite au croisement numéro 1 sur la carte et travaille au croisement numéro N.
Enfin, on supposera que si le trajet de Charlotte passe par son lieu de travail, elle s'arrête de conduire.

Entrée

La première ligne de l'entrée représente le nombre d'unités électriques dont dispose initialement la voiture de Charlotte chaque matin.
La seconde donne le nombre de croisements (N).
Enfin, les N suivantes donnent la matrice d'adjacence représentant la carte routière.

Sortie

La sortie sera constituée d'une seule ligne, donnant le nombre de jours pendant lesquels Charlotte pourra emprunter un nouveau trajet.

Exemples

Entrée	Trajets possibles	Sortie
4 9 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0	1-2-3-6-9 1-2-5-6-9 1-2-5-8-9 1-4-5-6-9 1-4-5-8-9 1-4-7-8-9	6
5 4 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0	1-3-4 1-2-3-4 1-2-1-3-4 1-3-1-3-4 1-3-2-3-4 1-2-1-2-3-4 1-2-3-1-3-4 1-2-3-2-3-4 1-3-1-2-3-4 1-3-2-1-3-4	10

Squelette CamlLight

(* Cette fonction parse une ligne correspondant a un entier.
   Il n'est pas necessaire de comprendre cette fonction pour utiliser le programme. *)

let parseInt () =
    int_of_string (input_line stdin)
;;

(* Cette fonction parse la matrice d'adjacence representant le reseau routier.
   Il n'est pas necessaire de comprendre cette fonction pour utiliser le programme. *)

let parseMap n =
    let m = make_matrix n n (-1) in
    for i = 0 to n - 1 do
        let textLine = input_line stdin in
        for j = 0 to n - 1 do
            m.(i).(j) <- int_of_string (sub_string textLine (j * 2) 1)
        done
    done;
    m
;;

(* Cette fonction renvoie l'entier etant le resultat de votre programme.
   N'oubliez pas de l'appeler a la fin. *)
    
let printSolution solution =
    printf__printf "%d" solution;
    print_newline()
;;

(****************** VOTRE PROGRAMME ******************)

(* Recuperation des informations *)
let capacity = parseInt ();;
let n = parseInt ();;
let m = parseMap n;;

(* Votre programme ici *)

(* N'oubliez pas de terminer votre programme par un appel a la fonction printSolution *)

Squelette OCaml

(* Cette fonction parse une ligne correspondant a un entier.
   Il n'est pas necessaire de comprendre cette fonction pour utiliser le programme. *)

let parseInt () =
    int_of_string (input_line stdin)
;;

(* Cette fonction parse la matrice d'adjacence representant le reseau routier.
   Il n'est pas necessaire de comprendre cette fonction pour utiliser le programme. *)

let parseMap n =
    let m = Array.make_matrix n n (-1) in
    for i = 0 to n - 1 do
        let textLine = input_line stdin in
        for j = 0 to n - 1 do
            m.(i).(j) <- int_of_string (String.sub textLine (j * 2) 1)
        done
    done;
    m
;;

(* Cette fonction renvoie l'entier etant le resultat de votre programme.
   N'oubliez pas de l'appeler a la fin. *)
    
let printSolution solution =
    print_endline (string_of_int solution)
;;
    
(****************** VOTRE PROGRAMME ******************)

(* Recuperation des informations *)
let capacity = parseInt ();;
let n = parseInt ();;
let m = parseMap n;;

(* Votre programme ici *)

(* N'oubliez pas de terminer votre programme par un appel a la fonction printSolution *)