Problema programma in C

[Urtus2]

Salve,
questo è il programma che devo scrivere in linguaggio C:

Un esploratore deve entrare in un labirinto di stanze, connesse tra loro da corridoi. In ciascuna stanza si trova un certo numero di oggetti di valorearcheologico. Il labirinto si compone di N stanze, numerate a partire da 1 e di M corridoi, anch'essi numerati a partire da 1. L'esploratore entra nella stanzaindicata dal numero S e, a partire da tale stanza, puo' muoversi liberamente percorrendo qualsiasi corridoio in entrambe le direzioni, ed entrando in altre stanze. Naturalmente non e' possibile accedere a stanze che non sono collegate tramite una sequenza di corridoi alla stanza di partenza. Il vostro compito èscrivere un programma che calcoli il numero R di oggetti che l'esploratore può raccogliere muovendosi nel labirinto. Il programma acquisisce in ingresso un testo formato da N+M+1 righe. La prima riga contiene una tripla di interi, separati da uno spazio: l'intero positivo N che indica il numero di stanze, l'intero positivo M che indica il numero di corridoi e l'intero positivo S che indica la stanza di partenza. Ognuna delle successive N righe contiene un numero intero positivo pari alla quantità di oggetti contenuti in una stanza: la i-esima di tali righe contiene la quantità di oggetti nella stanza di indice i. Ognuna delle successive M righe contiene una coppia di interi I e J, compresi tra 1 e N, separati da uno spazio; la coppia rappresenta un corridoio che collega la stanza I con la stanza J. Il risultato del programma deve essere scritto in forma di testo. Tale testo deve contenere in un'unica riga, il numero T e niente altro. Si assuma 1 < N < 100, 1 <= S < 100, 1 <= M < 10000, e che ogni stanza contenga al più 10 oggetti.

Ho già scritto in c INPUT e OUTPUT da/a file, ma non riesco a trovare un modo per confrontare quali sono le stanze che si possono collegare a quella da cui parte l'esploratore e quali no, ho provato a fare dei disegni di esempio ma non capisco lo stesso come implentare un algoritmo.

Spero mi possiate aiutare
Grazie

[M@ttia]

Quello che viene descritto "pittorescamente" con stanze, corridoi e labirinti, non è altro che la struttura matematica del GRAFO, composto da nodi (stanze) e lati che li collegano (corridoi).




Quello che viene richiesto è di esplorare il grafo a partire da un nodo S (source) e visitare tutti i nodi raggiungibili.
Di algoritmi di esplorazione dei grafi ne esistono diversi, ma i due più classici sono il DFS (depth-first search, ossia ricerca in profondità) e il BFS (breadth-first search, ossia ricerca in ampiezza).

Ti suggerisco di guardarti un attimino la teoria dei grafi (almeno la pagina di Wikipedia sopra, per familiarizzare con le notazioni) e poi implementare uno dei due algoritmi sopra, vista la grandezza tutto sommato ridotta (100 nodi e 10000 lati) del tuo grafo non dovrebbe essere difficile ottenere subito un risultato, che poi può venire ottimizzato man mano a seconda di come lo hai implementato.

[Urtus2]

Perfetto ho capito , ora ci do una occhiata grazie.

[Urtus2]

pensi che sarebbe possibile scrivere il programma senza uso di costrutti complessi tipo strutture e puntatori, perché io ci avevo pensato ma vorrei farlo con i soli costrutti tipo for, while, if etc... utilizzando quindi array (bidimensionali e monodimensionali).

[M@ttia]

Beh possibile è tutto possibile, solo non sicuramente la scelta più ideale (specie quando le cose si fanno "grosse", i puntatori sono inevitabili per non invecchiare davanti allo schermo)....

[Urtus2]

Allora dimmi se è giusto come ho pensato: ho creato una struttura "stanza" che contiene:

Codice: Seleziona tutto

struct stanza {
     int numero_oggetti; // numero oggetti
     bool gia_visitato; // la stanza è già stata visitata? è una flag
     struct corridoio corridoio1;
     struct corridoio corridoio2;
     struct corridoio corridoio3; //puntatori alle stanze collegate (es, max 4)
     struct corridoio corridoio4;
     };

e anche una struttura corridoio quindi:

Codice: Seleziona tutto

struct corridoio {
     int I;
     int J;
     }; 


a quel punto siccome il corridoio, come dice il testo, è formato da una coppia di interi (I e J) dove il primo numero indica una stanza e il secondo indica un'altra stanza ad essa collegata, allora per trovare quale stanza l'esploratore può raggiungere, e quindi contarne gli oggetti dentro, basta cercare con un for quali stanza (strutture) hanno la I uguale alla stanza di partenza S (I==S) e a quel punto la flag "gia_visitato" di quella stanza andrà a "true" (anche se questa ultima parte mi sembra superflua).
Può essere corretto?

[Urtus2]

correggo: i corridoi sono fino a 10000 non 4 come ho posto quindi inserisco un array di strutture di tipo corridoio:

Codice: Seleziona tutto

struct stanza {
     int numero_oggetti; // numero oggetti
     bool gia_visitato; // la stanza è già stata visitata? è una flag
     struct corridoio elenco_corridoi [ 10000 ];
     };

[M@ttia]

Desumo quindi tu abbia scelto di implementare il BFS.

