[java] Ricerca elementi in matrice

[franksisca]

[0 1 2 3 4]
 1 0 0 0 0 [0]
 0 0 0 0 0 [1]
 0 1 1 1 0 [2]
 0 0 1 0 0 [3]
 0 0 0 0 0 [4]

come faccio a capire (e credetemi che ci sto sbattendo) che l'elemento [0][0] ha 1 elemento a 1 nel suo intorno (se stesso), [2][3] ne ha 4 e (ad esempio) [3][3] ne ha 0???

mi aiutate per favore....

[Don[ITA]]

Beh non dovrebbe essere difficile...credo
Ogni elemento ha coordinate (x,y), il suo intorno non ha infiniti punti ma al massimo 8 punti di cui conosci le coordinate:
(x-1,y-1),(x,y-1),(x,y+1)
(x-1,y),(x,y [l'elemento in questione]), (x+1,y)
(x-1,y+1)(x,y+1)(x+1,y+1)
Cerchi gli elementi aventi queste coordinate, facendo ovviamente attenzione nel caso in cui ti trovi sul perimetro della matrice .
Forse qualcosa del genere dovrebbe andare:

per ogni elemento E della matrice
    se(E == 1)
        int x1 = (x(E)-1 >= 0) ? x(E) -1 : 0;
        int x2 = (x(E)+1 <= x(max)) ? x(E)+1 : x(E);
        int y1 = (y(E)-1 >= 0) ? y(E) -1 : 0;
        int y2 = (y(E)+1 <= y(max)) ? y(E)+1 : y(E);
        for(int x = x1; x < x2; x++)
            for(int y = y1; y < y2; y++)
                se(elemento(x,y) == 1)
                    intorno(E)++;

Ovviamente questo è uno pseudocodice inventato al momento, sicuramente non ottimizzato, ma credo funzionante
(questa roba qui "int x1 = (x(E)-1 >= 0) ? x(E) -1 : 0;" vuol dire "se x di E meno uno è maggiore o uguale a zero allora x1 = x di E meno 1, altrimento x1 = 0)

Saluti

[goldorak]

Originariamente inviato da franksisca

[0 1 2 3 4]
 1 0 0 0 0 [0]
 0 0 0 0 0 [1]
 0 1 1 1 0 [2]
 0 0 1 0 0 [3]
 0 0 0 0 0 [4]

come faccio a capire (e credetemi che ci sto sbattendo) che l'elemento [0][0] ha 1 elemento a 1 nel suo intorno (se stesso), [2][3] ne ha 4 e (ad esempio) [3][3] ne ha 0???

mi aiutate per favore....

Per esempio nel tuo caso devi gestire una matrice A 5x5, allora se vuoi evitare i controlli specifici sul perimetro introduci una matrice B 7x7 con delle sentinelle sul perimetro.

[0 1 2 3 4 5 6]
x x x x x x x [0]
x 1 0 0 0 0 x [1]
x 0 0 0 0 0 x [2]
x 0 1 1 1 0 x [3]
x 0 0 1 0 0 x [4]
x 0 0 0 0 0 x [5]
x x x x x x x [6]

x e' un valore sentinella, in questo caso non ci sono problemi a prenderlo uguale a zero, perche' semplifica i calcoli.

 for i = 1 to 5
  for j = 1 to 5
   C[i,j] = B[i-i,j-1]+B[i-1,j]+B[i-1,j+1]+B[i,j-1]+B[i,j]+
                B[i,j+1]+B[i+1,j-1]+B[i+1,j]+B[i+1,j+1]

C[i,j] conterra' il numero di 1 adiacenti alla posizione i,j nella matrice originale B.

[franksisca]

il fatto è che posso andare solo in 4 direzioni e deve esse "ricorsivo"......ad esempio:

0 0 0 0 0 0 0 0
0 1 1 0 1 0 0 0
1 1 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

l'elemento [1][1] ad esempio ha 5 1 vicini!!!

capito deve essere "ricorsivo"...

[franksisca]

in pratica mi deve riconoscere i percorsi di 1 presenti nella matrice....na specie di battaglia navale (che non c'entra niente)

0 0 0 0 0 0 0 0
0 1 1 0 1 0 0 0
1 1 0 0 0 1 1 0
0 1 0 0 0 0 0 0
0 0 1 1 1 0 0 0
0 0 1 0 1 0 0 0
0 0 1 0 1 0 0 0
0 0 1 1 1 0 0 0

ad esempiio in quella sopra se scelgo [1][1] mi dice 5, se scelgo [1][4] mi dice 1, se scelgo [7][3] mi dice 10.

sono stato chiaro?

[goldorak]

No, tu hai detto voglio sapere come calcolare i numero di 1 adiacenti ad un certa posizione x,y.
Se supponi che la matrice B possa contenere solo 0 ed 1 come valori, l'algoritmo te l'ho gia' dato io.
Se devi considerare solo i 4 valori adiacenti piu' quello originale basta calcolare cosi'
C[x,y] = B[x-1,y]+B[x+1,y]+B[x,y-1]+B[x,y+1]+B[x,y]

C e' una matrice ausiliaria che ti dice per ogni posizione x,y nella matrice originale B, quanti 1 sono nelle case adiacenti alla posizione x,y.

[franksisca]

Originariamente inviato da goldorak

No, tu hai detto voglio sapere come calcolare i numero di 1 adiacenti ad un certa posizione x,y.
Se supponi che la matrice B possa contenere solo 0 ed 1 come valori, l'algoritmo te l'ho gia' dato io.
Se devi considerare solo i 4 valori adiacenti piu' quello originale basta calcolare cosi'
C[x,y] = B[x-1,y]+B[x+1,y]+B[x,y-1]+B[x,y+1]+B[x,y]

C e' una matrice ausiliaria che ti dice per ogni posizione x,y nella matrice originale B, quanti 1 sono nelle case adiacenti alla posizione x,y.

non mi interessano solo gli adiacenti, ma gli 1 che formano un percorso neelle 4 direzioni "standard" (no diagonali)

0 0 0 0 0 0 0 0
0 1 1 0 1 0 0 0
1 1 0 0 0 1 1 0
0 1 0 0 0 0 0 0
0 0 1 1 1 0 0 0
0 0 1 0 1 0 0 0
0 0 1 0 1 0 0 0
0 0 1 1 1*0 0 0

ad esempio l'1* restituirebbe 10 perchè ha 9 numeri 1 (oltre a se) con i quali forma un percorso...

[gugoXX]

Quello che chiedi in questo ultimo intervento e' diverso da quello che chiedevi all'inizio, per il quale la risposta data
goldorak e Don sono sufficienti.

Comunque, per il tuo nuovo problema, con un algoritmo di flood-fill ce la si dovrebbe fare senza troppi problemi.
Per implementare un flood-fill in modo molto semplice ti basta uno Stack, e una struttura di supporto tipo HashTable, se non puoi cambiare (o non vuoi cambiare) il tuo dato originale.

Mi spiego con il solo Stack, che e' la piu' semplice.
Si inizia inserendo il punto nello stack.
E poi si comincia con un ciclo, dal quale si usicra' solo se non ci sono piu' elementi nello stack.
Si Scoda un punto dallo stack, si guarda se l'elemento della matrice e' a 1.
se e' ad uno, lo colora, (lo mette p.es. a 2). Inserisce nello stack tutti e 4 i punti vicini (o meno se siamo vicino ad un bordo).
Si continua, come detto, fino a che ci sono punti nello stack.

Quando non ci sono piu' punti nello stack, contiamo quanti punti abbiamo ora a 2 (colorati), li rimettiamo ad 1 e restitutiamo il dato.


Nella versione ad HashTable, ovvero quando non si puo'/deve cambiare la matrice originale, e' sufficiente memorizzare i punti colorati, e tenere conto del suo contenuto per sapere se un punto e' gia' stato o meno colorato, e quindi quando non lo si deve ricolorare.

[banryu79]

gugoXX: interessante il flood fill.
Allego banale link per fransiska, di wikipedia (english)

[franksisca]

Originariamente inviato da gugoXX

Quello che chiedi in questo ultimo intervento e' diverso da quello che chiedevi all'inizio, per il quale la risposta data
goldorak e Don sono sufficienti.

Comunque, per il tuo nuovo problema, con un algoritmo di flood-fill ce la si dovrebbe fare senza troppi problemi.
Per implementare un flood-fill in modo molto semplice ti basta uno Stack, e una struttura di supporto tipo HashTable, se non puoi cambiare (o non vuoi cambiare) il tuo dato originale.

Mi spiego con il solo Stack, che e' la piu' semplice.
Si inizia inserendo il punto nello stack.
E poi si comincia con un ciclo, dal quale si usicra' solo se non ci sono piu' elementi nello stack.
Si Scoda un punto dallo stack, si guarda se l'elemento della matrice e' a 1.
se e' ad uno, lo colora, (lo mette p.es. a 2). Inserisce nello stack tutti e 4 i punti vicini (o meno se siamo vicino ad un bordo).
Si continua, come detto, fino a che ci sono punti nello stack.

Quando non ci sono piu' punti nello stack, contiamo quanti punti abbiamo ora a 2 (colorati), li rimettiamo ad 1 e restitutiamo il dato.


Nella versione ad HashTable, ovvero quando non si puo'/deve cambiare la matrice originale, e' sufficiente memorizzare i punti colorati, e tenere conto del suo contenuto per sapere se un punto e' gia' stato o meno colorato, e quindi quando non lo si deve ricolorare.

infatti poi ho aggiunto dettagli, perchè capivo che non si capiva

Originariamente inviato da banryu79

gugoXX: interessante il flood fill.
Allego banale link per fransiska, di wikipedia (english)

grazie