Discussion :

[Opérateur]

Bonjour,

Dans le cadre d'un projet (je précise que je ne suis pas encore expert en programmation) je suis amené à déterminer toute la zone d'éléments adjacents identiques à un élément donné d'une matrice de caractère (je travaille en C++)

J'explique ce que j'entends par là :

J'ai une matrice m*n composée de trois caractères différents (il y a donc des répétitions). Un élément est adjacent à un autre élément s'il est situé en dessous, au dessus, à droite ou à gauche de celui-ci (par exemple : les éléments adjacents à l'élément central M[i][j] sont M[i + 1][j], M[i - 1][j], M[i]j+1] et M[i][j - 1])

Soit donc un élément M[i][j] contenant le caractère X je dois trouver toute la zone d'éléments adjacentes à M[i][j] et contenant le même caractère X.
Pour ce faire je dois donc :

- déterminer tous les éléments adjacents à M[i][j] et contenant X
- déterminer tous les éléments contenant X adjacents à une case adjacente à M[i][j] contenant X
- ... (je continue ainsi jusqu'a être arrivé au bout de la zone)

Graphiquement sur un exemple :

Voilà M (contenant les caractères 1,a et y) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
a a a a a y y y y 1 1 a a a
1 1 1 1 a a a a a 1 y y 1 y
y y y y y a a a a 1 a 1 y y
1 y 1 a 1 y y y a y 1 1 1 1
a y 1 1 a a 1 a a 1 1 1 y y
y y 1 1 1 1 1 1 y 1 1 1 1 1

Si je prends l'élément M[0][2] (ligne 0, colonne 2) la zone que je dois déterminer est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
a a a a a 
        a a a a a 
          a a a a 
                a 
              a a

Savez-vous comment je pourrais écrire un tel algorithme en C++ ?
Je pense que par récurrence c'est faisaible mais je n'ai pas encore étudié cette méthode de programmation donc je dois y parvenir sans elle.

Si vous avez une idée je suis preneur

merci

[Sylvain Togni]

Recherche "Flood Fill", c'est le nom de l'algorithme le plus courant pour faire ce genre de chose.

En gros, il faut nourrir une pile avec tous les voisins non encore visités puis prendre l'élément au sommet et ainsi de suite jusqu'à ce que la pile soit vide.

[Nemerle]

disons que tu stockes tes couples dans un vector E d'éléments (a,b).

Pour déterminer la zone à partir de M[i,j] où i,j sont donnés, tu fais (en franco algo ):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
booléen b=true;
E=vide
Ajouter (i,j) à E
Tant que b=true{
   booléen c=false
   Pour tout (a,b) de E{
      si(a<m){si M[a+1,b]=M[i,j] alors (Ajouter (a+1,b) à E et c=true)}
      si(a>1){si M[a-1,b]=M[i,j] alors (Ajouter (a-1,b) à E et c=true)}
      si(b<n){si M[a,b+1]=M[i,j] alors (Ajouter (a,b+1) à E et c=true)}
      si(b>1){si M[a,b-1]=M[i,j] alors (Ajouter (a,b-1) à E et c=true)}
   }
   si c=false alors b=false
}

[Opérateur]

Ah d'accord je vais voir ça !

merci bien pour vos deux réponses

[Opérateur]

Ton algorithme marche assez bien nemerle, merci bien

Mais j'ai toutefois un problèmes. Il ne s'arrête jamais et je n'ai pas eu trop de mal à trouver pourquoi :

Il ne faut pas que j'ajoute deux fois le même élément dans le vecteur E sinon forcément

1) J'ai des éléments en trop de le vecteur

et alors pire

2) L'algo ne s'arrête jamais :

Mettons que la zone contienne 2 éléments disposé ainsi :

y
y

L'algo va tester pour le y du dessus (élément N°1 de E) , il ne va trouver comme élément à ajouter que celui du dessous (elément N°2 de E). Ok, après cela il passe à l'élément du dessous (il faut bien car il a été rajouté au vecteur). Il va trouver l'élément du dessus et va le rajouter ( élément N°3, alors qu'il s'y trouve déja), etc.

Il faut donc à tout pris que j'évite de rajouter des éléments qui s'y trouvent déja.
Sais-tu comment je pourrais faire ça de manière efficace ? Bien sûr en faisant une recherche préalable dans le vecteur avant d'ajouter un élément ça s'arrangera mais je perderai de l'efficacité

en tout cas merci beaucoup !

[Opérateur]

J'ai vite fait implémenté une petite recherche

Je ne sais pas s'il est possible d'éviter d'en faire une ? J'ai pas encore calculer la complexité de ce code mais ça ne doit pas etre fameux

En tout cas comme ça ça fonctionne, merci infiniment

[Sylvain Togni]

Pour éviter une recherche tu peux utiliser une matrice de booléens pour marquer les éléments déjà visités et ne pas les visiter à nouveau.

[Nemerle]

sorry du retard, j'étais en déplacement à Panam

Effectivement, j'ai oublié un mini-truc:

les 4 conditionnelles

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

si M[a+1,b]=M[i,j]...

doivent être remplacées par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

si (M[a+1,b]=M[i,j] ET (a+1,b) n'appartient pas à E)...

Voila. Tu peux utiliser une matrice de booléen, ou toute fonction d'appartenance. [EDIT] OU MIEUX: après avoir ajouté (x,y) à E, tu "détruis" M[x,y] en passant la valeur à 0. Cela t'oblige de dupliquer ta matrice avant d'appliquer cet algo, mais cela t'évite la matrice de booléens ou la fct d'appartenance dans le vecteur !! [/EDIT]

Franchement, tu aurais pu trouver tout seul

[Opérateur]

Désolé pour le restard de ma réponse j'étais aussi assez occupé ces derniers jours et j'ai délaissé mon ordinateur.

Ah mais j'y suis parvenu (en détruisant M[x][y] comme tu dis), je n'ai meme pas eu besoin de dupliquer la matrice vu que je n'ai plus besoin des éléments en questions.

Mais sinon ceci suffit en fait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
Pour tout (a,b) de E{
      si(a<m){si M[a+1,b]=M[i,j] alors (Ajouter (a+1,b) à E et c=true)}
      si(a>1){si M[a-1,b]=M[i,j] alors (Ajouter (a-1,b) à E et c=true)}
      si(b<n){si M[a,b+1]=M[i,j] alors (Ajouter (a,b+1) à E et c=true)}
      si(b>1){si M[a,b-1]=M[i,j] alors (Ajouter (a,b-1) à E et c=true)}
   }

Pas besoin de chipoter avec des variables booléennes a et b

Ca fonctionne très bien maintenant, un grand merci à tous

P.S. : Si quelqu'un désire le code C++ du petit programme que vous m'avez aider à concevoir (c'est un bête jeu à 4 sous sur la ligne de commande) je peux lui envoyer en guise de remerciement (même si c'est sans doute sans intérêt pour vous )