Noto che nella tua struct "stanze" non hai il numero della stanza stessa, quindi presumo che le stanze verranno poi salvate in un gigante array

Codice: Seleziona tutto

stanza Elenco_Stanze [N]

giusto? In questo caso la i-esima stanza sarebbe Elenco_Stanze[ i ].

L'uso della struct corridoio in questo caso è superflua (ha senso se i collegamenti avessero avuto una lunghezza o altre proprietà struturate), e lo è anche il salvataggio di entrambi i nodi che collega, dato che uno di essi è sempre quello della stanza in cui lo salvi.

Io farei allora così:

Codice: Seleziona tutto

struct stanza
{
  int   numero_oggetti;       // numero oggetti in questa stanza
  bool  visitato;             // flag: la stanza è già stata visitata dal BFS?
  int   stanze_adiacenti [M]; // lista delle stanze raggiungibili da quella attuale
};

A questo punto l'input lo leggi come segue:

• Leggi e salvi int N, M, S
• Crei stanza Elenco_Stanze [N]
• Leggi le N righe con gli oggetti, e il valore dell'i-esima riga va ad aggiornare numero_oggetti di Elenco_Stanze
• Leggi le prossime M righe, e per ogni coppia (I,J) letta vai ad aggiungere in Elenco_Stanze[ I ] il valore J a stanze_adiacenti e viceversa con il valore I in Elenco_Stanze[J]

Fatto questo non ti resta che lanciare il BFS (sempre tenendo conto della stanza attuale come ad es. Z e cercando i collegamenti (risp. leggendo gli oggetti e aggiornando la flag) da Elenco_Stanze [Z]. L'algoritmo termina quando torni a S e tutte le stanze adiacenti risultano già visitate.


P.S.
Personalmente evito sempre un allocamento del tipo stanze_adiacenti [M], che va ad occupare memoria per M*N int, quando la stragrande maggioranza di essi sarà vuoto/inutilizzato (ogni stanza averà magari 4-5 vicini in media), preferendo quindi un array dinamico al quale aggiungere elementi alla bisogna. In C++ esiste la classe Vector, che implementa già in modo eccellente la cosa e ti permette di creare un array dinamico al quale fare array.aggiungi(elemento) e quindi tenendolo sempre della grandezza necessaria (ovviamente sotto il cofano usa i puntatori, ma all'utente finale non interessa). In C forse la cosa è meno immediata, ma appena M e N diventano un po' più grandi, non è più possibile riservare per ogni stanza un array da M elementi...

[Urtus2]

Desumo quindi tu abbia scelto di implementare il BFS.

Noto che nella tua struct "stanze" non hai il numero della stanza stessa, quindi presumo che le stanze verranno poi salvate in un gigante array

Codice: Seleziona tutto

stanza Elenco_Stanze [N]

giusto? In questo caso la i-esima stanza sarebbe Elenco_Stanze.

L'uso della struct corridoio in questo caso è superflua (ha senso se i collegamenti avessero avuto una lunghezza o altre proprietà struturate), e lo è anche il salvataggio di entrambi i nodi che collega, dato che uno di essi è sempre quello della stanza in cui lo salvi.

Io farei allora così:

Codice: Seleziona tutto

struct stanza
{
  int   numero_oggetti;       // numero oggetti in questa stanza
  bool  visitato;             // flag: la stanza è già stata visitata dal BFS?
  int   stanze_adiacenti [M]; // lista delle stanze raggiungibili da quella attuale
};

A questo punto l'input lo leggi come segue:

• Leggi e salvi int N, M, S
• Crei stanza Elenco_Stanze [N]
• Leggi le N righe con gli oggetti, e il valore dell'i-esima riga va ad aggiornare numero_oggetti di Elenco_Stanze
• Leggi le prossime M righe, e per ogni coppia (I,J) letta vai ad aggiungere in Elenco_Stanze[i] il valore J a stanze_adiacenti e viceversa con il valore I in Elenco_Stanze[J]

Fatto questo non ti resta che lanciare il BFS (sempre tenendo conto della stanza attuale come ad es. Z e cercando i collegamenti (risp. leggendo gli oggetti e aggiornando la flag) da Elenco_Stanze [Z]. L'algoritmo termina quando torni a S e tutte le stanze adiacenti risultano già visitate.


P.S.
Personalmente evito sempre un allocamento del tipo stanze_adiacenti [M], che va ad occupare memoria per M*N int, quando la stragrande maggioranza di essi sarà vuoto/inutilizzato (ogni stanza averà magari 4-5 vicini in media), preferendo quindi un array dinamico al quale aggiungere elementi alla bisogna. In C++ esiste la classe Vector, che implementa già in modo eccellente la cosa e ti permette di creare un array dinamico al quale fare array.aggiungi(elemento) e quindi tenendolo sempre della grandezza necessaria (ovviamente sotto il cofano usa i puntatori, ma all'utente finale non interessa). In C forse la cosa è meno immediata, ma appena M e N diventano un po' più grandi, non è più possibile riservare per ogni stanza un array da M elementi...

perfetto bravo ci hai preso in pieno riguardo l'array grande che contiene le varie stanze, allora procedo così che è anche come appunto avevo pensato

Grazie mille sei un grande !!

[M@ttia]

Prego figurati