#1 Le 05/08/2008, à 13:23
- rniamo
Problème d'algo [code c++][Résolu a priori]
bonjour,
je n'arrive pas à trouver un algo qui marche pour mon problème :
voici le code :
bool ZoneJeu::aLoup(int i, int j, bool **t)
{
if (i<0 || i>=nbx || j<0 || j>=nby)
return false;
bool **tab;
if (!t)
{
try
{
tab=new bool* [nbx];
for (int k=0;k<nbx;k++)
tab[k]=new bool[nby];
for(int k=0;k<nbx;k++)
for(int l=0;l<nby;l++)
tab[k][l]=false;
}
catch(bad_alloc&)
{
cout << "erreur d'alloc aloup" << endl;
}
}
else
tab=t;
if (tab[i][j])
return false;
tab[i][j]=true;
bool r=false;
if (imagesTable[i][j].getHaut()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getHaut()==ImageInfo::FORET || imagesTable[i][j].getHaut()==ImageInfo::CHASSEUR)
{
if (aLoup(i,j-1,tab))
return true;
}
if (imagesTable[i][j].getDroit()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getDroit()==ImageInfo::FORET || imagesTable[i][j].getDroit()==ImageInfo::CHASSEUR)
{
if (aLoup(i+1,j,tab))
return true;
}
if (imagesTable[i][j].getBas()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getBas()==ImageInfo::FORET || imagesTable[i][j].getBas()==ImageInfo::CHASSEUR)
{
if (aLoup(i,j+1,tab))
return true;
}
if (imagesTable[i][j].getGauche()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getGauche()==ImageInfo::FORET || imagesTable[i][j].getGauche()==ImageInfo::CHASSEUR)
r=aLoup(i-1,j,tab);
return r;
}
bool ZoneJeu::estFermeCommeIlFaut(ImageInfo::cote couleur, int i, int j, bool **t)
{
if (i<0 || i>=nbx || j<0 || j>=nby)
return true;
bool **tab;
if (!t)
{
try
{
tab=new bool* [nbx];
for (int k=0;k<nbx;k++)
tab[k]=new bool[nby];
for(int k=0;k<nbx;k++)
for(int l=0;l<nby;l++)
tab[k][l]=false;
}
catch(bad_alloc&)
{
cout << "erreur d'alloc estcommeilfaut " << endl;
}
}
else
tab=t;
if (tab[i][j])
return false;
tab[i][j]=true;
if (imagesTable[i][j].getHaut()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i,j-1,tab))
return false;
}
else if (imagesTable[i][j].getHaut()==ImageInfo::NON_DEFINI)
return false;
else if (imagesTable[i][j].getHaut()==ImageInfo::FORET && aLoup(i,j))
return false;
if (imagesTable[i][j].getBas()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i,j+1,tab))
return false;
}
else if (imagesTable[i][j].getBas()==ImageInfo::NON_DEFINI)
return false;
else if (imagesTable[i][j].getBas()==ImageInfo::FORET && aLoup(i,j))
return false;
if (imagesTable[i][j].getDroit()==couleur)
{
if (estFermeCommeIlFaut(couleur,i+1,j,tab))
return false;
}
else if (imagesTable[i][j].getDroit()==ImageInfo::NON_DEFINI)
return false;
else if (imagesTable[i][j].getDroit()==ImageInfo::FORET && aLoup(i,j))
return false;
if (imagesTable[i][j].getGauche()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i-1,j,tab))
return false;
}
else if (imagesTable[i][j].getGauche()==ImageInfo::NON_DEFINI)
return false;
else if (imagesTable[i][j].getGauche()==ImageInfo::FORET && aLoup(i,j))
return false;
return true;
}Le problème : j'ai un damier avec des pions (imagesTable[][]) qui ont 4 cotés et chacun des coté a une couleur (noir, jaune, rouge, bleu, loup, village, chasseur, foret).
Je veux savoir si mes couleurs sont regroupés entre elle (il éxiste un chemin qui permet de passer d'une cases à l'autre sans "sauter" par dessus une autre couleur) et si il n'y a pas un loup dans une foret qui touche mes couleurs (exemple : un loup à coté d'une case bleu/foret/foret/foret).
Je sais que c'est un peu confus mais vous pouvez tester une pré-version ici : http://rniamo.olympe-network.com/lgdm_site/
Dernière modification par rniamo (Le 06/08/2008, à 13:44)
< Quelques un des mes programmes | Cuisine Facile (pour les gourmands) | Fast MVC for PHP >
\ ^__^
\ (o o)\_______
(___)\ )\
Hors ligne
#2 Le 05/08/2008, à 18:03
- LarTicK
Re : Problème d'algo [code c++][Résolu a priori]
Bonjour,
Je ne suis pas sur d'avoir compris exactement ton problème, ni le code que tu donnes mais un algorithme de parcours de graphe est ce qui me parrait le plus approprié : http://fr.wikipedia.org/wiki/Parcours_(graphe)
parcours en largeur ou en profondeur peu importe, le résultat est le même.
Tes pions correspondent aux sommets, et la transition entre 2 cases est une arête qui relie les 2 sommets. A chaque case, avant de continuer le parcours, tu vérifies si toutes les transitions de cette case sont cohérentes et tu parcours seulement les arêtes qui t'interesses : d'après ce que je comprend, tu n'aurais pas envie de continuer au delà d'une barrière d'enclos.
En espérant que ça puisse t'aider. 
Hors ligne
#3 Le 06/08/2008, à 13:39
- rniamo
Re : Problème d'algo [code c++][Résolu a priori]
à moins que je n'ai pas compris je ne pense pas que ça aille puisqu'il faut prendre en compte les arrêtes et pas les sommets ... mais ça a aidé ma réflexion, merci.
De plus le prcours n'est ni en largeur ni en profondeur, il n'est pas "dans un sens".
Je crois que j'ai un bout de code correcte (à vérifier).
bool ZoneJeu::aLoup(int i, int j, bool **t)
{
if (i<0 || i>=nbx || j<0 || j>=nby)
return false;
bool **tab=NULL;
if (!t)
{
try
{
tab=new bool* [nbx];
for (int k=0;k<nbx;k++)
tab[k]=new bool[nby];
for(int k=0;k<nbx;k++)
for(int l=0;l<nby;l++)
tab[k][l]=false;
}
catch(bad_alloc&)
{
cout << "erreur d'alloc aloup" << endl;
}
}
else
tab=t;
if (tab[i][j])
return false;
tab[i][j]=true;
bool r=false;
if (imagesTable[i][j].getHaut()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getHaut()==ImageInfo::FORET || imagesTable[i][j].getHaut()==ImageInfo::CHASSEUR)
{
if (aLoup(i,j-1,tab))
return true;
}
if (imagesTable[i][j].getDroit()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getDroit()==ImageInfo::FORET || imagesTable[i][j].getDroit()==ImageInfo::CHASSEUR)
{
if (aLoup(i+1,j,tab))
return true;
}
if (imagesTable[i][j].getBas()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getBas()==ImageInfo::FORET || imagesTable[i][j].getBas()==ImageInfo::CHASSEUR)
{
if (aLoup(i,j+1,tab))
return true;
}
if (imagesTable[i][j].getGauche()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getGauche()==ImageInfo::FORET || imagesTable[i][j].getGauche()==ImageInfo::CHASSEUR)
r=aLoup(i-1,j,tab);
return r;
}
bool ZoneJeu::estFermeCommeIlFaut(ImageInfo::cote couleur, int i, int j, bool **t)
{
if (i<0 || i>=nbx || j<0 || j>=nby)
return true;
bool **tab=NULL;
if (!t)
{
try
{
tab=new bool* [nbx];
for (int k=0;k<nbx;k++)
tab[k]=new bool[nby];
for(int k=0;k<nbx;k++)
for(int l=0;l<nby;l++)
tab[k][l]=false;
}
catch(bad_alloc&)
{
cout << "erreur d'alloc estcommeilfaut " << endl;
}
}
else
tab=t;
if (tab[i][j])
return true;
tab[i][j]=true;
if (imagesTable[i][j].estNonDefinie())
return false;
if (imagesTable[i][j].getHaut()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i,j-1,tab))
return false;
}
else if (imagesTable[i][j].getHaut()==ImageInfo::FORET)
{
if (aLoup(i,j))
return false;
}
if (imagesTable[i][j].getBas()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i,j+1,tab))
return false;
}
else if (imagesTable[i][j].getBas()==ImageInfo::FORET)
{
if (aLoup(i,j))
return false;
}
if (imagesTable[i][j].getDroit()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i+1,j,tab))
return false;
}
else if (imagesTable[i][j].getDroit()==ImageInfo::FORET)
{
if (aLoup(i,j))
return false;
}
if (imagesTable[i][j].getGauche()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i-1,j,tab))
return false;
}
else if (imagesTable[i][j].getGauche()==ImageInfo::FORET)
{
if (aLoup(i,j))
return false;
}
return true;
}ps : les indentation foireuse c'est du codeblocks 
< Quelques un des mes programmes | Cuisine Facile (pour les gourmands) | Fast MVC for PHP >
\ ^__^
\ (o o)\_______
(___)\ )\
Hors ligne
#4 Le 06/08/2008, à 13:39
- rniamo
Re : Problème d'algo [code c++][Résolu a priori]
à moins que je n'ai pas compris je ne pense pas que ça aille puisqu'il faut prendre en compte les arrêtes et pas les sommets ... mais ça a aidé ma réflexion, merci.
De plus le prcours n'est ni en largeur ni en profondeur, il n'est pas "dans un sens".
Je crois que j'ai un bout de code correcte (à vérifier).
bool ZoneJeu::aLoup(int i, int j, bool **t)
{
if (i<0 || i>=nbx || j<0 || j>=nby)
return false;
bool **tab=NULL;
if (!t)
{
try
{
tab=new bool* [nbx];
for (int k=0;k<nbx;k++)
tab[k]=new bool[nby];
for(int k=0;k<nbx;k++)
for(int l=0;l<nby;l++)
tab[k][l]=false;
}
catch(bad_alloc&)
{
cout << "erreur d'alloc aloup" << endl;
}
}
else
tab=t;
if (tab[i][j])
return false;
tab[i][j]=true;
bool r=false;
if (imagesTable[i][j].getHaut()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getHaut()==ImageInfo::FORET || imagesTable[i][j].getHaut()==ImageInfo::CHASSEUR)
{
if (aLoup(i,j-1,tab))
return true;
}
if (imagesTable[i][j].getDroit()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getDroit()==ImageInfo::FORET || imagesTable[i][j].getDroit()==ImageInfo::CHASSEUR)
{
if (aLoup(i+1,j,tab))
return true;
}
if (imagesTable[i][j].getBas()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getBas()==ImageInfo::FORET || imagesTable[i][j].getBas()==ImageInfo::CHASSEUR)
{
if (aLoup(i,j+1,tab))
return true;
}
if (imagesTable[i][j].getGauche()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getGauche()==ImageInfo::FORET || imagesTable[i][j].getGauche()==ImageInfo::CHASSEUR)
r=aLoup(i-1,j,tab);
return r;
}
bool ZoneJeu::estFermeCommeIlFaut(ImageInfo::cote couleur, int i, int j, bool **t)
{
if (i<0 || i>=nbx || j<0 || j>=nby)
return true;
bool **tab=NULL;
if (!t)
{
try
{
tab=new bool* [nbx];
for (int k=0;k<nbx;k++)
tab[k]=new bool[nby];
for(int k=0;k<nbx;k++)
for(int l=0;l<nby;l++)
tab[k][l]=false;
}
catch(bad_alloc&)
{
cout << "erreur d'alloc estcommeilfaut " << endl;
}
}
else
tab=t;
if (tab[i][j])
return true;
tab[i][j]=true;
if (imagesTable[i][j].estNonDefinie())
return false;
if (imagesTable[i][j].getHaut()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i,j-1,tab))
return false;
}
else if (imagesTable[i][j].getHaut()==ImageInfo::FORET)
{
if (aLoup(i,j))
return false;
}
if (imagesTable[i][j].getBas()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i,j+1,tab))
return false;
}
else if (imagesTable[i][j].getBas()==ImageInfo::FORET)
{
if (aLoup(i,j))
return false;
}
if (imagesTable[i][j].getDroit()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i+1,j,tab))
return false;
}
else if (imagesTable[i][j].getDroit()==ImageInfo::FORET)
{
if (aLoup(i,j))
return false;
}
if (imagesTable[i][j].getGauche()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i-1,j,tab))
return false;
}
else if (imagesTable[i][j].getGauche()==ImageInfo::FORET)
{
if (aLoup(i,j))
return false;
}
return true;
}ps : les indentation foireuse c'est du codeblocks
< Quelques un des mes programmes | Cuisine Facile (pour les gourmands) | Fast MVC for PHP >
\ ^__^
\ (o o)\_______
(___)\ )\
Hors ligne
#5 Le 06/08/2008, à 13:42
- rniamo
Re : Problème d'algo [code c++][Résolu a priori]
à moins que je n'ai pas compris je ne pense pas que ça aille puisqu'il faut prendre en compte les arrêtes et pas les sommets ... mais ça a aidé ma réflexion, merci.
De plus le prcours n'est ni en largeur ni en profondeur, il n'est pas "dans un sens".
Je crois que j'ai un bout de code correcte (à vérifier).
bool ZoneJeu::aLoup(int i, int j, bool **t)
{
if (i<0 || i>=nbx || j<0 || j>=nby)
return false;
bool **tab=NULL;
if (!t)
{
try
{
tab=new bool* [nbx];
for (int k=0;k<nbx;k++)
tab[k]=new bool[nby];
for(int k=0;k<nbx;k++)
for(int l=0;l<nby;l++)
tab[k][l]=false;
}
catch(bad_alloc&)
{
cout << "erreur d'alloc aloup" << endl;
}
}
else
tab=t;
if (tab[i][j])
return false;
tab[i][j]=true;
bool r=false;
if (imagesTable[i][j].getHaut()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getHaut()==ImageInfo::FORET || imagesTable[i][j].getHaut()==ImageInfo::CHASSEUR)
{
if (aLoup(i,j-1,tab))
return true;
}
if (imagesTable[i][j].getDroit()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getDroit()==ImageInfo::FORET || imagesTable[i][j].getDroit()==ImageInfo::CHASSEUR)
{
if (aLoup(i+1,j,tab))
return true;
}
if (imagesTable[i][j].getBas()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getBas()==ImageInfo::FORET || imagesTable[i][j].getBas()==ImageInfo::CHASSEUR)
{
if (aLoup(i,j+1,tab))
return true;
}
if (imagesTable[i][j].getGauche()==ImageInfo::LOUP)
return true;
else if (imagesTable[i][j].getGauche()==ImageInfo::FORET || imagesTable[i][j].getGauche()==ImageInfo::CHASSEUR)
r=aLoup(i-1,j,tab);
return r;
}
bool ZoneJeu::estFermeCommeIlFaut(ImageInfo::cote couleur, int i, int j, bool **t)
{
if (i<0 || i>=nbx || j<0 || j>=nby)
return true;
bool **tab=NULL;
if (!t)
{
try
{
tab=new bool* [nbx];
for (int k=0;k<nbx;k++)
tab[k]=new bool[nby];
for(int k=0;k<nbx;k++)
for(int l=0;l<nby;l++)
tab[k][l]=false;
}
catch(bad_alloc&)
{
cout << "erreur d'alloc estcommeilfaut " << endl;
}
}
else
tab=t;
if (tab[i][j])
return true;
tab[i][j]=true;
if (imagesTable[i][j].estNonDefinie())
return false;
if (imagesTable[i][j].getHaut()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i,j-1,tab))
return false;
}
else if (imagesTable[i][j].getHaut()==ImageInfo::FORET)
{
if (aLoup(i,j))
return false;
}
if (imagesTable[i][j].getBas()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i,j+1,tab))
return false;
}
else if (imagesTable[i][j].getBas()==ImageInfo::FORET)
{
if (aLoup(i,j))
return false;
}
if (imagesTable[i][j].getDroit()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i+1,j,tab))
return false;
}
else if (imagesTable[i][j].getDroit()==ImageInfo::FORET)
{
if (aLoup(i,j))
return false;
}
if (imagesTable[i][j].getGauche()==couleur)
{
if (!estFermeCommeIlFaut(couleur,i-1,j,tab))
return false;
}
else if (imagesTable[i][j].getGauche()==ImageInfo::FORET)
{
if (aLoup(i,j))
return false;
}
return true;
}ps : les indentation foireuse c'est du codeblocks
< Quelques un des mes programmes | Cuisine Facile (pour les gourmands) | Fast MVC for PHP >
\ ^__^
\ (o o)\_______
(___)\ )\
Hors ligne
#6 Le 07/08/2008, à 09:05
- LarTicK
Re : Problème d'algo [code c++][Résolu a priori]
Pour moi, l'idée était d'identifier ton plateau à un graphe. Un damier peut se voir aussi comme un graphe où chaque case est un sommet qui est relié à ses 4 cases voisines par une arête. A partir de là tu peux appliquer tous les algos disponibles pour les graphes à ton problème. Dans ton cas, il faut prendre en compte une info supplémentaire, c'est qu'il faut que tes arêtes soient "bien formées" (les cotés qui se touchent doivent être compatibles), mais selon moi c'est juste un test et ça ne change pas fondamentalement l'algo.
Le but du parcours de graphe est de visiter tous les sommets du graphe et de ne les visiter qu'une fois. Le parcours en largeur ou en profondeur n'a pas de rapport avec l'orientation du graphe, c'est juste l'ordre dans lequel tu parcours tes voisins :
En largeur tu pars d'un sommet et tu parcours d'abord les voisins immédiats, puis les voisins à une distance 2, puis les voisins à une distance 3, etc.
En profondeur tu prends un voisin et tu parcours tous ses voisins avant de faire la même chose pour le second voisin et ainsi de suite. C'est ce que tu fais dans ton code.
Hors ligne
#7 Le 07/08/2008, à 15:40
- rniamo
Re : Problème d'algo [code c++][Résolu a priori]
oui, c'est vrai, je n'avais pas compris ta modélisation (peut être lu trop vite :\).
Merci.
< Quelques un des mes programmes | Cuisine Facile (pour les gourmands) | Fast MVC for PHP >
\ ^__^
\ (o o)\_______
(___)\ )\
Hors ligne