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

Version imprimable

07/11/2010, 15h59
Aspic

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

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 !
07/11/2010, 16h33
Matthieu Brucher

4 boucles for, puis récursif sur l'intérieur de la matrice ?
07/11/2010, 16h47
Aspic

Citation:

Envoyé par Matthieu Brucher

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

Euh, un peu plus de détails ? :oops:
07/11/2010, 16h53
Matthieu Brucher

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.
07/11/2010, 20h32
3DArchi

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 ?
07/11/2010, 22h11
Aspic

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...

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:

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:

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 :question:) ressemblera donc à
Code:

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:

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é ;):D

A toi à transformer tout cela en code :D

08/11/2010, 13h55
koala01
j'ai failli oublier...

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

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

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.
08/11/2010, 14h36
koala01

Citation:

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 :question:

Sans compter que les tests restent particulièrement simples dans l'algorithme que je présente ;)
08/11/2010, 14h49
Invité

Citation:

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

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

Citation:

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.
08/11/2010, 18h18
Aspic

Citation:

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

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:

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

08/11/2010, 19h29
Invité

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.
08/11/2010, 20h21
Aspic

Citation:

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 :D

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

Code:

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 )

08/11/2010, 21h04
Aspic

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...
09/11/2010, 11h30
Invité

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".
09/11/2010, 13h21
Aspic

Citation:

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 :P
09/11/2010, 13h52
Invité

Je voulais parler de "mes organisations" et non "les ..". (le L et le M sont très proches sur mon clavier :oops:)
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.

Ma tentative de le faire sans récursion, parce que c'est plus marrant :D :

Code:

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
const int DX[] = { 1, 0, -1, 0 };
const int DY[] = { 0, 1, 0, -1 }; // DY = DX[(i + 3) % 4]
 
void step(int x, int y) {
   printf("x=%d, y=%d\n", x, y);
}
 
void walk(int xMax, int yMax) {
   // A chaque itération, on ressert le contour à parcourir.
   for (int x1 = 0, y1 = 0, x2 = xMax, y2 = yMax; x1 < x2 && y1 < y2; ++x1, ++y1, --x2, --y2) {
       // On commence en haut à gauche et on réalise un contour complet en 4 étapes.
       int x = x1;
       int y = y1;
       for (int i = 0; i < 4; ++i) {
           // Le vecteur précalculé de déplacement à l'étape i.
           int dx = DX[i];
           int dy = DY[i];
           do {
               // Dans le cas d'un contour plat (x2-x1=1 et/ou y2-y1=1),
               // on ne marque pas les cases en dehors.
               if (x1 <= x && x < x2 && y1 <= y && y < y2) {
                   step(x, y);
               }
               x += dx;
               y += dy;
           } while (x1 <= x + dx && x + dx < x2 && y1 <= y + dy && y + dy < y2);
       }
   }
}
 
int main(int, char **) {
    walk(5, 2);
    return EXIT_SUCCESS;
}

Ca marche aussi avec des tailles du type 0x6, 1x1, 3x1, etc. Mine de rien, ce sont des cas aux limites bien pénibles (du moins en non récursif).

10/11/2010, 11h05
Invité

Bonjour,
Moi, je préfère cette méthode plutôt que la récursivité. Je n'utilise la récursivité que rarement, par exemple pour les arbres.
Je pense surtout à la pile et au contre-exemple du calcul de !n.
Pour le cas précis j'aurais peut-être été un peu plus détaillé, c'est à dire faire 4 boucles successives au lieu d'une seule avec 4 compteurs.
10/11/2010, 11h41
Goten

Les arbres ça se parcour aussi sans récursivité ... tant qu'a faire.
Mais bon, de nos jours je vois pas l'intérêt d'éviter la récursivité, tant que c'est bien placé et bien réfléchi. (la majorité des compilo implémentent le TCO)
10/11/2010, 12h08
Invité

Bonjour Goten,

Citation:

de nos jours ...

C'est vrai mais il y a tellement longtemps que j'ai commencé à développer, que certaines méthodes sont restées des habitudes. En Fortan on était obligé de trouver des astuces pour "tromper le compilateur" si on voulait faire des fonctions récursives.
Je suis resté avec cette façon de penser qui consiste à dire que si on est dans environnement où on doit faire exactement la même chose que ce qui a amené à entrer dans cet environnement, alors c'est de la récursivité, sinon c'est de la répétition, bouclage.
Dans le cas présent de remplissage avec décalage, pour moi, c'est plutôt du bouclage que de la récursivité.
En cas de récursivité, il serait impossible de commencer par la fin, en cas de bouclage, cela ne présenterait, généralement, aucune difficulté.