[C] inserire valori matrice in un grafo

[garfa]

Io ho una matrice allocata dinamicamente in cui inserisco i valori letti in input:

/* struttura per il valore della matrice */
typedef struct CELLA{
  int valore;      /* contiene il valore della cella */
  int marcatura;   /* colore che assume la cella :assume il valore 0=non si sa ancora;   1=non annerito;   2=annerito */
  int key;
  struct CELLA *next; 
}CELLA;

/*
  Alloca la memoria per una matrice di struct CELLA di dimensione n e ne restituisce
  un puntatore.
 */
CELLA** alloca_matrice(int n)
{
  CELLA **matrice;
  int i;

  /* alloco un array di n puntatori alla struttra CELLA e assegno il puntatore a una varibile matrice di tipo CELLA **  */
  if(!(matrice = (CELLA **) malloc (n * sizeof(CELLA*)))) {
 		fprintf(stderr,"Errore di allocazione per la matrice\n");
		return 0;
	}

 /* per ogni elemento matrice[i] dell'array si alloca un array di n elementi di tipo CELLA il cui indirizzo viene posto in matrice[i] */
  for(i=0; i<n; i++) {
    if(!(matrice[i] = (CELLA*) malloc (n * sizeof(CELLA)))) {
		fprintf(stderr,"Errore di allocazione per la i-esima posizione \"%d\"\n",i);
		return 0;
		}
   }
  return matrice;
}

esempio inserisco questi valori

1 1 1 2 3
5 4 2 3 1
1 5 3 4 3
2 4 4 1 4
1 2 1 5 4

se a un certo punto sò che i due 1 in rosso sarebbero anneriti
devo fare in modo di riconoscere che il 4 in blu non può essere annerito perchè devo rispettare la regola di non chiudere dei valori con celle rosse(cioè annerite), infatti l'1 verde rimarebbe chiuso

devo utilizzare un grafo con una visita in ampiezza o ci sono altri metodi???

[DanieleC88]

Potresti essere più specifico nello spiegare il problema? Non ho ben chiaro il criterio con cui annerisci o non annerisci.

[garfa]

Ti faccio un esempio per spiegarti:
questo è l'input
1 1 1 2 3
5 4 2 3 1
1 5 3 4 3
2 4 4 1 4
1 2 1 5 4
si applicano delle tecniche per verificare le 3 regole del gioco:
1) ogni numero deve comparire al più una volta per riga e colonna
2) due caselle nere possono avere al massimo un vertice in comune
3) le caselle non annerite devono formare una sola componente connessa verticalmente e orizzontalmnte

-1- = non annerito
*1* = annerito
all' inizio applico la PI che mi dice se ci sono 2 valori uguali quello in mezzo non va annerito
no (0, 1) : PI
1 -1- 1 2 3
5 4 2 3 1
1 5 3 4 3
2 4 4 1 4
1 2 1 5 4

questa mi dice che l'1 va annerito perchè c'è già un 1 non annerito(regola 1)
si (0, 0) : SB
*1* -1- 1 2 3
5 4 2 3 1
1 5 3 4 3
2 4 4 1 4
1 2 1 5 4

regola 2 le caselle nere possono essere solo in diagonale
no (1, 0) : NV
*1* -1- 1 2 3
-5- 4 2 3 1
1 5 3 4 3
2 4 4 1 4
1 2 1 5 4

di nuovo SB sull'altro 1 e cosi via
si (0, 2) : SB
*1* -1- *1* 2 3
-5- 4 2 3 1
1 5 3 4 3
2 4 4 1 4
1 2 1 5 4

no (1, 2) : NV
*1* -1- *1* 2 3
-5- 4 -2- 3 1
1 5 3 4 3
2 4 4 1 4
1 2 1 5 4

no (0, 3) : NV
*1* -1- *1* -2- 3
-5- 4 -2- 3 1
1 5 3 4 3
2 4 4 1 4
1 2 1 5 4

no (2, 3) : PI
*1* -1- *1* -2- 3
-5- 4 -2- 3 1
1 5 3 -4- 3
2 4 4 1 4
1 2 1 5 4

