Algoritmo per stampare su schermo percorso (s) attraverso un labirinto di testo

Question

Per il mio incarico C++, sto praticamente cercando di cercare attraverso un pezzo di testo in un file di testo (che viene trasmesso al mio vettore vec) a partire dal secondo personaggio in alto a sinistra. È per un labirinto di testo, dove il mio programma alla fine dovrebbe stampare i personaggi per un percorso attraverso di esso.

Un esempio di un labirinto sarebbe come:

############### 
Sbcde####efebyj 
####hijk#m##### 
#######lmi##### 
############### 
############### 
############### 
############### 
############### 
############### 
############### 
############### 
############### 
############### 
############### 

Dove '#' è un muro unwalkable e si comincia sempre al secondo carattere in alto a sinistra. I caratteri alfabetici rappresentano quadrati percorribili. Le uscite sono SEMPRE sulla destra. Il labirinto ha sempre una dimensione 15x15 in un file maze.text. I caratteri alfabetici si ripetono nello stesso labirinto, ma non direttamente l'uno accanto all'altro.

Quello che sto cercando di fare qui è: se un quadrato accanto a quello attuale ha un carattere alfabetico, aggiungilo al vettore vec, e ripeti questo processo fino a quando non arrivo alla fine del labirinto. Alla fine, dovrei renderlo più complicato stampando sullo schermo più percorsi che esistono in alcuni labirinti.

Finora ho questo per lo stesso algoritmo, che so che è sbagliato:

void pathcheck() 
{ 
    if (isalpha(vec.at(x)) && !(find(visited.begin(), visited.end(), (vec.at(x))) != visited.end())) 
    { 
     path.push_back(vec.at(x)); 
     visited.push_back(vec.at(x)); 
     pathcheck(vec.at(x++)); 
     pathcheck(vec.at(x--)); 
     pathcheck(vec.at(x + 16)); 
     pathcheck(vec.at(x - 16)); 
    } 
} 

visited è la mia tenuta vettore traccia delle piazze visitati.

Come aggiornarlo in modo che funzioni effettivamente, e alla fine così posso gestire più di un percorso (vale a dire se ci fossero 2 percorsi, il programma stamperebbe sullo schermo entrambi)? Ricordo che mi è stato detto che potrei aver bisogno di un altro vettore/array che tenga traccia dei quadrati che ho già visitato/controllato, ma come potrei implementarlo esattamente qui?

Answer 1

Sei sulla strada giusta. Quando si tratta di labirinti, il metodo tipico di risoluzione è attraverso una ricerca in profondità (la soluzione più efficiente per trovare un percorso) o una ricerca in ampiezza (meno efficiente, ma è garantito per trovare il percorso ottimale). Poiché sembra che tu voglia fare una ricerca esauriente, queste scelte sono fondamentalmente intercambiabili. Vi suggerisco di leggere su di loro:

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Breadth-first_search

In sostanza, è necessario analizzare il tuo labirinto e rappresentarlo come un grafico (in cui ogni non "#" è un nodo e ogni link è un percorso percorribile). Quindi, mantieni un elenco di percorsi parziali (ad esempio un elenco di nodi, nell'ordine in cui li hai visitati, ad esempio, [S, b, c] è il percorso parziale che inizia da S e termina in c). L'idea principale di DFS e BFS è che hai un elenco di percorsi parziali e uno per uno rimuovi gli elementi dall'elenco, genera tutti i possibili percorsi parziali che portano da quel percorso parziale, quindi li colloca nell'elenco e lo ripete. La principale differenza tra DFS e BFS è che DFS implementa questo elenco come stack (vale a dire che i nuovi elementi hanno la priorità maggiore) e BFS utilizza una coda (ad esempio, i nuovi elementi hanno la priorità più bassa).

Quindi, per il labirinto utilizzando DFS che avrebbe funzionato in questo modo:

1. nodo iniziale è S, in modo che il percorso iniziale è solo [S]. Spingere [S] nella pila ([[S]]).
2. Inserisci il primo elemento (in questo caso, [S]).
3. Crea un elenco di tutti i nodi possibili che puoi raggiungere in 1 spostamento dal nodo corrente (nel tuo caso, solo b).
4. Per ciascun nodo del passaggio 3, rimuovere tutti i nodi che fanno parte del percorso parziale corrente. Ciò impedirà i loop. (cioè per il percorso parziale [S, b], da b possiamo viaggiare verso c e verso S, ma S è già parte del nostro percorso parziale, quindi il ritorno è inutile)
5. Se uno dei nodi del passaggio 4 è l'obiettivo nodo, aggiungilo al tuo percorso parziale per creare un percorso completo. Stampa il percorso.
6. Per ciascun nodo del passaggio 4 che NON È il nodo obiettivo, generare un nuovo percorso parziale e inserirlo nello stack (cioè per [S], generiamo [S, b] e lo inseriamo nello stack, che ora dovrebbe apparire come [[S, b]])
7. Ripetere i passaggi da 2 a 6 finché lo stack non è vuoto, significa che si è attraversato ogni possibile percorso dal nodo iniziale.

NOTA: nell'esempio sono presenti lettere doppie (ad esempio, tre "e"). Per il tuo caso, magari creare una semplice classe "Node" che includa una variabile per contenere la lettera. In questo modo ogni "e" avrà la sua istanza e i puntatori avranno valori diversi che ti consentiranno di distinguerli facilmente. Non so C++ esattamente, ma in pseudo-codice:

class Node: 
    method Constructor(label): 
     myLabel = label 
     links = list() 

    method addLink(node): 
     links.add(node) 

si poteva leggere ogni personaggio nel file e se non è "#", creare una nuova istanza del Nodo per quel personaggio e aggiungere tutte le nodi adiacenti.

EDIT: Ho trascorso gli ultimi 3 anni come sviluppatore Python e mi sono un po 'rovinato. Guarda il seguente codice.

s = "foo" 
s == "foo" 

In Python, tale affermazione è vera. "==" in Python confronta il contenuto della stringa . Quello che ho dimenticato dai miei giorni come sviluppatore Java è che in molte lingue "==" confronta i puntatori della stringa. Ecco perché in molti linguaggi come Java e C++ l'asserzione è falsa perché le stringhe indicano diverse parti della memoria. Il mio punto è che, poiché questa affermazione non è vera, NON POTREBBE rinunciare a fare una classe Node e confrontare solo i caratteri (usando ==, NON usando strcmp()!) MA questo codice potrebbe essere un po 'confuso da leggere e deve essere documentato

Nel complesso, utilizzerei una sorta di classe Node solo perché è abbastanza semplice da implementare e risulta in un codice più leggibile E richiede solo di analizzare il tuo labirinto una volta!

Good Luck