[C++ Algo] Faire un remplissage en escargot dans une matrice

**Aspic** · 07/11/2010, 15h59

Bonjour,

Je cherche à remplir une matrice de taille (N*M) fixe en escargot en commençant par un point variable qui est forcément l'un des quatre coin

Exemple avec comme point de départ (0,0) :

En gros, on commence à remplir la première case
(0,0) puis (1,0) ... (1, N)
ensuite (2, N) puis (3, N) ... (N,M)
ensuite (N-1, M) ... (0, M)
ensuite (0, M-1) ... (0, 1) (1,1) ...

et ainsi de suite jusqu'à tout remplir

Voilà je sais pas si c'est simple à faire en C++ mais je sèche sur l'algo

Merci !

**Matthieu Brucher** · 07/11/2010, 16h33

4 boucles for, puis récursif sur l'intérieur de la matrice ?

**Aspic** · 07/11/2010, 16h47

Envoyé par Matthieu Brucher

4 boucles for, puis récursif sur l'intérieur de la matrice ?

Euh, un peu plus de détails ?

**Matthieu Brucher** · 07/11/2010, 16h53

Une boucle pour chaque face de la matrice, et ensuite tu refais la même chose sur la sous-matrice. Il faut simplement garder le niveau de récursion en mémoire.

**3DArchi** · 07/11/2010, 20h32

D'une certaine façon, ça peut aussi dépendre du type de structure utilisée pour la matrice. Autre chose, la taille de la matrice est connue à la compilation ?

**Aspic** · 07/11/2010, 22h11

J'avoue que j'ai un peu du mal avec la récursivité

Oui la taille de la matrice est fixe et connue à la compilation, elle est de 20 par 14...

**koala01** · 08/11/2010, 13h28

Salut,

En fait, pour ne pas foirer sa récursivité, le mieux est:

de définir le cas de base, c'est à dire, le cas dans lequel on ne rentre plus dans la récursivité
de faire en sorte que toute la logique tende vers ce cas de base.

Dans le cas que tu expose, il est même tout à fait possible de s'en sortir avec une seule boucle et la récursivité, même si un certain nombre de tests seront nécessaires pour assurer un remplissage correct.

En effet, on peut parfaitement estimer que l'on souhaite sur un écart clairement définit à chaque fois.

Ceci dit, l'important est de pouvoir déterminer la direction suivie lors du remplissage, et de pouvoir "basculer" de l'un à l'autre relativement facilement.

Ce que je te conseille donc, c'est la création d'une énumération proche de

Code :

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

1
2
3
4
5
enum direction
{
    horizontal, // on travaille sur la ligne
    vertical // on travaille sur la colonne
};

qui serait avantageusement desservie par l'opérateur ! qui s'assure de donner l'autre valeur, et dont une implémentation naïve pourrait être

Code :

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

1
2
3
4
5
direction operator ! (direction d)
{
    //renvoie vertical si d vaut horizontal et vice versa
    return (d==horizontal ? vertical : horizontal);
}

Pour que la fonction fonctionne, elle aura besoin, outre la matrice, de disposer:

de l'indice au départ duquel elle doit travailler
de l'indice d'arrivée qu'elle doit atteindre
de l'indice de départ de la dimension qui ne change pas
de l'indice d'arrivée de la dimension qui ne change pas
de la direction permettant de déterminer quelle est la dimension qui est manipulée.

Pour éviter les confusions tout en restant suffisamment "vague", je vais nommer ces informations respectivement movingBegin (indice de départ de la dimension qui change) movingEnd(indice d'arrivée de la dimension qui change), fixedBegin(indice de départ de la dimension qui ne change pas), fixedEnd(indice d'arrivée de la dimension qui ne change pas) et... d, qui nous permet de déterminer la dimension à manipuler.

Le cas de base est, sommes toutes, assez simple: si l'indice de départ de la dimension qui ne change pas (fixedBegin)correspond à l'indice d'arrivée de cette dimension (fixedEnd), hé bien C'EST-QU'ON-A-FI-NI.

