Newsgroup: it.comp.programmare
Titolo: Sempre su una matrice booleana.

Ho realizzato il  programma x trovare i gruppi di 1 allinterno di una
matrice booleana.
Ora vorrei sapere se ci sono degli 0 (e se si dove) allinterno di un gruppo
di 1.
Sapete darmi qualche idea??
Per ogni raggruppamento di 1 ottengo una lista del genere:
0 1 2 3 4 5 6 7 8 9.....
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   1
0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0   2
0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0   3
0 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0   4
0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0   5
0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0   6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   8
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   9
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   10
Dalla quale ottengo:
Gruppo
    |
   V
 [
0 ]--->[4,6,2]---->[4,4,3]---->[7,7,3]---->[2,5,4]---->[7,8,4]---->[2,3,5]--
-->[7,8,5]---->[3,8,6]
               AAA
     -------'  |   '----->Riga
    V           V
Inizio        Fine
Gli 0 racchiusi sono quelli in pos: (5,3),(6,3),(6,4),(4,5),(5,5),(6,5).
Non lo sarebbero ovviamente sati se fosse mancato ad es. l'1 in posizione
(6,6)
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (
http://www.grisoft.com
).
Version: 6.0.419 / Virus Database: 235 - Release Date: 13/11/02

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   10
Crei le solite liste:
2: (4, 6)
4: (4, 4), (7, 7)
5: (2, 5), (7, 8)
6: (3, 8)
Confronti le righe e identifichi i gruppi.
E' sufficiente modificare la funzione AddToGroup in modo che calcoli i
massimi e i minimi di ogni riga.
int min[num_righe];
int max[num_righe];
int ultima_riga;
AddToGroup(group, element, riga)
{
    group += element;    // aggiunge l'elemento al gruppo (in C++)
    if (element.start < min[riga])
        min[riga] = element.start;
    if (element.end > max[riga]
        max[riga] = element.end;
    ultima_riga = riga;
    for (all_hooked_elements)
    {
        AddToGroup(hooked_element, riga+1);
    }
}
Fatto questo, min e max conterranno l'inizio e la fine di ogni riga.
Ora inizia la ricerca degli zeri!
Gruppo d'esempio:
12345678
_111
100011
1001
11100011
110111
Avevo pensato a un algoritmo un po' incasinato, ma è meglio introdurre il
concetto di copertura per rendere tutto più semplice.
_Copertura_
CASO 1
A = segmento di '1'; B = segmento di '0'
Il segmento A "copre" il segmento B se:
B.start >= A.start && B.end <= A.end && abs(riga_di(B) - riga_di(A)) == 1
(cioè se sono su righe vicine)
Si dice anche che B è "coperto" da A.
CASO 2
A = segmento di '0'; B = segmento di '0'
Il segmento A "copre" il segmento B se: (come sopra)
B.start >= A.start && B.end <= A.end && abs(riga_di(B) - riga_di(A)) == 1
(cioè se sono su righe vicine)
e se
A è coperto.
Si dice anche che B è "coperto" da A.
(in parole povere, se A è coperto, pur essendo costituito di 0 e non di 1,
può coprire un segmento di zeri)
_Clipping_
dividiamo i segmenti in modo che per ogni coppia di segmenti A e B
appartenenti a righe vicine (abs(riga_di(B) - riga_di(A)) == 1):
B.start >= A.end || B.end <= A.start
Nooo!
E' incasinato anche questo da far paura...
Fammi pensare.......
000000
000
00000
0
000000
000
Fai così:
Cerca i gruppi di 0 all'interno della pseudo matrice (pseudo perchè non è
rettangolare in quanto per ogni riga conosci inizio e fine).
Questa volta gli zeri si potranno toccare soltanto in orizzontale o in
verticale (dato che gli uno si toccano anche in diagonale e quindi
"racchiudono" gli zeri).
Delimitati i gruppi, controlla se le parti che "sporgono" sono coperte
verticalmente!
000000
000
00000
0
000000
000
Nel seg. caso sono tutte coperte:
111111
000000
000111
00000
011111
000000
000111
111
Insomma si può fare, ma è un po' incasinato.
_________________
No, ti conviene usare la ricerca ricorsiva!
Che cos'è un gruppo chiuso?
E' un labirinto dove gli 1 rappresentano i muri e gli 0 la strada
percorribile.
Partendo da ogni 0 non ancora controllato, percorri la strada....se trovi
un'uscita (cioè se ti ritrovi alla riga 'riga' o 'ultima riga' oppure per in
una determinata riga X esci da min[X] o da max[X]....mi sto riferendo al
codice di prima).
_________________
MA CHE DEFICIENTE CHE SONO!!!!!!!
PERCHE' CONTROLLARE SE I SEGMENTI COPRONO ALTRI SEGMENTI!!!
CONTROLLIAMO SE NON LI COPRONO :-))))))))))))))))
Riprendiamo questo:
_111
100011
1001
11100011
110111
Rendiamo la matrice rettangolare aggiungendo dei 2 !!!
2111****
100011**
1001****
11100011
110111**
Così è facilissimo!!!
Qualsiasi segmento che interseca un usegmento di 2 (ho usato gli asterischi
perchè si vedono meglio) NON è coperto!
A questo punto sono gruppi chiusi soltanto i gruppi costituiti da segmenti
coperti :-)))
Kiuhnm
P.S. Scusami per la non linearità della mia esposizione!

Grazie mille ancora x il tuo aiuto!!
