Vous connaissez certainement les jeux de la trempe des kikoo et autres, dont le but est de faire disparaitre des blocs de couleurs en cliquant sur ceux ci, à condition qu´il existe un ou plusieurs blocs adjacents de la même couleur.
J´aimerais assez me lancer dans la création d´un jeu du même type ( en C++ bien sûr ) , mais je souhaiterais élaborer un algorithme efficace pour réaliser cette tache ( calcul des blocs ) .

Je viens d´en rédiger un en utilisant la récursivité, mais je craint fort que la mémoire sature ou que les performances soient excécrables.
Ca donne ca en pseudocode ( j´ai pas mis les protoypes ) :

. ..

int GetNbBlocks( int couleur ( du bloc cliqué ) )
{
int nombre = 1;

nombre += GetBlocksRight( couleur ) ;
nombre += GetBlocksLeft( couleur ) ;
nombre += GetBlocksUp( couleur ) ;
nombre += GetBlocksDown( couleur ) ;

return nombre;
}

int GetBlocksRight( int couleur )
{
int nb = 0;

Si le bloc courant ( à droite donc ) est ! = couleur
return 0;

sinon // Regarde les blocs adjacents
nb++;

nb += GetBlocksLeft( couleur ) ;
nb += GetBlocksUp( couleur ) ;
nb += GetBlocksDown( couleur ) ;

return nb;
}

int GetBlocksLeft( int couleur )
{
int nb = 0;

Si le bloc courant ( à gauche donc ) est ! = couleur
return 0;

sinon // Regarde les blocs adjacents
nb++;

nb += GetBlocksRight( couleur ) ;
nb += GetBlocksUp( couleur ) ;
nb += GetBlocksDown( couleur ) ;

return nb;
}

[ etc . .. ]

Bon la j´ai rédigé ca en C, mais je l´implémenterais en C++.
Dans le programme, on trouvera les instructions :

int blocs;

if((blocs = GetNbBlocks(couleurBlocClique))> 1 )
// Clacul du score...

Je souhaiterais l´implenter de manière itérative ( j´y ai déjà réfléchit, mais cela s´avère souvent complexe face à la simplicité de la récursivité ) .

Vous avez une idée ?

cet algo t´explosera en effet ta pile
en effet, tu vérifies un bloc, mais il est IMPORTANT de l´enlever de suite, sinon, il va etre testé un nombre infini de fois.

c´est un algo de remplissage, il est plus simple en récursif, mais pas besoin d´autant de fonctions.
Consideres d´abord ton truc dans un tableau a 2 dimentions de char par exemple, qu´on appellera T, puis :

int fill(char** T, int x, int y, int c)
{
int n=1;
if ( T[x][y]!=c) return 0;
T[x][y]=0; // efface le point actuel
n+=fill(T,x-1,y,c);
n+=fill(T,x+1,y,c);
n+=fill(T,x,y-1,c);
n+=fill(T,x,y+1,c);
return n;
}

l´appel est juste :

x,y : coords a tester
c = couleur a tester ( a l´init : c = T[x][y])

nb = fill(T,x,y,x);
// nb est le nombre de cases effectivement colorées...

normalement, a moins d´abuser énorément , ça ne te fait pas péter la pile

A oui j´avais oublié d´effacer les blocs à chaques fois
Je vais lire ta réponse, merci

sinon, tu peux le faire non récursif :

1. include < queue>

typedef struct
{
int x,y,c;
} Elem;

Elem mak(Elem e,int i,int j)
{
e.x+=i;
e.y+=j;
return e;
}

int fill(char** T, int x, int y, int c)
{
Elem e;
int nb=1;
queue<Elem, list<Elem>> L;
e.x=x;e.y=y;e.c=c;
L.push(e);
while(!L.empty())
{
L.pop(e);
if ( T[e.x][e.y]!=c) continue;
T[e.x][e.y]=0;
nb++;
L.push(mak(e,1,0));
L.push(mak(e,-1,0));
L.push(mak(e,0,1));
L.push(mak(e,0,-1));
}
return nb;
}

avec le meme appel : pas de pile gérée. Tout en file. ( j´ai utilisé des STL)

• je ne garantis pas que le code marche tel quel, car je l´ai tapé ici, mais a qq fautes de frappe pres : l´algo est théoriquement bon.

Tu me propose donc une solution récursive de nouveau.
Ceci dit, il est vrai qu´en restant raisonnable, il ne devrait pas y avoir de débordements.

( la présence de mes foncions blocs left, right, etc . .. étaient également inutile ) .

Merci

ARH !
T´as posté pendant que je répondais.
Je vais lire la nouvelle.

oui, cette nouvelles solution est itérative.
mais je te conseille la récursion dans ce cas quand meme...