Giro in Bici (ciclismo)

Aiuto
1

Salve a tutti,
Oggi ho provato a risolvere il problema delle OIS2016 “ciclismo”.
Ho provato a risolvere il problema con una dfs ma ottengo 0/100.
Qui trovate il mio codice = https://pastebin.com/KfY6uKTR.
Grazie :slight_smile:

2

Ciao! L’idea è quasi corretta, se non per un paio di piccoli errori. Il primo è che ti sei scordato di modificare il vettore visitato ogni volta che visiti un nodo :laughing: Almeno tu l’hai dichiarato, al contrario di me alle nazionali delle OIS… :man_facepalming:
Inoltre, il tuo algoritmo cerca ogni volta di andare a tutti i vicini di un nodo se sono più piccoli del vicino precedente; in realtà il problema dice che, da un nodo n, Giorgio andrà solo al nodo m tale che H[m] è il minore tra tutti i vicini di n. In poche parole, da un nodo n, Giorgio può scegliere un nodo soltanto (o, nel caso peggiore, non può sceglierlo affatto), e questo nodo deve essere quello più in basso tra tutti quelli disponibili. Nota bene: non è detto che H[m] sia minore di H[n]…
Ultima cosa: il tuo programma ha un problema in un caso particolare, cioè quando non riesce a trovare un vicino adatto (attento alle posizioni del vettore visitato a cui accedi!).

3

Siccome ho imparato da pochi giorni i grafi e non so muovermi ancora molto bene, vorrei chiederti come faccio a scegliere il nodo più basso tra quelli disponibili e a sapere quali sono i nodi disponibili ?

4

Dipende da come decidi di rappresentare il grafo. Tu hai deciso di rappresentarlo sotto forma di liste di adiacenza (ed è la scelta migliore quasi sicuramente): questo vuol dire che il vettore G[n] conterrà tutti i nodi che sono adiacenti a n. Dato che il problema ci chiede di passare sempre da un nodo n a un suo vicino, ora sappiamo che questo vicino si troverà per forza in G[n]. Per controllare tutti i vicini di un nodo basta usare un for come hai fatto tu: quel for ti permette di fare un ciclo tra tutti gli elementi di G[n], che sono i vicini di n.

Per trovare il minimo basta fare come se volessimo trovare il minimo elemento di un vettore: inizializziamo Min a -1 e Peso_Min ad un valore molto alto (come 1000001 , in quanto tutti i pesi H[i] <= 1000000), e ogni volta controlliamo se H[x] (l’elemento corrente) < Peso_Min e che x non sia il precedente (basta salvarsi il precedente in una variabile e aggiornarlo di volta in volta), aggiornando Min e Peso_Min se necessario. Alla fine di questo ciclo for abbiamo trovato il vicino con altezza più bassa che non sia il precedente, quindi possiamo continuare la chiamata ricorsiva se (Min != -1 && !visitato[Min]), altrimenti se Min == -1 ritorniamo n (perché Giorgio non può andare da nessun altra parte), infine se Min != -1 && visitato[Min]) ritorniamo Min (perché Giorgio arriva in un incrocio in cui è già passato).

Dimmi se hai altri dubbi!

5

Per come ho capito io, ho modificato così la dfs:

int dfs(int n)
{
    int Min = -1;
    int Peso_Min = 1000001;
    visited[n] = true;
    for (auto x : G[n])
    {
        if(H[x] < Peso_Min && x != prec)
        {
            Min = x;
            Peso_Min = H[x];
        }
        prec = x;
        if(!visited[Min] && Min != -1) dfs(Min);
        else if(Min == -1) return n;
        else if(visited[Min] && Min != -1) return Min;
    }
}
6

L’unico errore è che prec deve diventare n, non x, in quanto ogni volta che chiami la dfs, tu passi dal nodo n al nodo Min, quindi n è il precedente di Min, non x. Inoltre, dato che x viene dichiarato nel for, x esiste solamente nel for.
Cambia questa cosa e prova a sottometterlo, dovrebbe funzionare!

7

Non funziona lo stesso

8

Questo è il mio codice e dà 100/100, magari mi sta sfuggendo qualcosa… https://pastebin.com/SaShe0Nx

9

Il prec = n l’avevo messo dentro il for :smiley:

10

Ahh, aspetta, tu avevi messo ancora il prec e i vari if dentro il for, ho immaginato una graffa prima. Comunque, devi mettere tutta quella roba dopo perché non devi valutare ogni vicino di n ma soltanto quello minore, e se fai le operazioni dentro il for ogni volta scegli il minimo parziale, cioé il minimo fino a quel momento, e non il minimo tra tutti i vicini di n. Spero di esser stato chiaro :sweat_smile:

11

Si si grazie, avevo messo tutti gli if fuori dal ciclo già da un po’ ma mi ero scordato di uscire il prec…
Comunque ho ottenuto 100/100.
Grazie

1 Mi Piace