1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Formateur Android et JAVA
    Inscrit en
    novembre 2017
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Formateur Android et JAVA
    Secteur : Enseignement

    Informations forums :
    Inscription : novembre 2017
    Messages : 1
    Points : 1
    Points
    1

    Par défaut 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 : 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

  2. #2
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 474
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 474
    Points : 3 905
    Points
    3 905

    Par défaut

    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
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

Discussions similaires

  1. Parcours dans l'ordre d'un tableau associatif
    Par bobinwood dans le forum JavaScript
    Réponses: 2
    Dernier message: 19/04/2016, 10h52
  2. XML/XSL parcours itératif et récursif
    Par greIn dans le forum XML/XSL et SOAP
    Réponses: 3
    Dernier message: 07/11/2012, 01h04
  3. Parcours de dossier récursif
    Par YoshioToutou dans le forum Débuter
    Réponses: 6
    Dernier message: 04/03/2012, 17h06
  4. Parcours base de données et création tableau d'images
    Par clem037 dans le forum PHP & MySQL
    Réponses: 15
    Dernier message: 09/06/2009, 00h42
  5. Tableau de chaînes de caractères
    Par mac1 dans le forum Langage
    Réponses: 3
    Dernier message: 15/01/2006, 14h18

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo