Sujet Précédent Sujet Suivant

Matrice, trajet

Fermé
Apaachee Messages postés 248 Date d'inscription mardi 13 novembre 2007 Statut Membre Dernière intervention 25 août 2011 - 10 déc. 2009 à 15:17
Apaachee Messages postés 248 Date d'inscription mardi 13 novembre 2007 Statut Membre Dernière intervention 25 août 2011 - 12 déc. 2009 à 09:34
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.

8 réponses

Réponse 1 / 8
Pilow Messages postés 400 Date d'inscription vendredi 2 octobre 2009 Statut Membre Dernière intervention 23 décembre 2009 71
10 déc. 2009 à 15:26
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 : 

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
0
Réponse 2 / 8
Groarh Messages postés 682 Date d'inscription vendredi 1 août 2008 Statut Membre Dernière intervention 28 juin 2015 185
10 déc. 2009 à 16:49
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 ;)
0
Pilow Messages postés 400 Date d'inscription vendredi 2 octobre 2009 Statut Membre Dernière intervention 23 décembre 2009 71
10 déc. 2009 à 16:58
Ah oui j'avais utilisé une méthode aussi a peu près similaire pour une histoire de promenade dans un labyrinthe, autant pour moi c'est beaucoup plus simple si je me souviens bien
0
Réponse 3 / 8
Apaachee Messages postés 248 Date d'inscription mardi 13 novembre 2007 Statut Membre Dernière intervention 25 août 2011 47
10 déc. 2009 à 21:44
Vraiment merci pour cet algo, je regarde ça demain !
0
Réponse 4 / 8
Apaachee Messages postés 248 Date d'inscription mardi 13 novembre 2007 Statut Membre Dernière intervention 25 août 2011 47
10 déc. 2009 à 23:02
les 1 de mon 1er exemple correspondent aux 'j' de ma fonction 

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 ! :)
0
Pacorabanix Messages postés 3248 Date d'inscription jeudi 23 août 2007 Statut Membre Dernière intervention 19 mai 2013 661
11 déc. 2009 à 00:49
déjà dis-nous quand elle apparait ! (met des System.out.println() dans ton code pour tracer sur la cousole)
0
Pacorabanix Messages postés 3248 Date d'inscription jeudi 23 août 2007 Statut Membre Dernière intervention 19 mai 2013 661 > Pacorabanix Messages postés 3248 Date d'inscription jeudi 23 août 2007 Statut Membre Dernière intervention 19 mai 2013
11 déc. 2009 à 00:51
un rapide coup d'oeil me dis aussi qu'il est probable qu'elle soit par là :

jCourant+1

si jCourant est le dernier ça pose problème.
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 8
loupius Messages postés 697 Date d'inscription dimanche 1 novembre 2009 Statut Membre Dernière intervention 31 décembre 2017 148
11 déc. 2009 à 03:39
Convaincu que la récursivité était la méthode la plus simple, je vous ai pondu la solution suivante:
#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' ;-)
0
Réponse 6 / 8
Groarh Messages postés 682 Date d'inscription vendredi 1 août 2008 Statut Membre Dernière intervention 28 juin 2015 185
12 déc. 2009 à 02:11
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 : 

{ { 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.
0
loupius Messages postés 697 Date d'inscription dimanche 1 novembre 2009 Statut Membre Dernière intervention 31 décembre 2017 148
12 déc. 2009 à 03:37
Salut,
Ah c'est vrai je n'ai pas du tout pensé au parcours remontant !
La boucle 'while' parcourt la ligne à partir de 'colon' (qui est forcément un '1' (testé par if (!matrice[0][colon]))) en remontant vers 'colon = 0' (le test sur 'colon' assurant de ne pas devenir négatif).
Bonne réflexion.
0
Réponse 7 / 8
Apaachee Messages postés 248 Date d'inscription mardi 13 novembre 2007 Statut Membre Dernière intervention 25 août 2011 47
12 déc. 2009 à 08:19 
		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
0
Réponse 8 / 8
Apaachee Messages postés 248 Date d'inscription mardi 13 novembre 2007 Statut Membre Dernière intervention 25 août 2011 47
12 déc. 2009 à 09:34
Ah j'ai encore des soucis de boucles infinies ;'(
0

Discussions similaires

Problème colissimo suivi
Kim -
contrariness -

1 réponse
"Vous ne pouvez pas modifier une partie de matrice"
ptéranodon -
ptéranodon -

2 réponses
colis prêt à être expédiée depuis 9 jours !
Bobdurochelot -
lolo3402 -

4 réponses
Diagonale principale et diagonale secondaire d'une matrice
Nicki_5595 -
Nicki_5595 -

6 réponses
matrice
spider2017 -
eriiic -

1 réponse