Algorytmy do drukowania ścieżek ekranowych za pośrednictwem labiryntu tekstowego

Question

Dla mojego zadania C++, zasadniczo próbuję przeszukać fragment tekstu w pliku tekstowym (który jest przesyłany strumieniowo do mojego wektora vec) rozpoczynając od druga górna postać po lewej. To jest dla labiryntu tekstowego, w którym mój program ma na końcu wydrukować znaki dla ścieżki przez niego.

Przykładem labiryntu byłoby jak:

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

Gdzie „#” jest unwalkable ścian i zawsze rozpoczyna się w lewo na drugim górnym znaku. Znaki alfabetyczne oznaczają kwadraty, które można przechodzić. Zjazd (y) są ZAWSZE po prawej stronie. Labirynt ma zawsze rozmiar 15x15 w pliku labiryntu. Znaki alfabetyczne powtarzają się w tym samym labiryncie, ale nie bezpośrednio obok siebie.

Co staram się tutaj zrobić, to: jeśli kwadrat obok bieżącego ma alfabetyczną postać, dodaj go do wektora vec i powtarzaj ten proces, aż dojdę do końca labiryntu. Ostatecznie mam zrobić to bardziej skomplikowanym, drukując na ekranie wiele ścieżek, które istnieją w niektórych labiryntach.

tej pory mam to dla samego algorytmu, co wiem, to źle:

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 jest moje utrzymanie wektor utwór z odwiedzanych kwadratów.

Jak mogę to zaktualizować, aby faktycznie działało, i ostatecznie, aby móc zarządzać więcej niż jedną ścieżką (np. Gdyby były 2 ścieżki, program wydrukowałby na obu ekranach)? Pamiętam, jak mówiono mi, że mogę potrzebować innego wektora/tablicy, który śledzi kwadraty, które już odwiedziłem/sprawdziłem, ale w jaki sposób mogę to dokładnie tutaj zaimplementować?

Answer 1

Jesteś na dobrej drodze. Jeśli chodzi o labirynty, typową metodą rozwiązywania jest albo przeszukiwanie w głąb pierwszego (najskuteczniejsze rozwiązanie do znalezienia jakiejś ścieżki), albo przeszukanie w pierwszej kolejności (mniej wydajne, ale ma pewność, że znajdzie optymalną ścieżkę). Ponieważ wydaje się, że chcesz przeprowadzić wyczerpujące wyszukiwanie, te opcje są zasadniczo zamienne. Proponuję zapoznać się na nich:

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

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

Zasadniczo trzeba będzie analizować swoją labirynt i reprezentuje ją w postaci wykresu (gdzie każdy bez „#” to węzeł i każdy link jest ścieżką do chodzenia). Następnie przechowujesz listę częściowych ścieżek (tj. Listę węzłów w kolejności, w jakiej je odwiedziłeś, na przykład [S, b, c] jest częściową ścieżką zaczynającą się od S i kończącą się na c). Główną ideą systemu plików DFS i BFS jest lista częściowych ścieżek i jeden po drugim usuwanie elementów z listy, generowanie wszystkich możliwych ścieżek częściowych prowadzących od tej częściowej ścieżki, a następnie umieszczanie ich na liście i powtarzanie. Główną różnicą między DFS i BFS jest to, że system plików DFS implementuje tę listę jako stos (tj. Nowe elementy mają największy priorytet), a system plików BFS używa kolejki (to znaczy, że nowe elementy mają najniższy priorytet).

Więc do labiryntu z zastosowaniem DFS będzie działać tak:

1. węzeł początkowy jest S, więc początkowy ścieżka jest tylko [S]. Wciśnij [S] do swojego stosu ([[S]]).
2. Pop pierwszy przedmiot (w tym przypadku [S]).
3. Zrób listę wszystkich możliwych węzłów, do których można dotrzeć w 1 ruchu z bieżącego węzła (w twoim przypadku, po prostu b).
4. Dla każdego węzła z kroku 3 usuń wszystkie węzły będące częścią bieżącej ścieżki częściowej. Zapobiegnie to pętlom. (tzn. dla częściowej ścieżki [S, b], od b możemy podróżować do c i do S, ale S jest już częścią naszej częściowej ścieżki, więc powrót jest bezcelowy)
5. Jeśli jednym z węzłów z kroku 4 jest cel węzeł, dodaj go do ścieżki częściowej, aby utworzyć ukończoną ścieżkę. Wydrukuj ścieżkę.
6. Dla każdego węzła od kroku 4, który NIE JEST węzłem celu, wygeneruj nową ścieżkę częściową i wciśnij ją do stosu (tj. Dla [S] generujemy [S, b] i wciskamy ją do stosu, który teraz powinien wyglądać jak [[S, b]])
7. Powtarzaj kroki od 2 do 6, dopóki stos nie będzie pusty, co oznacza, że ​​przejechałeś każdą możliwą ścieżkę od początkowego węzła.

UWAGA: w twoim przykładzie znajdują się zduplikowane litery (na przykład trzy "e"). Dla twojej sprawy, może utwórz prostą klasę "Węzeł", która zawiera zmienną do przechowywania litery. W ten sposób każde "e" będzie miało swoją własną instancję, a wskaźniki będą miały różne wartości, pozwalające łatwo je odróżnić. Nie wiem, C++ dokładnie, ale w pseudo kod:

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

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

Można odczytać każdy znak w pliku, a jeśli to nie jest „#”, należy utworzyć nową instancję węzła dla tego znaku i dodać wszystkie sąsiednie węzły.

EDYCJA: Ostatnie 3 lata spędziłem jako programista w języku Python i zostałem trochę rozpieszczony. Spójrz na poniższy kod.

s = "foo" 
s == "foo" 

W Pythonie to stwierdzenie jest prawdziwe. "==" w Pythonie porównuje ciąg znaków zawartość. To, o czym zapomniałem z moich dni jako programisty Java, polega na tym, że w wielu językach "==" porównuje wskaźniki stringów:. Dlatego w wielu językach, takich jak Java i C++, asercja jest fałszywa, ponieważ ciągi wskazują na różne części pamięci.

Chodzi mi o to, że ponieważ to stwierdzenie nie jest prawdziwe, MOŻESZ zrezygnować z tworzenia klasy Node i po prostu porównać znaki (używając ==, NIE używając strcmp()!) ALE ten kod może być nieco mylący w czytaniu i muszą być udokumentowane.

Ogólnie rzecz biorąc, użyłbym jakiejś klasy Node tylko dlatego, że jest ona dość łatwa do zaimplementowania i skutkuje bardziej czytelnym kodem I wymaga tylko analizowania twojego labiryntu raz!

Powodzenia