Recherche de chemins

Messages postés
14
Date d'inscription
vendredi 15 janvier 2016
Statut
Membre
Dernière intervention
28 février 2016
- - Dernière réponse : edodo7
Messages postés
14
Date d'inscription
vendredi 15 janvier 2016
Statut
Membre
Dernière intervention
28 février 2016
- 28 févr. 2016 à 00:11
Bonjour, j'ai besoin de faire une méthode qui me dises si un chemin est toujours possible dans un plateau. Plus précisément mon plateau est un tableau de tableaux dont un l'élément à l'indice (i,j) est une objet de ma classe Case.
Un des attributs de Case est que sur les 4 cotés de la case il y a possibilité de placer des murs(en réalité ce ne sont que des valeurs booléennes de Case qui valent true si il y a un mur et false sinon). Mon but est donc une méthode qui puisse renvoyer true si depuis la première ligne du plateau, on peut atteindre la dernière en prenant en compte les murs de chaque case.
Merci.
Afficher la suite 

2 réponses

Messages postés
13431
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
20 juin 2019
280
Whismeril
Messages postés
13431
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
20 juin 2019
280 -
C'est du C#, mais dans le principe c'est un peu pareil.
> Whismeril
Messages postés
13431
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
20 juin 2019
-
Merçi pour ta réponse. Quelle est la complexité de l'algo? J'aurais besoin d'un algorithme qui demande moins de 5 secondes à être exécuté.
KX
Messages postés
15998
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 juin 2019
85 > edodo7 -
La complexité d'un algorithme ne permet pas de savoir combien de temps ils va mettre pour s'exécuter.

Un très bon algorithme sur une mauvaise machine peut-être plus long à s'exécuter qu'un mauvais algorithme sur une très bonne machine...
Whismeril
Messages postés
13431
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
20 juin 2019
280 -
tu peux tester le source associé si tu veux.
Il existe des versions gratuites de visual studio: Express et Community.

Pour la complexité, étant autodidacte je n'y ai même pas pensé à l'époque mais ça va assez vite, après je ne connais pas Java et ne sais pas si tout est transposable
Commenter la réponse de Whismeril
Messages postés
15998
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 juin 2019
85
0
Merci
Bonjour,

Un algorithme simple (à vérifier, je fait ça de tête)

Pour chaque case {
    Mettre la couleur de la case à blanc
}

Mettre la couleur de la case à jaune

Tant qu'il y des cases jaunes {
    Si la case d'arrivée est jaune {
        Retourner vrai
    }
    Pour chaque case jaune {
        Mettre la couleur à rouge
    }
    Pour chaque case rouge {
        Pour chaque case voisine de couleur blanche {
             Mettre la couleur de la case voisine à jaune
        }
    }
    Pour chaque case rouge {
        Mettre la couleur à noire
    }
}

Retourner faux

La complexité est proportionnelle au nombre de cases.
edodo7
Messages postés
14
Date d'inscription
vendredi 15 janvier 2016
Statut
Membre
Dernière intervention
28 février 2016
-
Merci pour ta réponse. J'avoue que je n'ai pas bien compris. Tout d'abord tu dit de mettre toutes les cases à blanc ensuite de mettre la couleur de la case à jaune. De quelle case parles tu? J'aimerais un peu plus de précisions si ce n'est pas trop demander.
KX
Messages postés
15998
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 juin 2019
85 -
Effectivement, j'en ai oublié un bout...

Il fallait lire : "Mettre la couleur de la case de départ à jaune"
edodo7
Messages postés
14
Date d'inscription
vendredi 15 janvier 2016
Statut
Membre
Dernière intervention
28 février 2016
> KX
Messages postés
15998
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 juin 2019
-
D'accord,je passe peut être pour un imbécile mais je dois avouer que le fonctionnement de l'algo reste flou pour moi. Je te serai reconnaissant si tu pouvais préciser le code afin que je sache quel est le but de chaque instruction.
Merci beaucoup.
KX
Messages postés
15998
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 juin 2019
85 > edodo7
Messages postés
14
Date d'inscription
vendredi 15 janvier 2016
Statut
Membre
Dernière intervention
28 février 2016
-
Comment tu peux parler de code alors qu'on ne sait pas comment il est fait vu que tu ne nous l'as pas montré ?

L'algo est un simple parcours en largeur. Si tu ne le comprends pas, prends toi une feuille de papier, des crayons de couleurs, dessine ta grille, et exécutes le étapes par étapes...
edodo7
Messages postés
14
Date d'inscription
vendredi 15 janvier 2016
Statut
Membre
Dernière intervention
28 février 2016
-
Voici comment j'ai implémenté le constructeur de mon plateau:
	public Quoridor ()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
tableau[i][j] = new Case();
}
}
joueur1 = new Player();
}


Voici le constructeur de ma classe Case:
	public Case()
{
value_case = true;//la case est vide
value_EdgeLeft = false;//il n'y a pas de mur à gauche de la case
value_EdgeRight = false;//il n'y a pas de mur à droite de la case
value_EdgeUp = false;//il n'y a pas de mur en haut de la case
value_EdgeDown = false; // il n'y a pas de mur en bas de la case
}
.
Le reste du code de la classe Case sont des getters et des setters.

Je vais suivre ton conseil concernant la compréhension de l'algo.
Commenter la réponse de KX