Graf z labiryntu

0

Witam. Mam pytanie. Jak przykładowo mając taki labirynt :

xxxox
xxxox
xxcox
xxxox , gdzie "x "jakieś ściany , "o" to ścieżki prawidłowe a "r" to cel do którego trzeba dojść

zaimplementować go do postaci grafu w języku ANSI C ? ( listy sąsiedztwa). Czyli graf ścieżki w labiryncie.

0

A gdzie widzisz problem? Niech każde 'o' oraz 'r' będą wierzchołkami grafu a jeśli się "stykają" to masz tam krawędź.

0

Ok . To może inaczej jednak. Mam labirynt zapisany w tablicy dwuwymiarowej, "X" to jakieś ściany , "O" to ścieżki przez którę mogę przechodzić i "C" to cel do którego muszę dojść najkrótszą drogą. W jaki sposób wykorzystać algorytm BFS do znalezienia najkrótszej drogi w takiej dwuwymiarowej tablicy ?

0

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ę)

  1. Dodajesz do kolejki punkt startowy (start_x,start_y)
  2. Wykonujesz pętlę dopóki nie trafiłeś na punkt końcowy lub kolejka nie jest pusta
  3. Wyciągasz z kolejki punkt (x,y) i oznaczasz go jako "odwiedzony" (np. zmieniając 'O' w tablicy na 'A' :P)
  4. Jeśli (x,y) to szukany wierzchołek to zapisujemy jego węzeł i przerywamy pętlę
  5. 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.

1 użytkowników online, w tym zalogowanych: 0, gości: 1