Dans tous les autres cas, il faut savoir s'il faut compter de manière normale, ou s'il faut, au contraire, compter à rebours.

Il nous suffit donc de prévoir une variable qui représentera le pas appliqué à la boucle.

Par facilité, je vais nommer cette variable step.

Nous lui donnons la valeur +1 si l'indice de départ de la dimension sur laquelle on travaille (movingBegin) est plus petit que l'indice d'arrivée de cette dimension (movingEnd) et la valeur -1 si c'est le contraire.

Il faut aussi déterminer le dernier indice qui devra être utilisé par la boucle, car nous devons en permanence nous arrêter avant l'indice maximal à atteindre: il sera en effet considéré comme l'indice de départ de l'appel récursif suivant.

Le problème, c'est que cet indice réel correspond à l'indice à attiendre- 1 quand on compte normalement et à l'indice à atteindre +1 lorsque l'on compte à rebours.

Comme nous avons déterminé un pas qui est, justement de 1 ou de -1, nous pouvons définir une variable (end) dont la valeur est... l'indice à atteindre - step.

Il ne nous reste donc plus qu'à créer une boucle pour tout indice allant de movingBegin à end par step qui appellera la fonction de remplissage dont je parlerai tout de suite

.

Et, pour assurer la récursion, nous devrons enfin appeler notre fonction en veillant à lui passer comme paramètre, outre la matrice à remplir,

l'indice de départ de la dimension qui était fixe comme indice de départ de la dimension utilisée
l'indice de fin de la dimension qui était fixe comme indice de fin de la dimension utilisée
l'indice de fin de la dimension utilisée corrigée en fonction du pas (en fait, la variable end) comme indice de départ de la dimension fixe
l'indice de départ de la dimension utilisée comm indice de fin de la dimension fixe
la direction qui n'est pas celle que l'on a utilisé

L'algorithme (je l'ai écrit en C++, mais je ne vais quand même pas tout faire pour toi, sinon, ou serait le plaisir

) ressemblera donc à

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
soit la fonction escargot(Matrice, movingBegin, movingEnd, fixedBegin,
                           fixedEnd, d )
SI fixedBegin est égal à fixedEnd
    c'est fini
SINON
    SI movingBegin est plus petit que movingEnd
        step vaut 1
    SINON
        step vaut -1
    FIN SI
    end vaut movingEnd - step
    POUR i valant movingBegin et tant que i ne vaut pas end par step
        Appeler fill( la matrice, i, fixedBegin, d )
    FIN POUR
        escargot( fixedBegin, fixedEnd, end, movingBegin, !d )
FIN SI

La fonction de remplissage (fill) enfin devra "simplement" vérifier la direction qui lui est donnée afin de déterminer si elle dois travailler sur la position en X (horizontale) ou la position en Y (verticale).

La position fournie par i sera la position "variable" et la position donnée par fixedBegin sera la position "fixe".

Elle pourrait donc ressembler à quelque chose comme

Code :

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

1
2
3
4
5
6
7
void fill(Matrice, variable, fixe, d)
{
    if(d==horizontal)
        // on travaille sur la position en X
    else
        // on travaille sur la position en Y
}

Et voilà... le tour est joué

A toi à transformer tout cela en code

**koala01** · 08/11/2010, 13h55

j'ai failli oublier...

l'appel de la fonction depuis ton programme se fera sous une forme proche de

Code :

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

1
2
3
4
5
6
int main()
{
    Matrice laMatrice;
   /*...*/
   escargot(laMatrice,0,14,0,20,horizontal);
}

Invité · 08/11/2010, 14h33

