Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Ciao a tutti ho un problema con questo progetto.
Inizio con spiegarvi cosa devo fare:
Bisogna costruire un "mosaico" su un pavimento XxY (n° dispari) delimitato da "pareti". Ogni pezzo,contenuto in una scatola, del mosaico ha 4 bordi (preticamente un quadrato: lato nord,sud,ovest ed est) dentati che vanno posizionati sul pavimento in questo ordine:
1)Prima il primo pezzo della scatola
2)Pezzo con il < mismatch con i pezzi già presenti nel mosaico
Per mismatch si intende:
Avendo due pezzi A e B con 3 denti per lato:
+1 +3 -3 +5 -2 +3
+3 +9 +1 +1
-2 A +2 +3 B 0
+3 -1 -1 +3
+1 0 0 +3 -5 -4
E ponendo che A sia già posizionato nel mosaico, allora B sarà posizoinato secondo questa formula: (N=nord, S=sud, O=ovest, E=est)
(NA1+SB1)^2+(NA2+SB2)^2+(NA3+SB3)^2
Cioè nel nostro caso:
- A Nord B Sud: (+1 + +3)^2+ (+3 + -5)^2+ (-3 + -4)^2 = 46
- A Est B Ovest: (+9 + +1)^2+ (+2 + +3)^2+ (-1 + -1)^2 = 129
- A Ovest B Est: (+3 + +1)^2+ (-2 + 0)^2+ (+3 + +3)^2 = 56
- A Sud B Nord: (+1 + +5)^2+ (0 + -5)^2+ (0 + -4)^2 = 77
Quindi posizioniamo B a nord di A inquanto il mismatch è 46.
Dopo aver posto un tassello, si controlla se il pavimento presenta delle zone completamente delimitate da tasselli già incollati: queste zone vengono subito riempite con la malta a presa rapida. Per "zona completamente delimitata" si intende un qualunque sottoinsieme di caselle vuote ciascuna delle quali sia
adiacente lato a lato solo ad altre caselle di questo sottoinsieme oppure a tasselli già incollati (ma non alle pareti che delimitano la stanza). La malta viene versata nella zona (o le zone) fino a riempirla, dopodichè si indurisce. Le caselle piene di malta indurita non possono più accogliere alcun tassello.
Allora io ho pensato di fare così:
Codice sorgente - presumibilmente C++
int righe =9;
int colonne =7;
int mosaico[righe][colonne];// righe x; colonne y;
int n_tasseli =8;
int n_denti =4;
typedefstruct tassello
{
int nord[n_denti];
int est[n_denti];
int sud[n_denti];
int ovest[n_denti];
} TASSELLO;
TASSELLO scatola[n_tasseli];
for(i=0;i<n_tasseli;i++){
for(j=0;j<n_denti;j++){
scatola[i].nord[j]=10;
scatola[i].est[j]=1;
scatola[i].sud[j]=3;
scatola[i].ovest[j]=0;
E così creo il "mosaico" e lo riempio di "tasselli".
Il centro lo calcolo così:
Ora inserito il primo tassello vanno inseriti gli altri secondo il mismatch
Per tenere traccia dei tasselli inseriti e quindi non scorrere tutto l'array bidimensionale creo una lista con inserimento in testa dove salvo i tasselli inseriti, e cancello solo se hanno tutti i bordi (nord,sud,ovest,est) cirocndati da tasselli.
Codice sorgente - presumibilmente C++
struct list_el {
int x;// righe
int y;/ colonne
struct list_el * next;
};
typedefstruct list_el item;
//nel main
item *curr, *head;
head =NULL;
//quando inserisco un pezzo
curr =(item *)malloc(sizeof(item));
curr->x =2;
curr->y =2;
curr->next = head;
head = curr;
//per leggerlo
curr = head;
while(curr){
printf("%d,%d\n", curr->x,curr->y);
curr = curr->next ;
}
Ancoro non l'ho fatto ma teoricamente basta leggere la lista e i bordi dei tasselli presenti e applicare la formula per il mismatch con ogni tassello nella scatola.
----------------------------------------------------------------------------------
Ora inizia il mio problema:
Come fare a determinare dove mettere la malta?
L'area da considerare deve essere delimitata da tasselli e non deve comprendere i bordi.
Allora io ho pensato di "nominare" le "caselle" dell'array bidimensionale in questo modo:
# b=bordo eventualmente bn(bordo neutro) bp e bc
# n=neutra
# p=pezzo
# c=confine
In modo da ottenere: con un pavimento da 5x5 con pezzo in centro
b b b b b
b n c n b
b c p c b
b n c n b
b b b b b
Però non mi viene in mente niente per poter determinare se è presente un'area chiusa da riempire con malta.
Per esempio se ho:
b b b b b b b b b b b b b b b b b b
b n n n n p p p b b p p p p p p p b
b n n n n p p b b p p p b
b n n n p p p b b p p p p p p p b
b n n n p p b oppure b n n p p b
b p p p p p p b b n n p p b
b p p n b b n n p p b
b p p p p p p n b b n n p p p p p b
b b b b b b b b b b b b b b b b b b
Il vuoto rappresenta la malta.
Cosa posso fare?
Secondo voi devo cambiare strutture dati?
Ultima modifica effettuata da andread il 09/11/2010 alle 20:45
Allora, posto che è mezzogiorno e sono quasi in calo di zuccheri, la mia proposta è questa.
Usa un algoritmo "a propagazione". Ammettendo che tu abbia una matrice piena di b, c, p e ' ' opportunamente costruita sulla base di tutti gli altri dati, puoi scorrerla normalmente con due for. Prima ti serve anche una lista concatenata che come elementi abbia delle strutture contenti una posizione (x,y) e un bit di controllo (0 o 1).
Quando nel for incontri una casella contenente uno spazio (ossia niente) la aggiungi alla lista inserendo la sua posizione e impostando il bit di controllo a 1. Quindi inizi a propagare la malta in questo modo, scorrendo la lista e iniziando dalla cella appena incontrata, eventualmente usando qualche thread: se ai lati o sulle diagonali della cella corrente c'è una cella vuota, allora aggiungi la cella vuota alla lista SE NON esiste già, inserendo posizione (x,y) e un bit di controllo impostato a 0. Poi ti sposti al successivo elemento della lista e, se il bit di controllo è 0, ripeti lo stesso procedimento (ossia controlli le celle vicine ed eventualmente le aggiungi). Al termine dell'algoritmo avrai una lista di celle adiacenti e vuote che ora riempirai con malta in questo modo: iteri sulla lista dall'inizio alla fine, leggi per ogni elemento il campo posizione e nella matrice iniziale metti una "m" (malta), poi deallochi l'ultima cella letta (tanto non ti serve più). Finito anche questo, sarai nella situazione seguente: sei ancora dentro ai due for iniziali, ma tutte le celle vuote connesse da altre celle vuote alla prima cella vuota incontrata sono state riempite, quindi verranno ignorate alle prossime iterazioni.
Al termine del for, avrai riempito tutti i sottoinsiemi connessi con della malta.
Ora ho uno stack che contiene tutte le "n" presenti nella matrice.
Ok, ma adesso come tiro fuori le "n" che devono diventare malta (" ") da quelle che non lo devono?
Cioè per fare sì che una zona sia riempita di malta allora bisogna fare in modo che sia delimitata da "p" ma una casella contente "n" può essere riempita anche se è circondata da "n" che a loro volta sono cirocndate da "p" e così via....
Come da esempi (forse mi sono spiegato male):
-Avendo
b b b b b b b b b b b b b b b b b b
b n n n n p p p b b p p p p p p p b
b n n n n p n p b b p n p n n n p b
b n n n p p n p b b p p p p p p p b
b n n n p n n p b oppure b n n p n n n p b
b p p p p n p p b b n n p n n n p b
b p n n n n p n b b n n p n n n p b
b p p p p p p n b b n n p p p p p b
b b b b b b b b b b b b b b b b b b
-Come ottengo (lascio il vuoto perchè si nota meglio ma andrebbe "m"):
b b b b b b b b b b b b b b b b b b
b n n n n p p p b b p p p p p p p b
b n n n n p p b b p p p b
b n n n p p p b b p p p p p p p b
b n n n p p b oppure b n n p p b
b p p p p p p b b n n p p b
b p p n b b n n p p b
b p p p p p p n b b n n p p p p p b
b b b b b b b b b b b b b b b b b b
Allora finchè una casella è delimitata da "p" basterebbe:
Codice sorgente - presumibilmente C++
int n,s,o,e;
currN = testa;
i = currN->x;
j = currN->y;
if(mosaico[i-1][j]=='p') n=1;//printf("p a NORD\n");
if(mosaico[i+1][j]=='p') s=1;//printf("p a SUD\n");
if(mosaico[i][j-1]=='p') o=1;//printf("p a OVEST\n");
if(mosaico[i][j+1]=='p') e=1;//printf("p a EST\n");
Ma per sapere se una casella circondata o con adiacente una "n" possa essere riempita perchè le caselle attorno sono in qualche modo cirocndate da "p" come si può fare? Idee?
Ps.: scusate per le parti in maiuscolo ma era per staccare il testo.
Per prima cosa, il tuo algoritmo non è quello che intendevo io. Tu hai semplicemente aggiunto alla lista dinamica tutte le piastrelle n non vicine a piastrelle b, e questo è abbastanza inutile.
Il tuo push è un po' strano. Di solito il push restituisce l'indirizzo della nuova testa. Tu invece passi un parametro che deve essere vuoto e che viene allocato solo dentro la funzione. Per di più testa è globale (invece dovrebbe essere un parametro della funzione). Di currN poi non te ne fai nulla perché coincide con testa. Inoltre push DEVE aggiungere gli elementi in coda e non in testa, è strettamente necessario perché l'algoritmo funzioni.
Ridefinisci push con questa signature:
Codice sorgente - presumibilmente C/C++
nodo* push(nodo* head, int x, int y, int ctrl)
Ora, io intendevo fare una cosa del genere:
Codice sorgente - presumibilmente C/C++
nodo* tmp;
/* ... */
for(i=1; i < righe; i++)
for(j=1; j < colonne; j++)
if (mosaico[i][j] == 'n')
{
testa = push(testa, i, j, 0);
for(tmp = testa; tmp; tmp = tmp->next)
{
if (mosaico[i + 1][j] == 'n') testa = push(testa, i + 1, j, 0);
if (mosaico[i][j + 1] == 'n') testa = push(testa, i, j + 1, 0);
/* eccetera */
}
/* Ora la lista contiene un insieme connesso di n */
/* Qui controlli che sia coerente, poi svuoti la lista */
/* N.B.: se l'insieme non è coerente, sostituisci tutte le n nella lista con o */
}
Alcune considerazioni:
1) La lista viene creata tante volte quante sono gli insiemi connessi di n, quindi si riempie e si svuota più volte durante i due for;
2) Il for(tmp = testa...) itera su tutti gli elementi della lista e man mano ne aggiunge di nuovi. All'inizio ce ne sarà solo uno. Se questo ha delle n adiacenti le aggiunge, quindi la lista cresce mentre viene enumerata.
3) Alla fine di questo for, la lista contiene le piastrelle n connesse tra loro, ma questo insieme non è necessariamente coerente, ossia può essere vicino al bordo. L'unica condizione perché n sia coerente è che nessuna piastrelle della lista sia adiacente a un bordo b. Basta un semplice for per controllare questa condizione. Oppure, ancora meglio, puoi controllarla direttamente quando scorri la lista! Se incontri un b, stoppi il for con un break e usi una variabile di controllo per sapere l'esito.
4) Una volta verificata la coerenza, ci sono due possibilità: o l'insieme è coerente, nel qual caso lo riempi di malta, oppure non lo è. Se non lo è, abbi cura di sostituire tutte le n che sono presenti sia nella lista che nella matrice con un'altra lettera, ad esempio "o", ad indicare che quell'insieme di piastrelle non può essere riempito (ciò evita altri controlli da parte della coppia di for iniziali).
5) Ricordati di svuotare la lista.
Ultima modifica effettuata da Il Totem il 11/11/2010 alle 17:12
Devi aggiungere elementi in coda e non in testa, te l'avevo già detto.
Lascia stare il bit di controllo, a guardar bene non serve.
Se negli if controlli che la piastrella non sia un bordo, devi impostare un qualche flag che ti dica questo, poiché se arrivi alla fine del while non sai se sei uscito perché hai finito di contare le piastrelle n vicino o perché una era vicina al bordo.
Perché la funzione che aggiunge elementi si chiama Leggi? Un po' di coerenza di vuole.
Ti ho detto ti togliere il bit di controllo, perché non serve. Infatti tu aggiungi un nuovo elemento alla lista con il bit a 1. Poi, mentre scorri, se il bit è 1, lo aggiungi di nuovo. Risulta che aggiungi infiniti elementi tutti uguali senza mai uscire dal ciclo.
Per piacere, usa l'indentazione e le parentesi in maniera corretta, e soprattutto decidi come metterle.