no (3, 3) : PI
*1* -1- *1* -2- 3
-5- 4 -2- 3 1
1 5 3 -4- 3
2 4 4 -1- 4
1 2 1 5 4

no (4, 1) : PI
*1* -1- *1* -2- 3
-5- 4 -2- 3 1
1 5 3 -4- 3
2 4 4 -1- 4
1 -2- 1 5 4

no (1, 4) : PI
*1* -1- *1* -2- 3
-5- 4 -2- 3 -1-
1 5 3 -4- 3
2 4 4 -1- 4
1 -2- 1 5 4

no (2, 1) : PI
*1* -1- *1* -2- 3
-5- 4 -2- 3 -1-
1 -5- 3 -4- 3
2 4 4 -1- 4
1 -2- 1 5 4

no (3, 0) : PI
*1* -1- *1* -2- 3
-5- 4 -2- 3 -1-
1 -5- 3 -4- 3
-2- 4 4 -1- 4
1 -2- 1 5 4

questo dice che se ci sono 2 valori uguali e un altro spaiato questo andrà annerito
si (3, 4) : CS
*1* -1- *1* -2- 3
-5- 4 -2- 3 -1-
1 -5- 3 -4- 3
-2- 4 4 -1- *4*
1 -2- 1 5 4

no (2, 4) : NV
*1* -1- *1* -2- 3
-5- 4 -2- 3 -1-
1 -5- 3 -4- -3-
-2- 4 4 -1- *4*
1 -2- 1 5 4

si (2, 2) : SB
*1* -1- *1* -2- 3
-5- 4 -2- 3 -1-
1 -5- *3* -4- -3-
-2- 4 4 -1- *4*
1 -2- 1 5 4

no (3, 2) : NV
*1* -1- *1* -2- 3
-5- 4 -2- 3 -1-
1 -5- *3* -4- -3-
-2- 4 -4- -1- *4*
1 -2- 1 5 4

si (3, 1) : SB
*1* -1- *1* -2- 3
-5- 4 -2- 3 -1-
1 -5- *3* -4- -3-
-2- *4* -4- -1- *4*
1 -2- 1 5 4

si (0, 4) : SB
*1* -1- *1* -2- *3*
-5- 4 -2- 3 -1-
1 -5- *3* -4- -3-
-2- *4* -4- -1- *4*
1 -2- 1 5 4

no (4, 4) : NV
*1* -1- *1* -2- *3*
-5- 4 -2- 3 -1-
1 -5- *3* -4- -3-
-2- *4* -4- -1- *4*
1 -2- 1 5 -4-

questo mi dice che il 5 non va annerito regola 3
no (4, 3) : A
*1* -1- *1* -2- *3*
-5- 4 -2- 3 -1-
1 -5- *3* -4- -3-
-2- *4* -4- -1- *4*
1 -2- 1 -5- -4-

[garfa]

arrivato a questo punto dovrebbe applicare la regola
[NI] Nero impossibile: cioè assumendo che la casella sia nera e applicando ricorsivamente le tecniche NV e SB si ottiene una configurazione che non rispetta le regole,allora la casella non può essere annerita.

sul numero 1 in posizione (4,2)
quello che deve fare è fare una supposizione
cioè dico la annerisco e applico ricorsivamente le altre regole e trovo una contraddizione
infatti se 1 è nero , l'1 in posizione (4,0) è bianco perchè rimarebbe chiuso il 2 (4,1) e l'1(2,0) sarebbe nero per la regola SB

devo trovare
1 il modo per sapere che (4,0) deve essere bianco
2 memorizzare il tutto in un a struttura tipo una pila per poi estrarre la marcatura giusta da dare alla cella su cui si è fatta la supposizione
Scusa ma è un po un casino da spiegare...
non è che mi dai una mano!!!

[DanieleC88]

Originariamente inviato da garfa

Scusa ma è un po un casino da spiegare...
non è che mi dai una mano!!!

Mah, oggi proprio c'ho la testa che mi fuma, non sono in grado di aiutarti.
Magari dopo me lo studio con più calma, ma spera in un utente più esperto di me...

ciao

[garfa]

Nessuno riesce ad aiutarmi!!!