Problema programma in C

[Jackoz33]

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

[Devil 8Ball]

Per arrivare alla soluzione devi crearti un albero multi-dimensionale doppiamente concatenato.
Se ho compreso correttamente la richiesta, è sufficiente creare un ipotetico albero con N nodi (stanze), ogniuna delle quali contiene X oggetti e collegata tramite M corridio (ovvero puntatori doppi alle stanze a cui è collegata).
come tipo di dato, mi verrebbe in mente questa struttura:

struct Chamber {
int object // numero oggetti;
int already_visited = 0 //la stanza è già stata visitata? 0 FALSE 1 TRUE
struct Chamber *corridor1 = NULL;
struct Chamber *corridor2 = NULL;
struct Chamber *corridor3 = NULL; //puntatori alle stanze collegate (supponiamo max 5)
struct Chamber *corridor4 = NULL;
struct Chamber *corridor5 = NULL;
}

int questo modo puoi crearti N stanze, e in base agli input sai quali sono collegate e quali no; infine scorri tutte le stanze controllando il flag per vedere se è già stata visitata

[Jackoz33]

grazie

[Jackoz33]

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

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

e anche una struttura corridoio quindi:

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?

[Devil 8Ball]

Il ragionamento mi sembra corretto, forse un po' più complicato del necessario ma se ti trovi tu non ti forzo certo a cambiarlo.
Dalla tua soluzione però sorge un problema: supponiamo che tu sia nella stanza X che è collegata a Y e Z.
Ora, secondo la tua risoluzione (giusta ripeto) visiti Y, torni a X e visiti Z.
Tuttavia, se Z non presenta corridoi (escluso quello proveniente da X), hai pensato a come fare per tornare indietro?

[Jackoz33]

perfetto questo era il problema che si creava se era un vero problema di ricerca in un grafo invece qui io so a priori quali sono le stanze che hanno nella coppia (I,J) la I che è uguale alla stanza di partenza S quindi il mio ciclo di ricerca sarebbe così:

for (i=1; i<=N; i++) {
if ( elenco_stanze[i].elenco_corridoi[i].I == S )
     {
/* se uno dei 10000 corridoi che una stanza può avere ha come primo numero 
   I = S allora ho trovato una delle stanze che può essere collegata a quella 
   di partenza S*/
          elenco_stanze_collegabili_a_S[i] = elenco_stanze[i];
/* aggiungo il numero di oggetti di tale stanza al totale che dovrò stampare */
          contatore_oggetti_totale += elenco_stanza[i].numero_oggetti;
/* e devo anche mettere la flag a true a dire che ho appena visitato l'oggetto
   e non dovrò rivisitarlo più poichè il programma dice che l'esploratore
   può anche tornare indietro nei corridoi */
          elenco_stanza[i].gia_visitato = true;
     }
}

Sono però d'accordo che l'ho resa più complessa inutilmente e che in questo caso la flag è quasi inutile, concordi con me?

[Devil 8Ball]

Giusto giusto stavo considerando un problema più generale al tuo...
Per i flag a questo punto fai così: una volta che visiti una stanza (e prendi gli oggetti) puoi porre gli oggetti di quella stanza a 0 (come se gli avessi effettivamente presi) in modo che se ti trovi una stanza con 0 oggetti sai che per forza di cose che è già stata visitata, senza ricorrere al flag

[Jackoz33]

Giusto giusto stavo considerando un problema più generale al tuo...
Per i flag a questo punto fai così: una volta che visiti una stanza (e prendi gli oggetti) puoi porre gli oggetti di quella stanza a 0 (come se gli avessi effettivamente presi) in modo che se ti trovi una stanza con 0 oggetti sai che per forza di cose che è già stata visitata, senza ricorrere al flag

Ottimo grazie mille...!