Linguaggio c: risolutore labirinto
ciao a tutti!!!
E' da un po' che sto sbattendo la testa ma proprio non riesco a scrivere una funzione che trovi la strada per uscire da un labirinto.
in pratica devo scrivere una funzione ricorsiva per attraversare un labirinto, la funzione deve ricevere come argomenti una matrice di caratteri e la posizione di partenza.
Qualcuno potrebbe darmi una spunto. io ho scritto tutto il programma ma la funzione in questione è sbagliata, o meglio non riesco a capire come ritornare indietro nel caso in cui avessi imboccato una strada sbagliata...
vi ringrazio anticipatamente...
E' da un po' che sto sbattendo la testa ma proprio non riesco a scrivere una funzione che trovi la strada per uscire da un labirinto.
in pratica devo scrivere una funzione ricorsiva per attraversare un labirinto, la funzione deve ricevere come argomenti una matrice di caratteri e la posizione di partenza.
Qualcuno potrebbe darmi una spunto. io ho scritto tutto il programma ma la funzione in questione è sbagliata, o meglio non riesco a capire come ritornare indietro nel caso in cui avessi imboccato una strada sbagliata...
vi ringrazio anticipatamente...
Risposte
Inizia a mostrare quello che sei riuscito a fare. Ci sono diversi algoritmi per risolvere il tuo problema. Visto che non ti è stata chiesto di trovare la strada più breve, ma solo di trovarne una, allora io userei Best First Search. Ma utilizza una priority queue. Altri algoritmi forse più semplici da implementare sono invece il Depth First Search e Breadth First Search. Il Depth First Search è probabilmente quello più facile da implementare in modo ricorsivo e quello che ha in mente il tuo professore.
ciao e grazie per la risposta questo è il codice che ho fatto io
http://codepad.org/z1sQVVtb
naturalmente la funzione di cui sopra è tutta sbagliata, diciamo che l'ho fatta troppo su misura per il labirinto che ho fatto io, infatti per quello funziona ma solo perché gli if sono messi in un ordine preciso LOL...
comunque a parte gli scherzi non vorrei usare i grafi e algoritmi troppo complicati sia perchè il nostro professore non la ha ancora spiegati sia perchè non riesco ancora ad usarli bene...
avevo in mente di fare qualcosa usando la ricorsione, solo che non riesco a tradurla in codice.
Avevo pensato ad una cosa del genere:
- marca la cella corrente
- per ogni cella A, adiacente alla cella corrente C
- Se A appartiene alla lista delle celle visitate, RETURN False
- Se A non è camminabile, RETURN False
- Se A == Cella finale, allora
- arrivo = True
- GOTO Fine
- Altrimenti goal = avanza(A)
- Fine:
- se goal == true allora Marca la cella corrente C con il carattere 'x'
solo che come ho già detto non so come tradurlo in c...
http://codepad.org/z1sQVVtb
naturalmente la funzione di cui sopra è tutta sbagliata, diciamo che l'ho fatta troppo su misura per il labirinto che ho fatto io, infatti per quello funziona ma solo perché gli if sono messi in un ordine preciso LOL...
comunque a parte gli scherzi non vorrei usare i grafi e algoritmi troppo complicati sia perchè il nostro professore non la ha ancora spiegati sia perchè non riesco ancora ad usarli bene...
avevo in mente di fare qualcosa usando la ricorsione, solo che non riesco a tradurla in codice.
Avevo pensato ad una cosa del genere:
- marca la cella corrente
- per ogni cella A, adiacente alla cella corrente C
- Se A appartiene alla lista delle celle visitate, RETURN False
- Se A non è camminabile, RETURN False
- Se A == Cella finale, allora
- arrivo = True
- GOTO Fine
- Altrimenti goal = avanza(A)
- Fine:
- se goal == true allora Marca la cella corrente C con il carattere 'x'
solo che come ho già detto non so come tradurlo in c...
Cercherei di tabelizzare tutte le varie scelte che incontro durante il percorso.
Faccio un passo indietro quando incontro un muro, ed un passo avanti quando incontro un bivio.
In questo modo percorro tutte le strade possibili, sperando che una mi porti a destinazione.
Faccio un passo indietro quando incontro un muro, ed un passo avanti quando incontro un bivio.
In questo modo percorro tutte le strade possibili, sperando che una mi porti a destinazione.
ho provato a fare come dici ma se poi devi tornare indietro di più di un passo?
Non so se mi sono spiegato...
Non so se mi sono spiegato...
"_overflow_":
ho provato a fare come dici ma se poi devi tornare indietro di più di un passo?
Non so se mi sono spiegato...
CERTO...
Ogni qualvolta hai terminato le scelte del bivio, o trivio, fai un passo indietro, ricontrolli se hai altre possibilità e se non ne hai un altro passo indietro e cosi' via.
Quando sei sul punto iniziale (punto 1), e non hai altre scelte, hai terminato il tutto.
vi ringrazio... però proprio non riesco, ora riprovo un po' e vedo...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo