Discussion :

[trihanhcie]

Bonjour,

Je suis peu rouillé niveau algo...
Supposons une matrice 2d avec des 0 et 1.

Je cherche à connaitre le nombre de groupe de 1 qui sont contenus dans la matrice. Les "1" font parti d'un meme groupe s'ils sont adjacents (horizontalement, verticalement ou oblique).

Exemple:
1 0 0 1
1 0 1 0
0 0 1 0
1 0 0 0

Retournerait 3

Quel est la meilleure manière de procéder. Je pensais créer une autre matrice ou je sauvegarderais les "index" que j'ai déjà parcouru mais je me demande si c'est la bonne méthode.

Merci

[Invité]

salut,

tu as plus simple.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
    nbGroupe = 0
    pour chaque ligne
        pour chaque colonne
            si ta case courante est un 0 tu skip
            sinon
                groupeExistant = false
                pour les cases adjacentes (de la ligne du dessus, ou celle de droite) as candidate
                    si candidate==1 alors
                        //notre case courante appartient à ce groupe
                        groupeExistant = true
                    finsi
                finpour
                si groupeExistant == false alors
                    //cest le tout premier 1 isolé
                    nbGroupe++
                finsi
            finsi
        finpour
    finpour

[Flodelarab]

Bonjour

@galerien69 : Pardon, rien de personnel, mais je ne crois pas que ça marche.
Exemple:
1 0 0 1
1 1 1 0
0 0 1 0
1 0 0 0
A la première ligne, tu vas créer 2 groupes, alors qu'il s'agit du même (qui va se relier par la suite).


Personnellement, je ferais un système de coloriage.
Une case contenant un 1 prend un nombre et colorie tous ces voisins (égaux à 1) de ce nombre.
Le résultat est le plus grand nombre moins un.
Dans l'exemple initial, tu aurais les groupes 2, 3, 4. Donc, nombre de groupes: 3.

[Invité]

hello Flodelarab,

mais je ne crois pas que ça marche.

et tu as absolument raison

j'etais parti sur considérer des chaines (comme au go) donc comprendre chaque el d'une même chaine pointe vers la même valeur
lorsque deux chaines se rencontre (idem on compare la valeur pointée de deux cel "candidate" et celles-ci diffèrent), on met à jour la valeur pointée des deux pointeurs respectifs vers la même valeur (et on soustrait 1 au compte du nombre de chaine) puis dans l'euphorie de la simplification je m'y suis perdu.

je vais qd même tenter de corriger l'algorithme du premier poste (je suis convaincu qu'il n'y a pas besoin d'autant d'espace utilisé (pointeur à chaque fois) et qu'il n'y a pas non plus besoin de masques binaires pour représenter l'union de chaine par case)

