Bonjour,
J'ai un petit problème, j'ai un tableau de string contenant n*m cases (donc un tableau en 2D). De plus, une case peut avoir deux états :
Les cases vides qui sont représentés par un espace.
Les cases qui représente un "pixel noir" et qui sont représentés par un "X"
L'idée est que j'ai implémenté l'algorithme de flood_fill qui consite a remplir une forme dans le tableau en lui donnant les coordonées d'une case vide (représenté par un espace) :
Pour mieux comprendre, voilà un exemple avec "flood_fill(array, 1, 2);"
Maintenant moi, mon problème c'est de trouver automatiquement ce "1,2". Du coup je suis partie du principe que j'allais re-utiliser flood_fill et que si je tombais sur les bors de mon tableau, donc i = 0 ou j = 0 et que la case n'était pas un X, ça veut dire que je suis en dehors d'une forme non? Et si c'est le cas, je mets une variable z (par référence) à 0 et je "return;" cela donne :
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 Avant : ---------- | XXXXXXX| | X X| |X X| |XXXXX X| | X X| | XXX X| | XX| | | | | ---------- Apres : ---------- | XXXXXXX| | XZZZZZZX| |XZZZZZZZX| |XXXXXZZZX| | XZZZX| | XXXZX| | XX| | | | | ----------
L'idée est donc que je parcours mon tableau en lancant check(array, i, j, z) et si j'ai (z != 0) alors je lance flood_fill sur i et j et tout devrait marcher correctement!
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 void check(std::string array[9][9], int i, int j, int &z) { if ((i == 0 || j == 0 || i == 8 || j == 8 ) && array[i][j] != "X") { std::cout << "Here" << std::endl; // Ca c'est mon print de debug pour le bug que j'explique après z = 0; return; } if (array[i][j] == " ") { array[i][j] = "Z"; z++; check(array, i+1, j, z); check(array, i-1, j, z); check(array, i, j+1, z); check(array, i, j-1, z); } }
Sauf que dans certain cas ça marche pas du tout.. Par exemple sur "check(array, 1, 3, 0);" et en modifiant mon tableau d'origine j'ai :
Du coup, le problème c'est que pour debugger un algo reccursif comme ça c'est ultra chaud... du coup je sèche un peu.
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 ---------- | XXXXXXX| | X X| |X X| | X| | X X| | XXX X| | XX| | | | | ---------- Here Here Here Here Here Here Here Here Here Here Here Here Here ---------- | XXXXXXX| | XZZZZZZX| |XZZZZZZZX| | ZZZZZZZX| | ZZZXZZZX| | ZZZXXXZX| | ZZZZZZXX| | ZZZZZZZ | | | ----------
Si quelqu'un a une idée ou des questions n'hésitez pas :-). Ou si quelqu'un a un meilleur algorithme pour trouver une forme je suis preneur!
Merci d'avance
Partager