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
