Première descente à skis

Slalom entre les sapins

James a projeté de frimer lors d'une future descente à skis. Non seulement il veut semer tous ses poursuivants, mais il lui faut maintenant ajouter un peu de piment à l'exercice.

La descente est parsemée d'arbres. Afin de mettre hors course ses poursuivants, qui sont en motoneige, il va tenter de passer le plus de fois possible entre des paires d'arbres rapprochés.

C'est vous qui préparez la mission, vous avez une carte de la descente avec la position des arbres. Cette carte est discrétisée. Chaque case est soit occupée par un arbre *, soit «vide» ..

Voici un exemple de carte :

.......
..*.*..
..*.*..
.*.*...
.*.*...

La descente se fait de haut en bas. James occupe une des cases, et à chaque instant, il peut choisir de descendre tout droit (|), de dévier un peu sur la droite \ (sur la droite du plan, c'est-à-dire sur sa gauche), ou un peu sur la gauche /. Il ne doit bien sûr jamais occuper une position qui contient un arbre.

Voici deux exemples de descente :

...|...
..*|*..
..*/*..
.*|*...
.*.*...

ou bien

...|...
..*|*..
..*\*..
.*.*|..
.*.*...

Dans le premier cas, il passe à travers 4 paires d'arbres. Dans le second cas, il passe seulement à travers 2 paires d'arbres, ce qui est moins bien. Les deux parcours peuvent être décrits, si on connaît la position de départ par ||g| pour le premier et ||d| pour le second (notez comment on remplace / par g et \ par d pour décrire la descente)

Étant donné le plan de la descente, et sachant que James va partir exactement au centre, en haut, proposez lui un chemin optimal qui maximise le nombre de passages entre des paires d'arbres. Notez bien que seuls les passages entre des paires d'arbres très rapprochés (une seule case vide entre eux) sont recherchés (James a juste la place, mais les motoneiges ne passeront pas). Si la carte contient 5 lignes, vous n'avez que 4 indications à fournir (une direction correspond à une transition entre 2 lignes, il y en a donc une de moins que de lignes).

Voici un exemple de carte contenant 21 colonnes et 20 lignes :

.*.**.*........*.*...
...*.*.......*.*.*.*.
.*.**.*........*.*...
.*.*..*.*....*.*.....
.*.*..*.*........*.*.
..*.*........*.**.*..
..*.*...*.*.....*.*..
..*.*.......*.*..*.*.
....*.**.*.......*.*.
.*.*.*.*...*.*.......
.*.**.*.*.*..........
.*.*.*.*........*.*..
.....*.*..*.*....*.*.
......*.**.*.....*.*.
.*.**.*.*.*..........
..*.*.*.*....*.*.....
......*.*..*.*.*.*...
*.*..*.*.....*.*.....
*.*.....*.*...*.*....
*.*.......*.*..*.*...

En partant du centre, James a la possibilité de passer entre 12 paires d'arbres, en suivant le trajet suivant :

.*.**.*.../....*.*...
...*.*.../...*.*.*.*.
.*.**.*./......*.*...
.*.*..*|*....*.*.....
.*.*..*|*........*.*.
..*.*..|.....*.**.*..
..*.*../*.*.....*.*..
..*.*./.....*.*..*.*.
....*\**.*.......*.*.
.*.*.*\*...*.*.......
.*.**.*/*.*..........
.*.*.*|*........*.*..
.....*\*..*.*....*.*.
......*|**.*.....*.*.
.*.**.*|*.*..........
..*.*.*|*....*.*.....
......*\*..*.*.*.*...
*.*..*.*\....*.*.....
*.*.....*|*...*.*....
*.*.......*.*..*.*...

La solution peut alors être donnée sous cette forme :

ggg|||ggddg|d|||dd|

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