[C] Progetto da realizzare in C

[Fabietto206]

Ciao a tutti mi servirebbe una mano su un progetto che devo consegnare per l'università.
Ecco il testo:

Il problema
Come noto, per creare un nuovo mondo a partire dal caos primordiale, bisogna innanzitutto dividere la terra dalle acque. In questo progetto si fa proprio questo. Il mondo appena creato viene poi diviso in habitat al fine di essere popolato.

Divisione terra/acqua
Il caos primordiale è costitutito da una griglia N x N di caselle. Ad ogni casella è associato un valore di Vitalità Primordiale (numeri interi, cioè positivi o anche negativi). Ogni casella è adiacente ad altre 8 (2 in verticale, 2 in orizzontale, e 4 in diagonale - chiaramente le caselle di bordo sono adiacenti solo ad altre 5 caselle, e le quattro caselle di spigolo solo ad altre 3). Ogni coppia di caselle adiacenti possono essere direttamente connesse, oppure possono essere reciprocamente separate da una apposita barriera.
Inizialmente tutte le coppie di caselle adiacenti sono separate da una barriera. La creazione del mondo consiste nella rimozione progressiva di queste barriere, una ad una. Notare che le barriere che separano coppie di caselle in diagonale sono indipendenti fra loro: date 4 caselle adiacenti
AB
CD
la rimozione della barriera fra A e D non implica (nè impedisce) quella della barriera fra B e C.
Due caselle sono dette comunicanti se è possible raggiungere la prima dalla seconda attraverso una sequenza di caselle ciascuna direttamente connessa alla successiva.
Dai quattro angoli del caos primordiale viene immessa di continuo acqua e terra (in effetti, sabbia), che da qui si espande in tutte le caselle comunicanti. Dall'angolo Nord-Ovest e da quello diametralmente opposto
viene immessa acqua; dagli altri due, terra. In ogni momento, una casella può essere già riempita o da terra o da acqua, proveniente da uno dei quattro angoli, oppure può essere ancora vuota. Inizialmente, solo i quattro angoli sono riempiti (da acqua o terra).
Come noto acqua e terra vanno separate! Una barriera non viene mai tolta se ciò causasse un mescolamento di acqua e terra. Cioe' non viene mai rimossa una barriera che separa due caselle attualmente invase rispettivamente da acqua e da terra. Di tutte le altre barriere, viene rimossa ogni volta quella che
separa le due caselle adiacenti la cui vitalità sommata sia maggiore. In caso di pareggio, si rimuova la barriera che connette la casella più settentrionale, e in caso di ulteriore pareggio, quella più ad oriente.
Nota: la rimozione di una barriera non implica sempre un travaso di acqua o sabbia in una zona non ancora occupata. Può succedere ad esempio che si rimuovano barriere fra zone ancora senza nè acqua nè sabbia, oppure fra zone entrambe già occupate da acqua, etc.
La crazione del mondo termina quando sono rimaste solo barriere necessarie a separare acqua da terra.
Nota: a questo punto, ogni casella sarà necessariamente riempita di acqua oppure di sabbia.
Inoltre, l'acqua immessa da Nord e quella immessa da Sud sono diverse per salinità, composizione chimica, etc, e distinguibili; lo stesso vale per la sabbia. Al termine della creazione del mondo, può succedere che l'acqua immessa dai due angoli opposti si sia miscelata, oppure che sia rimasta separata da barriere, e lo stesso per la sabbia: quando una casella di acqua (o sabbia) è cumunicante con entrambe le fonti di acqua (o sabbia), queste si amalgano e si ottine acqua (o sabbia) "mista", distinguibile da ciascuna delle
due originali "pure".

Suddivisione in Habitat
Una volta separate terra e acqua, il passaggio successivo è il popolamento con animali e piante. Genie diverse (ancora senza nome) vengono create per habitat diversi. Al fine di creare in serie esseri viventi nelle giuste quantità, bisognerà misurare quanto sono diffusi ciascuno dei diversi habitat che si sono
formati (oceani, coste, fiordi, pianure, etc).
Ogni casella ha infatti un habitat, definito dal pezzetto di mondo 7 x 7 centrato intorno a quella casella.
Ogni configurazione diversa corrisponde ad un habitat diverso. Dunque due caselle, a qualunque distanza, hanno lo stesso habitat, se sono entrambe invase della stessa acqua (o sabbia), e se sono circondate dalla stessa configurazione di terra e acqua (distinguendole inoltre fra mista e pura, e, se pura, per origine). In altre parole due caselle hanno lo stesso habitat se e solo se i loro due intorni corrispondono esattamente nel contenuto, casella per casella, orientamento compreso. In altre parole ancora, un animale che viva in una casella non avrebbe modo di distinguere quella casella da altre caselle con lo stesso habitat guardandosi intorno entro tre caselle in ogni direzione, nemmeno con l'ausilio di una bussola.
Caselle vicine al bordo (o sul bordo) sono circondate da meno caselle di mondo: il loro habitat avrà dunque alcune caselle mancanti. Questi habitat "di bordo" possono essere identici solo ad habitat dello stesso tipo.
Lo scopo di questa fase è determinare, per ogni casella di mondo, quante altre caselle condividano lo stesso identico habitat.

