Trouvez un chemin pour Brasegali

Il fait des bonds de plus de 30 mètres.

Brasegali est très dynamique. Il peut faire des bonds par dessus des immeubles entiers. Et justement... vous allez devoir l'aider à traverser une ville. Brasegali va partir du nord-ouest de la ville (coin supérieur gauche) et se rendre au sud-est (coin inférieur droit). Vous disposez d'un plan de la ville :

...@@.@
....@..
@....@.
...@.@@
@.....@
.@.@@..
@@.....

Cette ville exemple est petite : 7x7. Les emplacements vides sont signalés par des . et les immeubles par des @.

Brasegali va donc devoir sauter de case en case, éventuellement par dessus des immeubles. Mais il ne doit pas sortir de la ville ni se poser sur un toit : il ne peut donc occuper que des cases contenant un point .

Brasegali peut sauter dans une des 4 directions n (nord), s (sud), e (est) et o (ouest). De plus il peut sauter d'une seule case ou de 3 cases. Toutefois, s'il saute de 3 cases, cela lui coutera deux fois plus d'énergie que s'il saute d'une seule case (mais il ira plus loin...).

Vous devez donner la liste des sauts que Brasegali doit faire pour atteindre le coin sud-est en minimisant l'énergie qu'il dépense. Les saut peuvent être encodés avec une lettre n, s, e, o pour des saut de taille 1, et N, S, E, et O pour des sauts de taille 3.

Dans l'exemple précédent, une solution optimale serait :

eeSSeE

Les positions qu'emprunterait alors Brasegali sont représentées ci-dessous :

123@@.@
....@..
@....@.
..4@.@@
@.....@
.@.@@..
@@56..7

Il peut y avoir plusieurs solutions optimales (par exemple, eSeSeE fonctionne aussi). Vous devez en fournir une seule.

Si l'entrée était l'exemple précédent, il suffirait donc de répondre eeSSeE pour valider le défi.

Ce problème est tiré de c0d1ng UP 2017
Pour ce type de défi, vous devez être connecté (accès à une URL donnant l'instance du problème à résoudre)

Tags : cup17 graphe defiweb