Recherche de chemin Roguelike

Votre tâche sera, étant donné un tableau bidimensionnel des éléments décrits ci-dessous, qui représente un donjon, de générer ou de renvoyer un nombre unique représentant la quantité de pièces d'or que le voyou peut collecter sans réveiller aucun monstre.

Les éléments du tableau sont les suivants:

1. Les espaces vides sont représentés par un .ou par un espace, votre appel;
2. La position de départ de Rogue est bien sûr représentée par @;
3. Une pièce d'or est représentée par $;
4. Les murs sont représentés par #;
5. Les monstres sont représentés par des personnages de la regexp suivante: [a-zA-Z*&].

Le tableau ne doit pas contenir de caractères non répertoriés ci-dessus, vous pouvez donc supposer que tout ce qui n'est pas un mur, un espace vide, le voyou ou une pièce d'or est un monstre.

Les règles de pathfinding sont les suivantes:

1. Le voleur ne peut traverser que des cellules vides ou des cellules contenant de l'or;
2. Il faut un tour pour se déplacer vers une cellule adjacente ou adjacente en diagonale;
3. Ramasser l'or est instantané;
4. Le voleur ne peut pas rester adjacent ou diagonalement adjacent à un monstre pendant plus d'un tour sans le réveiller, ce qui est interdit;
5. Le voleur peut entrer dans la zone de conscience d'un monstre un certain nombre de fois, le monstre ne se réveillera que si le voleur passe deux tours consécutifs près de lui.

Règles d'entrée et de sortie

Vous pouvez obtenir l'entrée dans n'importe quel format raisonnable, y compris un tableau à deux dimensions, un tableau plat, une chaîne ou quoi que ce soit d'autre. Si cela vous facilite la vie, vous pouvez également prendre les dimensions du tableau.

Il est garanti que le voyou ne sera pas près d'un monstre au début.

Un programme complet ou une fonction est très bien.

Notation

Il s'agit de code-golf , le score est le nombre d'octets de votre soumission, moins étant meilleur.

Cas de test

J'utilise des points pour les espaces vides ici à des fins de lisibilité, si vous le souhaitez, vous pouvez utiliser des espaces (voir ci-dessus). Notez également que c'est une pure coïncidence que le voyou est toujours dans le coin supérieur gauche, votre code devrait également gérer toute autre position valide.

1)
@..
.$.
...  -> 1

Juste un test de raison.

2)
@....
...g$
.....  -> 0

Encore une fois, un test de santé mentale.

3)
@....
...$g
.....  -> 1

Le voleur peut saisir l'or en se déplaçant de la gauche.

4)
@....g..
.......$
........
.....h..  -> 1

Le voleur peut zigzaguer entre les monstres, sans jamais rester plus d'un tour près de chacun.

5)
@....z..
.......$
.....b..  -> 0

Les tactiques du scénario de test précédent ne fonctionnent pas ici - les zones de sensibilité des monstres se chevauchent.

6)
@$#.
###$
....  -> 1

Test de santé mentale.

7)
@..#..
$.$g.$
...#..  -> 2

Idem.

8)
@#.d#$
$...##
e.....
..$...
##..$b
.#..g$  -> 3

De tout l'or ici, seulement trois peuvent être atteints en toute sécurité: l'or près de la position de départ peut être obtenu en descendant un puis en revenant à la position de départ. Pour s'échapper du coin supérieur gauche, le coquin doit se déplacer en diagonale en bas à droite deux fois. L'or au milieu ne pose aucun défi. L'or extérieur gardé par get bpeut être obtenu en se déplaçant en diagonale de l'endroit à droite de l'or du milieu, puis en arrière. Le reste ne peut pas être obtenu: l'or en haut à droite est bloqué par les murs, et l'or en bas à droite nécessite deux tours dans les zones de sensibilité des monstres.

Les cas de test suivants ont été généreusement donnés par mbomb007.

9)
  12345678
a @....g.D
b .......$
c ......#.
d .....h..  -> 1

Celui-ci est délicat. Un chemin est b4-b5-c6-b7-c8-b8(grab).

10)
  12345678
a @....g.D
b .......$
c .......#
d .....h..  -> 1

Un chemin est [bc]4-c5-b6-c7-b8(grab).

11)
  12345678
a @....g.D
b ......#$
c .......#
d .....h..  -> 1

Le mur supplémentaire ne change rien, [bc]4-c5-b6-c7-b8(grab)c'est toujours une solution.

les solutions précédentes (en partie) peuvent être trouvées dans le conteneur de pied de page dans le lien tio (celles-ci sont probablement plus lisibles)

JavaScript (Node.js) , 883 436 411 360 345 311 octets

g=>g.map((r,y)=>[...r].map((c,x)=>A+=c=="$"&&P(g,x,y)),A=0)|A
P=(g,x,y,m={},p={},I=i=9,M={})=>{if(/[.$]/.test(c=(g[y]||0)[x])){for(;i--;)if(/^[^.@$#]$/.test(C=(g[y+~-(i/3)]||0)[x+i%3-1])){if(m[C])return
M[C]=1}for(;I--;)if(!p[(X=x+~-(I/3))+","+(Y=y+I%3-1)]&&P(g,X,Y,M,{...p,[x+","+y]:1}))return 1}return c=="@"}

Essayez-le en ligne!

Explantion -

au lieu de passer du joueur à l'argent, je suis passé de l'affaire au @. Je pense que je devrais être plus rapide parce que je sais quand arrêter de chercher (atteindre le @), et lorsque vous cherchez de l'argent, vous devez toujours continuer à bouger jusqu'à ce que vous ayez couvert tous les endroits (et les moyens d'y accéder). donc l'algo est assez simple de cette façon - la fonction principale g.map((r,y)=>[...r].map((c,x)=>A+=c=="$"&&P(g,x,y)),A=0)|A: trouver de l'argent -> si vous l'avez trouvé -> commencer à chercher le joueur -> si vous l'avez trouvé -> l'incrément A permet maintenant d' if(/[.$]/.test(c=(g[y]||[])[x]))accéder au localisateur de chemin aka P juste vérifier si la cellule actuelle est "spéciale" -> si c'est le cas, nous voulons revenir si c'est un joueur. cas particuliers: @ # (monstre)

for(;i--;) if(/^[a-zA-Z*&]$/.test(C=(g[y+~-(i/3)]||0)[x+i%3-1])) -> if my neighbor is a monster {if(m[C])return false -> and it already was in the previous turn - this path is not value M[C]=1} -> if not just add it to the neighbors monsters for(;I--;) if(!p[(X=x+~-(I / 3))+","+(Y=y+I%3-1)]&&P(g,X,Y,M,{...p,[x+","+y]:1}))return true itérer à nouveau les voisins - si je n'y étais pas déjà (p est le chemin emprunté) continuer le chemin (appeler P)