[Algo]Cases voisines

[atra27]

Bonjour,
C'est un petit probléme assez ardu je trouve.

J'ai donc un tableau de n par n cases représenté sous la forme d'un array[x][y]

Les cases on 3 etats:
0: Vide
1: Blanc
2: Noir

Il me faudrait un algo qui me retourne toutes les cases qui sont totalement entourées par des cases de l'autre couleur.
Un exemple simple:

La donc l'algo doit me retourner les coordonnée de la boule noire.

Maintenant il y as un petit hic:


La, les deux boules noires sont entourées, DONC, l'algo doit me retourner les coord de ces deux boules.

Enfaite, les coordonnées d'une pièce ne doivent t'être renvoyées que si les 4 cotés de cette pièce sont occupées par des pions de l'autre couleur OU que les pièces de même couleur connectées ne sont elles aussi entourées de pions de l'autre couleur.

Une idée? :$

[php_addict]

et bein...

pour chaque case tu teste les cases voisines un foreach en php par exemple

si le test des cases voisines de la case en cours est concluant tu balance le resultat dans un tableau resultat genre $resulat = array();

ex: $resulat[10][25] ( $resulat[x][y] )


non ?

[Ter Rowan]

ton système revient à dire vrai si il existe au moins une place vide parmi les voisins de la meme couleur que la bille sélectionnée

on est d'accord ?

[atra27]

ton système revient à dire vrai si il existe au moins une place vide parmi les voisins de la meme couleur que la bille sélectionnée

on est d'accord ?

On est d'accord

Reste la réalisation, j'avais pensé a etablir des groupes en parcourant le tableau, puis a calculer le nb de cases vides autour de chaque groupe.

Enfaite je laisse libre la façon de faire tournerla fonction, ici j'ai cité un exemple ou elle retourne les coordonnées des points concernés mais on peut en faire une qui renvoie vrai ou faux suivant les coordonnées du point passé en paramétre.

Enfaite la forme m'importe peu, je veux juste la maniére de proceder pour...

Mais sinon Ter Rowan tu est dans le vrai!

Par contre php_addict, ta solution est simple, mais ne tiens pas en compte l'effet des deux cases ensemble! Il marcherai uniquement pour 1 seule case entourée.

[Ter Rowan]

je réfléchis en meme temps mais est ce que les couleurs de boules peuvent changer (genre à la reversi) ou est ce qu'un croisement est blanc il le reste à jamais ?

[niahoo]

l'idée de ter rowan est très bonne.
3 tableaux: Liste_boules, Open, Closed

1) tu récup toutes les boules noires dans liste_boules

2) tu prends une boule noire dans Liste_boules tu la places dans Open
3) tu prends la premiere boule de Open
si elle a une case voisine vide, tu vides Open, les boules qui y sont ne sont pas entourées
sinon, si elle a des voisines noires dans Liste_boules, tu les déplaces dans open
sinon, si aucune boule de ta liste Open ne trouve de voisine qui ne soit pas déjà dans Open, toute ta liste Open est une groupe entouré => tu les places dans Closed pour choper les coordonnées plus tard, et tu reprends au 3)
sinon, tu reprends au 3)


bon voilà, c'est surement pas exactement ça mais tu comprends l'idée.

[atra27]

je réfléchis en meme temps mais est ce que les couleurs de boules peuvent changer (genre à la reversi) ou est ce qu'un croisement est blanc il le reste à jamais ?

Quel rapport? si le croisement change de couleur je change le 1 en 2 ou inversement. L'algo me retourne la situation au moment ou on execute donc je vois pas en quoi les changements possibles de couleurs peuvent changer la donne.


Niahoo:
Pas compris le 3éme point :$

[niahoo]

ben le 3eme point c'est l'algo en lui-même donc il va te falloir y réfléchir d'avantage :p

[Ter Rowan]

je réfléchis en meme temps mais est ce que les couleurs de boules peuvent changer (genre à la reversi) ou est ce qu'un croisement est blanc il le reste à jamais ?

Quel rapport? si le croisement change de couleur je change le 1 en 2 ou inversement. L'algo me retourne la situation au moment ou on execute donc je vois pas en quoi les changements possibles de couleurs peuvent changer la donne.


Niahoo:
Pas compris le 3éme point :$

le rapport concerne les changements d'états pour optimiser les calculs

Soit on fait un algo qui recalcule tout tout le temps (par exemple la proposition de niahoo).

Soit on fait un algo qui s'appuie sur l'historique (si une bille est dans l'état "entouré par les autres", elle l'est pour toujours)

[nicodd]

C'est assez facile a faire en exploitant la récursivité, en partant d'une bille une fonction parcourt les 4 voisins de cette bille.
4 possibilités :
Le voisin est une case vide => false;
Le voisin est une bille de la couleur opposée => true;
Le voisin est en dehors de la zone => true; (pour gérer les bords)
Le voisin est un bille de la même couleur => tu relance ta fonction récursive, et tu considère le résultat qu'elle te renvoie.
Ta fonction renvoie le ET des résultats pour les 4 voisines.
Si c'est true, elle réponds bien à tes conditions, si c'est false ce n'est pas le cas.
Si tu veux toutes les billes qui répondent aux conditions, il faut en plus marquer les billes de même couleur qui ont été explorées.

Si tu veux un exemple d'implémentation, donne un exemple exploitable de données.