Come procede?
Ho avuto tempo di fare un implementazione e sembra funzionare abbastanza bene.
Questa è la parte centrale:
Codice:
public static ArrayList<Point> contigui(int x, int y, HashSet<Point> viewed) {
ArrayList<Point> vicini = new ArrayList();
boolean quit = true;
for (int i=-1; i<=1; i++) {
int a = x+i; // coordinata X1 del vicino
if (a>=0 && a<mat.length) {
for (int j=-1; j<=1; j++) {
int b = y+j; // cordinata Y1 del vicino
if (b>=0 && b<mat[0].length && mat[a][b]==1) {
Point v = new Point(a, b);
if (!viewed.contains(v)) {
vicini.add(v);
if (viewed.add(v)) {
quit = false;
}
}
}
}
}
}
if (!quit) {
for (int k=0; k<vicini.size(); k++) {
Point p = vicini.get(k);
vicini.addAll(contigui(p.x, p.y, viewed));
}
}
return vicini;
}
Tramite questa funzione sostanzialmente trovo tutti gli 1 contigui alla posizione X,Y.
In pratica:
- mi trovo tutti i vicini di (X,Y)
- per ognuno di essi, chiamiamoli (Xv, Yv) mi calcolo la funzione contigui(Xv, Yv).
La ricorsione termina quando non aggiungo più nuovi vicini.
Una piccola nota su come genero i vicini del generico punto P(X,Y):
a) Definiamo vicino V di coordinate (A,B) l'elemento da cui P dista 1.
b) Definiamo Delta la varazione di una singola coordinata (es. X+1, delta X = 1).
Ora appare abbastanza evidente che i possibili Delta sulle coordinate saranno [-1, 1].
Per cui con quei due cicli for mi genero tutti i delta calcolandomi le coordinate del vicino V(A,B):
A=X+I
B=Y+J
con I,J nell'intervallo [-1, 1].
Notare che includo anche lo 0 per poter fissare una data riga o una data colonna ed includere tutti i possibili elementi vicini.
Ovviamente le coordinate generate con questo sistema devono essere valide (devono ricadere all'interno della matrice), per questo noterete un po' di if atti a fare i dovuti controlli.
Alla lista aggiungo solo quelli marcati con un 1, ovvero del colore che mi interessa.
Poi il gioco prosegue facilmente chiamando la funzione contigua(X,Y) su ogni elemento della matrice, appena ho un altro po' di tempo vedo se c'è qualche trucco per ottimizzare il tutto (penso ci si possa ragionare su).