Problema programma in C

[tomjones23]

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

[Filly95]

Parto dal presupposto che sto imparando il C. Così a occhio ti posso dire che conviene utilizzare la programmazione dinamica, ma visto che gli oggetti non hanno un valore particolare per cui devi recuperare quelli "migliori", potresti muoverti con un approccio greedy. Questo pdf mi ha aiutato molto: http://81.208.32.83:8080/ioi/files/G...rritoriali.pdf

EDIT: Ho detto una cazzata, per questo problema meglio grafi come ha detto demos88. Nel pdf linkato sopra sono spiegati abbastanza bene.

[demos88]

A occhio direi che a livello astratto il problema da risolvere è l'identificazione della componente connessa di un grafo potenzialmente non connesso a partire dal nodo di partenza e il conto di tutti gli oggetti presenti nei nodi connessi. I dati di input in tuo possesso costituiscono la matrice di adiacenza relativa al grafo.
Se hai capito quello che ho scritto sopra, penso che tu abbia la risposta in tasca: una volta che definisci che una stanza corrisponde a un nodo e un corridoio a un arco bidirezionale, sommi gli oggetti contenuti in tutti i nodi del sottografo connesso che contiene il nodo di partenza. Altrimenti devi studiarti un po' di teoria dei grafi, o pensarla in modo diverso (al momento non mi viene in mente nulla).
Mi pare che sia l'algoritmo di Tarjan quello che permette la definizione del sottografo (fortemente) connesso. E' passato un po' di tempo dall'esame di Dati e Algoritmi quindi potrei ricordare male.

[tomjones23]

Ok ho capito. Purtroppo l'esame che devo fare è di programmazione in C e quello di algoritmi e strutture dati ancora non lo seguo quindi non conosco questi algoritmi ecco perchè credo che in questo esempio non ci sia proprio tutto l'algoritmo di ricerca nei grafi ecco perchè ho pensato di creare queste due strutture:

struct corridoio {
     int I;
     int J;
     };  

struct stanza {
     int numero_oggetti; // numero oggetti
     bool gia_visitato; 
     struct corridoio elenco_corridoi [ 10000 ];
     };

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 stanze (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?