Matrice, trajet

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

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 ;)

Vraiment merci pour cet algo, je regarde ça demain !

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 ! :)

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' ;-)

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.

		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

Ah j'ai encore des soucis de boucles infinies ;'(