Dati in Input
Il file di input e' un file di testo in ASCII così formattato: inizialmente, compare il numero di righe (che è anche quello di colonne) che compone il Caos Primordiale. Poi, di fila, il valore di Vitalità Primordiale di ciascuna casella, riga per riga, a partire dall'angolo a Nord-Ovest (finendo dunque nell'angolo a Sud-Est).

Output 1/2: divisione terra e acqua
La divisione finale fra terra e acqua deve essere scritta in un file di testo ASCII, con lo stesso nome del file di input, ma terminato dal postfisso "_b.ppm". La prima riga deve contenere i caratteri P3 (una lettera P
e il numero 3, attaccati). La seconda riga di testo deve contenere il numero di righe del mondo, ripetuto due volte (altezza e larghezza della griglia dunque), seguito dal valore 7 (questi tre numeri vanno separati da spazi).
Dalla terza riga in poi deve comparire una serie di numeri separati da spazi, tre per casella, che specificano se quella casella è invasa da acqua, da terra, e, in entrambi i casi, se l'acqua o la terra provengono dalla fonte nell'angolo a Nord o a Sud (o se si tratta di commistioni).

Si faccia riferimento alla seguente tabella:
Semantica: Tripletta:
Acqua "pura" da fonte a N-O 2 0 5
Acqua "pura" da fonte a S-E 0 2 5
Acqua miscelata 1 1 5
Sabbia "pura" da fonte a N-E 2 5 0
Sabbia "pura" da fonte a S-O 0 5 2
Sabbia miscelata 1 5 1
L'ordine delle caselle è lo stesso di quello del file in input: dalla riga più a Nord a quella più a Sud, e, in ogni riga, dalla casella più a Ovest a quella più a Est. Si possono aggiungere liberamente caratteri di spazio, accapo o tabulazione fra i numeri o le triplette.

Output 2/2: separazione e conteggio habitat
Anche in questo caso, deve essere prodotto un file di testo ASCII, con lo stesso nome del file di input, ma aggiunto dell'estensione "_a.ppm". La prima riga deve contenere i caratteri P2. La seconda riga è identica a quella del primo file prodotto.
Dalla terza riga in poi deve comparire una serie di numeri separati da spazi, uno per casella, nello stesso ordine descritto sopra. Per ogni casella, deve comparire il numero 0 se l'habitat di quella casella compare più di altre 7 volte, altrimenti il numero (7 - i), se l'habitat di quella casella compare identico altre i volte nella scacchiera (caselle che hanno un habitat unico nella mappa appaino dunque col numero 7).

Esempi di istanze del problema
In una griglia 3 x 3 come la seguente:
6 1 7
2 20 4
5 3 8
La prima barriera ad essere abbattuta è quella fra 20 e 8. Come conseguenza, la casella di valore 20 si riempie di acqua proveniente dall'angolo Sud-Est. La seconda barriera a saltare sarebbe quella fra 20 e 7, ma questo causerebbe un miscelamento di acqua e terra. Quindi viene invece rimossa la barriera fra
20 e 6: l'acqua proveniente da Sud-Est e quella proveniente da Nord-Ovest si miscelano. Dopo tutte le rimozioni, la situazione finale vede tutte le caselle riempite di acqua mista, meno i due angoli di valore 7 e 5, che saranno rimasti di sabbia \pura" del rispettivo tipo.
In una griglia così piccola ogni casella ha un habitat reso diverso dalle condizioni di bordo (ad es, la casella di valore 6 è l'unica con prosecuzioni di mondo a E, S e SE).

Mi servirebbe una mano nella struttura dati da utilizzare per ottimizzare al meglio i tempi e il costo delle varie funzioni inerenti al progetto.
Non richiedo una risoluzione del progetto ma una mano nella scelta della struttura dati da scegliere tutto qua....

Ecco l'intero testo del progetto:
http://rapidshare.com/files/39400955...2010d.pdf.html

[Fabietto206]

Dato ke nel file di testo passato come input, oltre ai valori delle vitalità, mi viene anke passato il numero n di righe o colonne. Quindi ho pensato di memorizzare la matrice passata in un array di dimensione n*n.

Da questo array costruisco un'heap (in modalità top-down o bottom-up) e quindi in cima allo heap avrò la casella con la vitalità maggiore da cui partirò e da li poi proseguire con i collegamenti se possibili, dice ke può reggere??

L'elemento casella lo vedo come costituito dal valore + un char x indicare se conterrà acqua o terra.

Consigli?

[Fabietto206]

up

[Teo@Unix]

Originariamente inviato da Fabietto206

up

Credo che aver presentato tutto l'intero progetto abbia provocato un pò di spavento agli utenti del forum... ci vuole molto tempo per leggersi tutto, capire il problema, pensare ad una soluzione e proporti qualcosa...

Il mio consiglio è di cominciare a buttare giù qualcosa tu poi quando trovi una difficoltà chiedi relativamente per quel determinato passaggio.

Penso che così avresti più risposte. Posta del codice.

Non che altrimenti non ci sia volontà di aiutarti ma purtroppo il tempo è nemico numero uno in molti casi..... ... anche il mio....

divide et impera no?