Matrice, trajet
Apaachee
Messages postés
248
Date d'inscription
Statut
Membre
Dernière intervention
-
Apaachee Messages postés 248 Date d'inscription Statut Membre Dernière intervention -
Apaachee Messages postés 248 Date d'inscription Statut Membre Dernière intervention -
Bonjour, j'ai quelques soucis à élaborer une fonction en Java, je m'explique...
Je possède une matrice du type
0 0 0 0 1 0 0
0 0 0 0 1 1 0
0 0 0 0 0 1 0
0 0 0 0 1 1 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
0 0 1 1 0 1 0
0 1 1 0 0 0 0
Enfin voila, les '1' forment un "parcours" dans ma matrice, parcours qui peut 'monter', descendre, aller à gauche ou droite, et ma fonction doit me permettre de savoir si le parcours des 1 relie le bord du haut au bord du bas de ma matrice.
Ca a priori l'air assez simple, mais je bloque vraiment sur la façon de faire.
Je possède une matrice du type
0 0 0 0 1 0 0
0 0 0 0 1 1 0
0 0 0 0 0 1 0
0 0 0 0 1 1 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
0 0 1 1 0 1 0
0 1 1 0 0 0 0
Enfin voila, les '1' forment un "parcours" dans ma matrice, parcours qui peut 'monter', descendre, aller à gauche ou droite, et ma fonction doit me permettre de savoir si le parcours des 1 relie le bord du haut au bord du bas de ma matrice.
Ca a priori l'air assez simple, mais je bloque vraiment sur la façon de faire.
A voir également:
- Matrice, trajet
- Google trajet historique - Guide
- La poste est prête à prendre en charge votre envoi. dès qu'il nous sera confié, vous pourrez suivre son trajet ici. ✓ - Forum Mobile
- Michelin trajet - Télécharger - Transports & Cartes
- La poste est prête à prendre en charge votre envoi. dès qu'il nous sera confié, vous pourrez suivre son trajet ici ✓ - Forum Consommation & Internet
- Comment supprimer un trajet sur waze ✓ - Forum GPS
8 réponses
Bonjour
Cela peut paraitre "simple" oui mais l'algo est quand même assez "embêtant" quand même !
Je te conseil de regarder vers la récursivité.
Imaginons tu ai ce tableau
Tu pars du haut a gauche
tu as une variable "ligne" qui désigne le nombre de caractere sur chaque ligne
tu parcours ta première ligne et a chaque 1 que tu rencontre tu lance la fonction récursive ci-dessous
Et tu boucle en recursif toujours
Moi je l'avais fais en C et ça donnait un truc du genre :
Avec tout ca tu dois tester que tu n'est pas deja passé par cette case, pour éviter les boucles infinis
Cela peut paraitre "simple" oui mais l'algo est quand même assez "embêtant" quand même !
Je te conseil de regarder vers la récursivité.
Imaginons tu ai ce tableau
Tu pars du haut a gauche
tu as une variable "ligne" qui désigne le nombre de caractere sur chaque ligne
tu parcours ta première ligne et a chaque 1 que tu rencontre tu lance la fonction récursive ci-dessous
Et tu boucle en recursif toujours
Moi je l'avais fais en C et ça donnait un truc du genre :
int ta_fonction() { if (tab[x + 1][y] && tab[x + 1][y] == '1') { if (x+1 = la dernière ligne de ton tableau) SUCCESS ! else rappel ta fonction avec tes nouvelles coordonnées } else if (tab[x - 1][y] && tab[x - 1][y] == '1') { if (x-1 = la dernière ligne de ton tableau) SUCCESS ! else rappel ta fonction avec tes nouvelles coordonnées } else if (tab[x][y - 1] && tab[x][y - 1] == '1') { rappel ta fonction avec tes nouvelles coordonnées } else if (tab[x][y + 1] && tab[x][y + 1] == '1') { rappel ta fonction avec tes nouvelles coordonnées } return (0); }
Avec tout ca tu dois tester que tu n'est pas deja passé par cette case, pour éviter les boucles infinis
Hello !
J'ai eu affaire à un problème similaier l'année dernière. J'avais une image monochrome (noir et blanc => 0 pour noir et 1 pour blanc) et il fallait écrire une fonction Java pour extraire des zones de pixels noirs contigus.
Le prof nous avait montré une méthode non récursive basée sur une liste de points à parcourir. La liste contient des doublets (x, y) représentant les coordonnées des points mémorisés. Il faut aussi copier la matrice, car cette méthode exige qu'on la modifie.
Mettons que la liste s'appelle L, et la copie de la matrice M.
Je vais esayer d'être le plus clair possible :
- on parcourt la première ligne de M pour trouver un 1, que l'on ajoute à L. C'est le point de départ.
- boucle while :
- pour chaque 1 dans L, on le met à 0 dans M et on regarde les voisins directs (gauche, droite, haut, bas) ; quand le voisin est à 1, on l'ajoute à L.
- si on a un point sur la dernière ligne, succès !
- fin boucle while
- si la liste est vide, ça veut dire que tous les 1 contigus ont été traités. À ce moment-là, il faut reparcourir la première ligne pour en trouver un autre et recommencer.
- si on n'a rien trouvé, échec.
Je sais que c'est un peu dur de se convaincre que cette méthode fonctionne, mais elle est garantie par deux choses :
- tous les 1 de L seront forcément traités, donc tous les voisins et les voisins des voisins, etc. du point de départ seront traités ;
- le programme ne va pas boucler car les points traités sont mis à 0 dans M.
Je reste dispo pour les questions ;)
J'ai eu affaire à un problème similaier l'année dernière. J'avais une image monochrome (noir et blanc => 0 pour noir et 1 pour blanc) et il fallait écrire une fonction Java pour extraire des zones de pixels noirs contigus.
Le prof nous avait montré une méthode non récursive basée sur une liste de points à parcourir. La liste contient des doublets (x, y) représentant les coordonnées des points mémorisés. Il faut aussi copier la matrice, car cette méthode exige qu'on la modifie.
Mettons que la liste s'appelle L, et la copie de la matrice M.
Je vais esayer d'être le plus clair possible :
- on parcourt la première ligne de M pour trouver un 1, que l'on ajoute à L. C'est le point de départ.
- boucle while :
- pour chaque 1 dans L, on le met à 0 dans M et on regarde les voisins directs (gauche, droite, haut, bas) ; quand le voisin est à 1, on l'ajoute à L.
- si on a un point sur la dernière ligne, succès !
- fin boucle while
- si la liste est vide, ça veut dire que tous les 1 contigus ont été traités. À ce moment-là, il faut reparcourir la première ligne pour en trouver un autre et recommencer.
- si on n'a rien trouvé, échec.
Je sais que c'est un peu dur de se convaincre que cette méthode fonctionne, mais elle est garantie par deux choses :
- tous les 1 de L seront forcément traités, donc tous les voisins et les voisins des voisins, etc. du point de départ seront traités ;
- le programme ne va pas boucler car les points traités sont mis à 0 dans M.
Je reste dispo pour les questions ;)
les 1 de mon 1er exemple correspondent aux 'j' de ma fonction
Erreur : java.lang.ArrayIndexOutOfBoundsException : -1
Je connais cette erreur mais je suis un peu largué pour la corriger :/
J'ai besoin de vous ! :)
public int estGagnant(){ //Renvoit 0 si pas de gagnant, gagnant si on connecte les 2 bords // 1 si Jaune gagne int resultat = -1; int j=0; int condition = 0; //Piles Pile pileI = new Pile(); Pile pileJ = new Pile(); Pile sommetSave = new Pile(); //On scan la première ligne pour trouver les 'j', on stocke les coordonnées dans les 2 piles for(int i=0;i<nbCases;i++){ if(this.plateau[i][j] == 'j'){ pileI.empiler(i); pileJ.empiler(j); sommetSave.empiler(i); } } //1er scan terminé while(condition == 0){ //Case courante int iCourant = pileI.sommet(); int jCourant = pileJ.sommet(); int test=0; //Si case en dessous et jaune ET derniere ligne, partie gagnée pour Jaune ! if((this.plateau[iCourant][jCourant+1] == 'j') && (jCourant+1 == nbCases)){ return 1; } //Si une case a coté de la courante est jaune, on empile if((this.plateau[iCourant+1][jCourant] == 'j') && (!dejaPresent(pileI,pileJ,iCourant+1,jCourant))){ //Case a droite de la courante test++; pileI.empiler(iCourant+1); pileJ.empiler(jCourant); } if(this.plateau[iCourant][jCourant+1] == 'j' && (!dejaPresent(pileI,pileJ,iCourant,jCourant+1))){ //Case en bas de la courante test++; pileI.empiler(iCourant); pileJ.empiler(jCourant+1); } if(this.plateau[iCourant-1][jCourant] == 'j' && (!dejaPresent(pileI,pileJ,iCourant-1,jCourant))){ //Case à gauche test++; pileI.empiler(iCourant-1); pileJ.empiler(jCourant); } if(this.plateau[iCourant][jCourant-1] == 'j' && (!dejaPresent(pileI,pileJ,iCourant,jCourant-1))){ //Case au-dessus test++; pileI.empiler(iCourant); pileJ.empiler(jCourant-1); } //Si on enregistre 2 données, on sauvegarde le(s) sommet(s) while(test > 1){ sommetSave.empiler(sommetSave.sommet()-(test+1)); test--; } //Si pas de nouveau chemin if(test == 0){ //Si en plus pas de résultat sauvegardé if(sommetSave.estVide()){ condition = 1; } else{ pileI.setSommet(sommetSave.sommet()); pileJ.setSommet(sommetSave.sommet()); sommetSave.depiler(); } } } return resultat; } public boolean dejaPresent( Pile a, Pile b, int i, int j){ //Fonction qui recherche dans a et b si i et j sont déja présent boolean result = false; while(a.estVide()){ if((a.sommet() == i) && (b.sommet() == j)) result = true; a.depiler(); b.depiler(); } return result; }
Erreur : java.lang.ArrayIndexOutOfBoundsException : -1
Je connais cette erreur mais je suis un peu largué pour la corriger :/
J'ai besoin de vous ! :)
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Convaincu que la récursivité était la méthode la plus simple, je vous ai pondu la solution suivante:
NB: Je suis désolé, mais ce n'est que du 'C' ;-)
#include <stdio.h> #include <stdlib.h> #define LIGNE 8 #define COLON 7 int matrice [LIGNE][COLON] = { { 0, 0, 0, 0, 1, 0, 0 }, { 0, 0, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0, 1, 0 }, { 0, 0, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 1, 0, 0 }, { 0, 0, 0, 1, 1, 1, 0 }, { 0, 0, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 1, 1, 0 } }; int recursive (int matrice[][COLON], int colon, int nbLigne, int nbColon) { if (!matrice[0][colon]) return 0; // Non trouvable // Recherche du '1' le plus à gauche while ( (colon) && matrice[0][colon-1]) colon--; for (; (colon<nbColon) && matrice[0][colon]; colon++) if( (nbLigne == 1) || recursive(&matrice[1], colon, nbLigne-1, nbColon)) return 1; // Trouvé return 0; // Non trouvé } int main() { int i, retour; for (i=0; i<COLON; i++) if( (retour = recursive(matrice, i, LIGNE, COLON)) ) { printf("Trouvé départ=%d arrivée=%d!\n", i+1, retour); return (EXIT_SUCCESS); } printf("Non trouvé !\n"); return (EXIT_FAILURE); }Bonne réflexion.
NB: Je suis désolé, mais ce n'est que du 'C' ;-)
Salut loupius, comme on se retrouve ;)
Je suis pas sûr de comprendre ta boucle while « recherche du '1' le plus à gauche ». Il me semble qu'elle parcourt une ligne de matrice de droite à gauche, mais que se passe-t-il si la première valeur rencontrée est '0' ?
De plus, je pense que ton programme ne gère pas les parcours « qui remontent », du style :
Je suis prêt à livrer le code de mon propre algorithme, mais pas avant qu'on m'ait prié à genoux ^^ j'aime bien quand les gens cherchent un peu par eux-mêmes.
Je suis pas sûr de comprendre ta boucle while « recherche du '1' le plus à gauche ». Il me semble qu'elle parcourt une ligne de matrice de droite à gauche, mais que se passe-t-il si la première valeur rencontrée est '0' ?
De plus, je pense que ton programme ne gère pas les parcours « qui remontent », du style :
{ { 0, 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0, 0 }, { 0, 1, 1, 0, 1, 1, 1 }, { 0, 0, 1, 1, 1, 0, 1 }, { 0, 0, 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 1, 1, 1 }, { 0, 0, 0, 1, 1, 0, 0 }, { 0, 0, 0, 1, 0, 0, 0 } }
Je suis prêt à livrer le code de mon propre algorithme, mais pas avant qu'on m'ait prié à genoux ^^ j'aime bien quand les gens cherchent un peu par eux-mêmes.
int resultat = 0; int j=0; int condition = 0; //Piles Pile pileI = new Pile(); Pile pileJ = new Pile(); Pile sommetSave = new Pile(); //On scan la première ligne pour trouver les 'j', on stocke les coordonnées dans les 2 piles int var = 0; for(int i=0;i<nbCases;i++){ if(this.plateau[i][j] == 'j'){ pileI.empiler(i); pileJ.empiler(j); sommetSave.empiler(var); var++; } } int passage = 1; while(condition == 0){ System.out.println("Passage dans la boucle no :"+passage); int iCourant = pileI.sommet(); int jCourant = pileJ.sommet(); int test=0; //Si une case a coté de la courante est jaune, on empile if(iCourant<nbCases){ if((this.plateau[iCourant+1][jCourant] == 'j') && (!dejaPresent(pileI,pileJ,iCourant+1,jCourant))){ //Case a droite de la courante System.out.println("Case a droite detect"); test++; pileI.empiler(iCourant+1); pileJ.empiler(jCourant); } } if(jCourant<nbCases){ if(this.plateau[iCourant][jCourant+1] == 'j' && (!dejaPresent(pileI,pileJ,iCourant,jCourant+1))){ //Case en bas de la courante //Case Gagnante System.out.println("jCourant+1 : "+jCourant); System.out.println("iCourant+1 : "+iCourant); if(jCourant+2 == nbCases){ System.out.println("Jaune Gagne"); condition = 1; resultat = 1; } System.out.println("Case en bas detect"); test++; pileI.empiler(iCourant); pileJ.empiler(jCourant+1); } } if(iCourant>0){ if(this.plateau[iCourant-1][jCourant] == 'j' && (!dejaPresent(pileI,pileJ,iCourant-1,jCourant))){ //Case à gauche System.out.println("Case a gauche detect"); test++; pileI.empiler(iCourant-1); pileJ.empiler(jCourant); } } if(jCourant > 0){ if(this.plateau[iCourant][jCourant-1] == 'j' && (!dejaPresent(pileI,pileJ,iCourant,jCourant-1))){ //Case au-dessus System.out.println("Case au dessus detect"); test++; pileI.empiler(iCourant); pileJ.empiler(jCourant-1); } } System.out.println("Test : "+test); //Si on enregistre 2 données, on sauvegarde le(s) sommet(s) while(test > 1){ sommetSave.empiler(sommetSave.sommet()-(test+1)); System.out.println("Test 6"); test--; } //Si pas de nouveau chemin if(test == 0){ //Si en plus pas de résultat sauvegardé if(((sommetSave.sommet)-1) == 0){ System.out.println("sommetSave vide, plus rien a analyser"); condition = 1; //pain = 31; } else{ sommetSave.depiler(); System.out.println("Test 8"); System.out.println("On setSommet a : "+sommetSave.sommet()); pileI.setSommet(sommetSave.sommet()); pileJ.setSommet(sommetSave.sommet()); System.out.println("la new coordonnee est : ("+pileI.sommet()+","+pileJ.sommet()+")"); } } passage++; } return resultat;
Ca a l'air de fonctionner :p