Parcours optimisé et récursif d'un tableau de chaîne
Bonjour,
j'essai de résoudre un algo proposé à la BattleDev RegionJob de novembre 2017, dont voici la version anglaise ici :
https://questionsacm.isograd.com/cod...adventurer.pdf
En résumé : j'ai une grille représentant un donjon : le personnage commence en haut à gauche de la grille, il doit trouver une épée en bas à droite de la grille. Une fois l'épée trouvée, il doit revenir à la sortie en haut à gauche de la grille.
Sur la grille, il peut y avoir :
- des cases traversables représentées par un '.'
- des cases murs non traversables représentées par un '#'
- des cases pièges représentées par un '!', qui peuvent être traversées une fois uniquement.
Par exemple :
Code:
1 2 3 4 5 6 7 8
|
String[] map = new String[]{
".#.!.",
".#.#!",
".!.!.",
".#.#.",
".!.#."
}; |
Le but de l'algorithme est :
- de retourner -2 s'il est impossible d'atteindre l'épée
- de retourner -1 s'il est possible d'atteindre l'épée mais pas de revenir à la sortie
- de retourner le nombre minimal de piège à traverser s'il est possible d'atteindre l'épée et de ressortir du donjon.
J'ai trouvé une solution qui marche sur des grilles de taille réduite, mais pour une grille à 20, le traitement et trop long et fait planter mon cas de test :
https://gist.github.com/bastienwcs/c...229ee68b524297
C'est en JAVA (j'ai appelé l'épée treasure au lieu de sword). C'est un algo récursif qui parcours toutes les solutions possibles et stocke le minimum de piège à chaque fois qu'il trouve un aller-retour possible (c'est la méthode found() qui est appelée.
Je suis obligé de copier les grilles à chaque appel car en Java la référence est gardée et ça modifierait le même tableau à chaque fois, je pense que c'est ce qui fait ramer le plus le process.
Y-a-t'il une solution plus optimisée qui ferait qu'un cas de grille en 20x20 ne planterait pas ?
Merci d'avance pour votre aide, désolé si je n'ai pas posé ma question dans la bonne section