Bonjour,
Je ne vais pas trouver une réponse meilleure, mais j'ai eu le cas pour une recherche en escargot à partir du centre du tableau. En fait c'est pas vraiment en excargot, puisque le but était de tester toutes les cases, en s'éloignant au fur et à mesure du centre.
J'ai fini par adopter le principe suivant : chaque case a une position connue par rapport au point d'origine et un ordre de visite connu.
J'ai une simple boucle et un switch avec autant de cases qu'il y a de positions à tester. Cela peut paraitre un peu lourd, mais si la dimension du tableau est fixe, ainsi que le sens de parcourt, c'est la solution la plus rapide puisqu'il n'y a aucun test. Et dans mon cas, c'était le plus important.

**koala01** · 08/11/2010, 14h36

Envoyé par Pierre Dolez

Bonjour,
Je ne vais pas trouver une réponse meilleure, mais j'ai eu le cas pour une recherche en escargot à partir du centre du tableau. En fait c'est pas vraiment en excargot, puisque le but était de tester toutes les cases, en s'éloignant au fur et à mesure du centre.
J'ai fini par adopter le principe suivant : chaque case a une position connue par rapport au point d'origine et un ordre de visite connu.
J'ai une simple boucle et un switch avec autant de cases qu'il y a de positions à tester. Cela peut paraitre un peu lourd, mais si la dimension du tableau est fixe, ainsi que le sens de parcourt, c'est la solution la plus rapide puisqu'il n'y a aucun test. Et dans mon cas, c'était le plus important.

Euhhhh... et ton switch case... c'est pas des tests

Sans compter que les tests restent particulièrement simples dans l'algorithme que je présente

Invité · 08/11/2010, 14h49

Euhhhh... et ton switch case... c'est pas des tests

Un switch c'est un branchement codé à la compilation.

Sans compter que les tests restent particulièrement simples dans l'algorithme que je présente

Je ne pense pas avoir dit que ma méthode est meilleure, jamais je n'oserais faire une chose pareille, simplement je voulais exposer une méthode pour la recherche dans un tableau raster donc de grande dimension. Ma zone de recherche se limite à un carré de 7x7. Très modestement, je voulais simplement participer.

**Aspic** · 08/11/2010, 18h18

Envoyé par Pierre Dolez

Bonjour,
Je ne vais pas trouver une réponse meilleure, mais j'ai eu le cas pour une recherche en escargot à partir du centre du tableau. En fait c'est pas vraiment en excargot, puisque le but était de tester toutes les cases, en s'éloignant au fur et à mesure du centre.

Dans mon cas, je ne veux pas partir du centre mais justement terminer au centre

Je suis rentré chez moi, je vais tenter de coder l'algo et de le tester

**Aspic** · 08/11/2010, 18h46

Alors ca marche pas mal

Mais y'a un bug, il y a une colonne (la première) qui n'est pas prise en compte dans l'ecargot.

Voici mon algo adapté à l'Allegro (ne vous souciez pas de la structure BITMAP* ...)

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
 
// appel principal :
escargot2(zoneJeu, 0, 20, 0, 14, true); // zoneJeu est une BITMAP* celle affichée à l'écran qui est blanche de base
 
bool escargot2(BITMAP* masque, int movingBegin, int movingEnd, int fixedBegin, int fixedEnd, bool d)
{
    int step, end;
 
    if (fixedBegin == fixedEnd)
    {
        printf("fin\n");
        return false;
    }
    else
    {
        if (movingBegin < movingEnd) step = 1;
        else step = -1;
 
        end = movingEnd - step;
        for (int i = movingBegin; i != end; i+=step)
        {
            // horizontal
            if (d == true)
            {
                // ajustement de +16 pr avoir le centre de la case
                printf("case : %d %d\n", i*TX+16, fixedBegin*TY+16);
                circlefill(masque, i*TX+16, fixedBegin*TY+16, 2, ROUGE);
            }
            else
            {
                printf("case : %d %d\n", fixedBegin*TY+16, i*TX+16);
                circlefill(masque, fixedBegin*TY+16, i*TX+16, 2, BLEU);
            }
            refreshZone(masque, 32); // affiche à l'écran
            rest(50); // ralenti la boucle
        }
 
        return escargot2(masque, fixedBegin, fixedEnd, end, movingBegin, !d);
    }
}

