Seconde descente à skis

Slalom sous contrainte

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
Ce problème est tiré de c0d1ng UP 2019

Type de retour

une chaine de caractères

Entrée du problème

Lien vers les données d'entrée

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : optimisation simulation récursivité cup19 level5