edit: version corrigée de l'algo du premier poste. Je laisse le code.
Dans les grandes lignes:
meme check des cellules adjacentes (sauf que sur cellule de gauche au lieu de droite..)
etude du pattern
xxx
x1
avec le merge de chaine en fonction des valeurs de x (même idée de coloriage que Flodelarab sauf qu'appliqué à un plus petit motif)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    function P(i,j,v){
        m[i][j]=v;
    }
 
    var nbGroupes=0;
    var id=0;//le premier id que nous allouerons vaudra 1
    for(var i = 0;i<m.length; ++i){
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)==0)continue;
            if(i==0){
                if(j==0){
                    nbGroupes++;
                    id++
                    P(i,j,id)
                }else{
                    //si i==0 on regarde pas les cases adjacentes du dessus... donc seul check sur case de gauche
                    if(M(i,j-1)){
                        P(i,j,M(i,j-1));
                    }else{
                        nbGroupes++;
                        id++
                        P(i,j,id)  
                    }
                }
            }else{
                if(j==0){
                    var oneOrOther = M(i-1,j)||M(i-1,j+1)
                    //si j==0 il y a au maximum une chaine
                    if(oneOrOther){
                        P(i,j,oneOrOther)
                    }else{
                        nbGroupes++;
                        id++
                        P(i,j,id)
                    }
                }else{
                    //trois cas: nouvelle chaine, existe 1 chaine, existent deux chaines distinctes
                    var c1 = null;//représente la valeur de la première chaine
                    var c2 = null;
                    var candidates = [M(i,j-1), M(i-1,j-1), M(i-1,j), M(i-1,j+1)]; //resp à gauche et les trois du haut
                    candidates.forEach(x=>{
                        if(x==0)return;
                        if(c1==null||x==c1){
                            c1 = x;
                        }else{
                            c2=x;
                        }
                    })
                    if(c2){
                        //la chaine "c1" prend les coeffs de la chaine c2
                        //on ne considere que les coeff de la ligne courante avant lel courant
                        //ainsi que ceux depuis la colonne "à droite" de lel courant sur la ligne précédente
                        //car c'est le seul cas ou on peut avoir deux chaines distinctes
                        //0  0  2
                        //1 <-  ^
                        nbGroupes--;
                        for(var j1 = 0; j1<=j; ++j1){
                            if(M(i,j1)==c1){
                                P(i,j1,c2)
                            }
                        }
                        for(var j1 = j+1; j1<m[i].length; ++j1){
                            if(M(i-1,j1)==c1){
                                P(i-1,j1)=c2
                            }
                        }
                    }else{
                        if(c1){
                            P(i,j,c1)
                        }else{
                            nbGroupes++
                            id++
                            P(i,j,id)
                        }
                    }
                }
            }
        }
    }
    return nbGroupes;
}
 
 
 
//useless below
var assert = require('assert');
function test(s,exp){
    var m = s.split('\n').map(x=>x.trim()).filter(x=>x.length).map(x=>x.split(/\s+/).map(y=>parseInt(y)));
    assert.equal(run(m), exp);
    return m;
}
/*
var m;
s = `
1 0 1
1 0 1
1 1 1
`;
test(s, 1)
 
s = `
1 0 1
0 1 1
0 1 0
`;
test(s, 1)
 
s = `
1 0 1
0 0 0
0 1 0
`;
test(s, 3)
 
 
s = `
1 0 1
0 0 0
0 1 0
`;
test(s, 3)
 
s =`
1 0 0 1
1 1 1 0
0 0 1 0
1 0 0 0
`
test(m,2)
 
 
s =`
1 0 0 1
1 0 1 0
0 0 1 0
1 0 0 0
`
test(s,3)*/
 
s = `
1 1 0 1
1 1 0 1
0 0 1 0
1 0 0 0
`
console.log(test(s, 2))//merge deux chaines

@flodelarab
je n'ai compris ta version qu'apres, mais effectivement, elle simplifie bcp l'algo

[trihanhcie]

Merci !!

La solution de Flodelrab me parle... mais je ne suis pas sur de l'algo
Par exemple,

1 0 0 1
1 0 1 1
1 0 0 0
0 0 0 1

M(0,0) = 1 ainsi M(1,0)
M(0, 3) = 2 car il n'a pas ete colorie et M(1,2) = 2 et M(1,3) = 2
M(1, 0) = 1 donc M(2,0)= 1
M(3,3) = 3 car il n'a pas ete colorie.

est ce que j'ai manque quelque chose?

[Flodelarab]

est ce que j'ai manque quelque chose?

Oui, le recoloriage.
Ce qui n'arrive pas si tu fais une récursivité.
Sinon, un groupe pourra être bicolore, tricolore... ou pire.

Je modifie un peu ton exemple:

1 0 0 1 0
1 0 1 1 0
1 0 0 0 1
0 0 1 0 0

M(0,0) = 2. Ainsi M(0,1) = 2. Ainsi M(0,2) = 2.
M(3,0) = 3. Ainsi M(2,1) = 3, M(3,1) = 3. Ainsi M(4,2) = 3
M(2,3) = 4.

2 0 0 3 0
2 0 3 3 0
2 0 0 0 3
0 0 4 0 0

Et pour être bien clair, tu vas traiter les voisins des voisins, avant de traiter les voisins.