Nie jest to idealna struktura ale jeśli bardzo ci zależy żeby takiej używać...
0. Tworzysz sobie kolejkę wierzchołków (czyli par (x,y)), ale każdy wierzchołek w kolejce niech zawiera też informację o tym "skąd przyszliśmy". (to "skad przyszliśmy" mozemy zapisywać znów w tablicy dwuwymiarowej, tak jak mapę)
- Dodajesz do kolejki punkt startowy (start_x,start_y)
- Wykonujesz pętlę dopóki nie trafiłeś na punkt końcowy lub kolejka nie jest pusta
- Wyciągasz z kolejki punkt (x,y) i oznaczasz go jako "odwiedzony" (np. zmieniając 'O' w tablicy na 'A' :P)
- Jeśli (x,y) to szukany wierzchołek to zapisujemy jego węzeł i przerywamy pętlę
- Wkładasz do kolejki wszystkie nieodwiedzone punktu sąsiadujące z (x,y) które mają 'O' czyli coś w stylu:
if (tablica[x+1][y] == 'O'){
//wkladamy (x+1,y) do kolejki
}
if (tablica[x][y+1] == 'O'){
//wkladamy (x,y+1 do kolejki
}
itd
6. Przy wkładaniu do kolejki zapisujemy w wierzchołku że przyszliśmy tu z (x,y)
7. Po wyjściu z pętli mamy zapisany węzeł końcowy i wykonujemy wsteczne odczytywanie ścieżki. Z węzła końcowego wyciągamy współrzędne węzła z którego tam przyszliśmy, z tego węzła znów i postepujemy tak aż trafimy na węzeł początkowy.