Afin d'éviter que les robots de Krikket ne trouvent les éléments de la clé verrouillant le Cocon de Temps Ralenti qui emprisonne les Krikketiens, Arthur est contraint de voyager dans les paysages montagneux hostiles de Krikket.
Il doit se rendre d'un point A à un point B et dispose d'une carte indiquant les altitudes (des nombres entre 0 et 255). Son objectif est de trouver un chemin de A vers B, avec le plus petit dénivelé positif.
À supposer que la carte soit celle-ci (cette carte est zoomée, chaque case fait normalement un seul pixel) :
Le niveau de gris de chaque cellule correspond à son altitude (nombre entre 0 et 255). Arthur peut se déplacer dans la direction nord, sud, est ou ouest, en partant de la cellule nord-ouest (en orange), et pour arriver dans la cellule sud-est (en vert).
Un chemin qui minimise le dénivelé positif est le suivant :
En suivant ce chemin, chaque cellule traversée a pour altitude : 148, 175,
122, 154, 154, 130, 154, 100, 148
Le dénivelé pour passer d'une cellule à l'autre est :
altitude : 148 175 122 154 154 130 154 100 148 dénivelé : +27
-53 +32 0 -24 +24 -54 +48
On ne tient compte que du dénivelé positif :
altitude : 148 175 122 154 154 130 154 100 148 dénivelé positif : +27
+32 0 +24 +48
Le total du dénivelé positif est donc : 131 (27 + 32 + 0 + 24 + 48).
On ne peut pas trouver de chemin qui mène du nord-ouest au sud-est avec un dénivelé positif strictement plus petit. La solution précédente est donc valide sur cette petite carte.
Pour encoder le chemin solution, on peut coder les déplacements d'Arthur (N,
S, E, O), depuis le départ au nord-ouest jusqu'à l'arrivée au sud-est, ce qui
donne dans le cas du chemin précédent : ESEESSSE.
Voici la carte réelle de la zone que doit traverser Arthur :
Donner la séquence de déplacements que doit effectuer Arthur pour joindre l'extrême nord-ouest à l'extrême sud-est en minimisant le dénivelé positif.
