[C] matrice connessione tra celle

[garfa]

Data una matrice

1 0 3 4 2
2 4 5 0 1
3 0 4 5 0
5 3 1 2 4
0 1 0 3 0
così i valori sono collegati

il valore 0 indica caselle annerite
come posso fare per verificare che i valori non anneriti (quelli diversi da 0) siano collegati tra di loro ( cioè non ci siano valori isolati da celle annerite)

così non sono collegati
0 1 0 2 0
5 4 2 3 1
0 5 0 4 3
2 0 4 1 0
1 2 0 5 4

i tre zeri in rosso chiudono nell'angolo il gruppo composto da 2-1-2

[garfa]

nessuno può aiutarmi!!!
forse devo usare una struttura a grafo!!!:mc:

[fracarro]

Se ho capito bene il problema potresti facilmente risolverlo usando un grafo e un algoritmo per il problema dell'albero di copertura minimo. In pratica, consideriamo la prima matrice che hai postato, quello che devi fare è creare un nodo di un grafo per ogni numero della matrice non annerito e collegare tra di loro questi nodi con i nodi dei numeri non marcati e ad esso vicini (per vicini intendo quelli sopra sotto e ai lati del numero dato ma non quelli in obliquo).

Per esempio, al numero 1 nella posizione [1,1] della tua matrice abbiamo un solo vicino che è il numero due in basso. Al numero due, nella posizione [2,1] abbiamo associato i numeri 4 (sulla destra) e 3 (in basso) e così via.

Una volta costruito questo grafo ti basta applicare un algoritmo per il calcolo dell'albero di copertura (Prim o Kruskal) e verificare che il risultato sia un albero e non una foresta (più alberi).

N.B. Gli algoritmi che ti ho indicato calcolano l'albero di copertura minimo considerando in base ad un costo che viene assegnato agli archi. Poichè nel tuo caso sei interessato solo alla "connettività" tra tutti i numeri non marcati della matrice metti ad 1 il costo di tutti gli archi e risolvi.