[C] Progetto labirinto

[roberto.p89]

Salve a tutti,
ho visto già altre discussioni riguardati lo stesso progetto che sto sviluppando io, ma nessuna di queste risolve il mio problema quindi vorrei chiedervi aiuto.
Il progetto consiste nel generare in modo casuale un labirinto di grandezza n x m con un numero k di muri interni. L'ingresso del labirinto potrà trovarsi in una delle posizioni perimetrali del labirinto ad eccezione dei suoi vertici, mentre l'uscita può trovarsi in un punto qualsiasi.
Non ho problemi nel generare il labirinto neanche per trovarne la soluzione (ad eccezione di un caso).
Per trovare la soluzione non posso utilizzare funzioni ricorsive.
L'algoritmo che ho usato consiste nel partire dall'uscita e tracciare il percorso fino all'ingresso. Ho reputato più agevole questo metodo in quanto la posizione dell'ingresso è vincolata dall'essere posizionata sul perimetro.
Dunque l'algoritmo di risoluzione si divide in due punti:
1- far raggiungere all'esploratore un muro perimetrale
2- una volta raggiunto questo muro con l'algoritmo della mano destra sarò sicuro di trovare l'ingresso nel caso sia raggiungibile.
Nel punto 2 non ho problemi. Il vero problema è raggiungere una posizione perimetrale dalla posizione d'uscita.
Qualcuno sa darmi consigli su come fare?
Se può essere utile fornisco il codice del labirinto da me sviluppato.
grazie

[clockover]

Scusa ma che modo è partire dall'uscita?? Secondo me non può essere valida una cosa del genere... altrimenti un labirinto che esiste a fare

[roberto.p89]

le specifiche del progetto mi chiedono di trovare una soluzione al labirinto, e anche partendo dall'uscita verso l'ingresso trovo una soluzione. Secondo te non va bene utilizzare questo metodo? Ma partendo dall'ingresso sorgono diversi problemi nella ricerca dell'uscita. Perchè utilizzando sempre l'algoritmo della mano destra e ponendo che l'esploratore non ripassi due volte sullo stesso punto (altrimenti troverebbe l'uscita solo nel caso sia perimetrale) c'è la possibilità che mi ritrovi dei punti che non vengono controllati.

[clockover]

Guarda io non lo farei così... secondo me non è logico...
Potresti però provare con algoritmi non ricorsivi di visita utilizzando una pila

[roberto.p89]

praticamente tu diresti, partendo dalla posizione d'ingresso, ogni cella della matrice labirinto ha come dati lo stato delle celle adiacenti (a destra, in alto, a sinistra e in basso), e questo stato può essere muro, calpestabile o "già provato". In questo modo provo ogni direzione sequenzialmente e nel caso mi porti ad un vicolo cieco ritorno indietro segnando quel percorso come "già provato". E' questo quello che intendi?

[clockover]

Si io farei così.. faresti una visita in ampiezza

[roberto.p89]

mmm... ho capito. ma in questo caso la pila dovrebbe avere sia un puntatore al elemento successivo che al precedente (per poter tornare indietro in caso di percorso "sbagliato") giusto?
grazie comunque sei stato gentilissimo!!

[clockover]

lasciando stare la questione dei puntatori.... la pila ti serve apposta per tornare indietro e scegliere un altro percorso... quindi come farebbe una funzione ricorsiva.. poi ovviamente il resto dell'algoritmo devi implementarlo per adattarlo alla tua struttura dati...