Informatique - Le jeu de Röckse

On dispose sur les cases d'une grille NxN des pénalités et des gains comptés comme des pénalités négatives. Le jeu de Röckse débute à la case (0, 0) et cherche un chemin vers la case (N-1, N-1) qui minimise les pénalités. À chaque étape du chemin, un nombre fini de déplacements est autorisé. Des cases bonus ajoutent, une fois atteintes, des sauts possibles pour la suite du chemin.
La partie I porte sur les fonctions de base sur les chemins et les sauts. Ensuite, la partie II propose de trouver un chemin optimal avec une recherche exhaustive. La partie III utilise les résultats de la partie II pour construire une méthode de recherche gloutonne. Enfin, la partie IV étudie une résolution du problème par programmation dynamique.