Discussion :

[conradson]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[anapurna]

salut

si j'ai bien tout compris tu doit gérer un aller et un retour
mais entre l'aller et le retour les pièges qui on fonctionné se transforme en mur ?

1°) Recenser toutes les cas possible à l'aller (Pas forcement les plus rapide)
si impossible result := -2 sinon result := 0;
2°) Pour chaque solution trouvé en 1 Faire l'inverse avec une map modifier (Piège déclenché selon la solution (verifier que la case n'a pas ete visité et que ce n'est pas un piege))
si -2 dans la premiere pas la peine de chercher la suite
si impossible result := -1 sinon result := 0 ;
a ce niveau tu peu optimiser en faisant une sorte de coupe alpha beta


le plus simple serais de garder la map original et de conserver les déplacement de chaque solution
de cette maniere pour chaque solution tu pourra savoir si tu as traversé la cellule ou pas et donc declenché ou pas le piège