Et une vidéo pour montrer le résultat !
http://www.tutoworld.com/temp/escargot.avi

Merci

Invité · 08/11/2010, 19h29

Oui, c'est pas mal.
Le contexte dont j'ai parlé, la recherche à partir du centre a une finalité différente. Ce n'était même pas un autre solution.
L'image s'efface très rapidement quand c'est fini, je me demande si le dernier point est fait.
Pour la première colonne, ça va pas être facile de le tester. Je pense à une solution : dans ce cas présent le départ est en haut à gauche, avant d'appeler la fonction la première fois, vous dessinez la première colonne de bas en haut. Ca me parait plus économique que de faire un test dans la fonction.
Bonne soirée.

**Aspic** · 08/11/2010, 20h21

Envoyé par Pierre Dolez

Pour la première colonne, ça va pas être facile de le tester. Je pense à une solution : dans ce cas présent le départ est en haut à gauche, avant d'appeler la fonction la première fois, vous dessinez la première colonne de bas en haut. Ca me parait plus économique que de faire un test dans la fonction.
Bonne soirée.

J'y est pensé mais à mon avis j'ai mal codé l'algo de Koala car y'a juste pour cette colonne que ca marche pas et c'est normal...

Peux être que si Koala passe par là il verras le soucis

Sinon effectivement le dernier point n'est pas fait mais c'est pas grave

**koala01** · 08/11/2010, 20h42

A vrai dire, voilà le code tel que je l'ai écrit de mon coté... adapté à l'utilisation de BITMAP...:

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
enum direction
{
    horizontal,
    vertical
};
direction operator ! (direction d)
{
    return (d==horizontal ? vertical : horizontal);
}
void fill(BITMAP * mask, int variable, int constant, direction d)
{
    if(d==horizontal)
        /* variable sert pour la dimension horizontale et constant pour
         * la direction verticale
         */
    else
        /* ici, c'est l'inverse ;) */
}
void escargot(BITMAP* mask,int movingBegin, int movingEnd, int fixedBegin,
              int fixedEnd,direction d)
{
    if(fixedBegin==fixedEnd)
    {
        /* ne fait simplement rien: on a fini le travail :D */
    }
    else
    {
        int step=(movingBegin<movingEnd)? 1:-1;
        int end=movingEnd - step;
        for(int i=movingBegin;i!=end;i+=step)
        {
            fill(mask,i,fixedBegin,d);
        }
        escargot(fixedBegin,fixedEnd,end,movingBegin,!d);
    }
}
int main()
{
    escargot(0,20,0,14,horizontal);
}

Je te laisse juste gérer l'affichage des points

(dans la fonction fill )

**Aspic** · 08/11/2010, 21h04

Et il remplit bien toute la matrice chez toi ?
Car ton code produit le même résultat que le mien, à savoir la colonne de gauche n'est pas remplie...

Invité · 09/11/2010, 11h30

Bonjour,
Pour le cas de la première colonne, ça ne m'étonne qu'à moitié. J'ai remarqué que toutes les organisations avec fonction récursives sont précédées d'une "première colonne".

**Aspic** · 09/11/2010, 13h21

Envoyé par Pierre Dolez

Bonjour,
Pour le cas de la première colonne, ça ne m'étonne qu'à moitié. J'ai remarqué que toutes les organisations avec fonction récursives sont précédées d'une "première colonne".

Ah bon ? enfin pour l'instant j'ai une parade mais ca me parrait quand même bizarre, si jamais quelqu'un passe par là et trouve une explication

Invité · 09/11/2010, 13h52

Je voulais parler de "mes organisations" et non "les ..". (le L et le M sont très proches sur mon clavier

)
C'est à dire que c'était un constat que j'avais fait pour mes algo.
Dans le cas présent, on peut l'expliquer par le fait que la première colonne est considérée comme "déjà traitée", puisqu'on a déjà fait 3 côtés.

[C++ Algo] Faire un remplissage en escargot dans une matrice

C++

Discussions similaires

Partager

Partager