La première descente à skis (voir l'autre problème) n'a pas suffit à James. Toujours prêt à relever de nouveaux défis, il décide cette fois d'ajouter une contrainte à sa descente : balayer la largeur de piste la plus grande.
C'est encore à vous qu'il incombe de lui préparer son trajet. À chaque étape, il
peut descendre |, se décaler vers la gauche g ou vers la droite d. L'objectif principal est
de maximiser le nombre de passages entre 2 arbres *.*, comme précédemment, mais
vous avez comme objectif secondaire de maximiser la largeur de piste utilisée.
Voici un exemple de piste :
.*.**.*........*.*...
...*.*.......*.*.*.*.
.*.**.*........*.*...
.*.*..*.*....*.*.....
.*.*..*.*........*.*.
..*.*........*.**.*..
..*.*...*.*.....*.*..
..*.*.......*.*..*.*.
....*.**.*.......*.*.
.*.*.*.*...*.*.......
.*.**.*.*.*..........
.*.*.*.*........*.*..
.....*.*..*.*....*.*.
......*.**.*.....*.*.
.*.**.*.*.*..........
..*.*.*.*....*.*.....
......*.*..*.*.*.*...
*.*..*.*.....*.*.....
*.*.....*.*...*.*....
*.*.......*.*..*.*...
Voici une première descente :
.*.**.*.../....*.*...
...*.*.../...*.*.*.*.
.*.**.*./......*.*...
.*.*..*|*....*.*.....
.*.*..*\*........*.*.
..*.*...\....*.**.*..
..*.*...*|*.....*.*..
..*.*..../..*.*..*.*.
....*.**|*.......*.*.
.*.*.*.*/..*.*.......
.*.**.*/*.*..........
.*.*.*|*........*.*..
.....*\*..*.*....*.*.
......*|**.*.....*.*.
.*.**.*|*.*..........
..*.*.*|*....*.*.....
......*/*..*.*.*.*...
*.*..*|*.....*.*.....
*.*...|.*.*...*.*....
*.*.......*.*..*.*...
^ ^ : largeur
Et en voici une seconde :
.*.**.*.../....*.*...
...*.*.../...*.*.*.*.
.*.**.*./......*.*...
.*.*..*|*....*.*.....
.*.*..*|*........*.*.
..*.*..|.....*.**.*..
..*.*../*.*.....*.*..
..*.*./.....*.*..*.*.
....*/**.*.......*.*.
.*.*\*.*...*.*.......
.*.**\*.*.*..........
.*.*.*|*........*.*..
.....*\*..*.*....*.*.
......*|**.*.....*.*.
.*.**.*|*.*..........
..*.*.*|*....*.*.....
......*/*..*.*.*.*...
*.*..*|*.....*.*.....
*.*...|.*.*...*.*....
*.*.......*.*..*.*...
^ ^ : largeur
Ces deux descentes sont optimales en ce qui concerne le nombre de paires d'arbres traversées. Il y en a 12 dans les deux cas, et on ne peut pas faire mieux.
En ce qui concerne la largeur de piste occupée, la seconde solution est par contre meilleure, puisque la descente occupe en largeur une bande de 7 cases (on ne peut pas faire mieux), contre seulement 5 (on ne peut pas faire moins) pour la première.
La solution à privilégier est donc la seconde, et il faudrait ici répondre :
ggg|||gggdd|d|||g||
Une même carte peut avoir plusieurs solutions. Par exemple, la solution suivante est aussi valide :
ggg|dd|g|gg|d|||ggg
