Slides en français (Sorbonne Université Camp 2021)
Débutants
Aujourd’hui, vous allez devoir apprendre à sortir de ce labyrinthe.
9 17
#################
..........#.....#
#########.#.###.#
#...........#...#
######.########.#
#......#.....#..#
#.######.#..#####
#........#......#
###############.#
Entrées-sorties
Jeux de tests
Sources à compléter
Vous pouvez les appeler comme suit :
ocaml laby.ml < laby1.txt
python3 laby.py < laby1.txt
Exercices
Toutes les fonctions demandées prennent en argument les dimensions m × n du labyrinthe ainsi que le labyrinthe laby. On vous garantit que l’entrée est toujours en (1, 0) et la sortie en (n - 1, m - 2).
Exercice 1
Écrire une fonction sortie_accessible qui renvoie Vrai s’il est possible d’accéder à la sortie, Faux sinon.
Exercice 2
Écrire une fonction chemin qui trace un chemin composé de x pour accéder à la sortie.
Par exemple, sur le fichier laby1.txt, votre code pourra renvoyer :
#################
xxxxxxxxxx#.....#
#########x#.###.#
#.....xxxx..#...#
######x########.#
#xxxxxx#xxxx.#..#
#x######x#xx#####
#xxxxxxxx#xxxxxx#
###############x#
Exercice 3
Écrire une fonction plus_court_chemin qui trace un plus court chemin composé de x pour accéder à la sortie.
Par exemple, sur le fichier laby3.txt, votre code pourra renvoyer :
#################
xxxxxxxxxx......#
#########x#####.#
#.......xx......#
#.######x########
#.......xxxxxxxx#
#.########.##.#x#
#.............#x#
###############x#
Exercice bonus 4
Vous êtes maintenant muni d’un marteau qui démolit n’importe quel mur avec un coût de 5 (on suppose que se déplacer d’une case a un coût de 1). Écrire une fonction plus_court_chemin_avec_marteau qui trace un plus court chemin composé de x pour accéder à la sortie.