Wyjście z labityntu, bez biblioteki STL.

0

Witam. Mam do napisania program :

Wczytuję rozmiar labiryntu AxB, wypełniam danymi z przedziału {-5,-1,0}, przy czym liczba -5 może wystąpić raz lub dwa razy w n linijkach (jedna z nich to punkt początkowy, a druga wyjście), gdzie -1 oznacza ścianę, a liczba 0 oznacza korytarz. Można isć w cztery strony (nie na skos) Na wyniku ma być liczba mówiąca o długości najkrótszej drogi, lub informacja, że wyjścia nie ma
Co najważniejsze : Nie mogę użyć nic z biblioteki STL, tj. vector, set, map, list, queue, ani znaków '[' i ']'.

Zrobiłem deklarację tablicy dwuwymiarowej na malloc, wskaźniki. Ale co teraz? Algorytmów widziałem na necie sporo, ale wszystkie korzystają z STL.. Proszę o pomoc :)

0

Transponuj sobie ten labirynt na graf nieskierowany i puść tam Dijkstre.

0

Mozna cos wiecej? Programuje od 3 miesiecy, nie zrozumielem za wiele z tego co powiedziales :)
Nie znam grafow i tego algorytmu, nie da sie bez nich..?

0

Wszystko co byś wymyślił, będzie Dijkstrą lub jego niedorobioną wersją, i tak, bez grafów niuja.

0

Możesz zamiast Dijkstry użyć algorytmu Bellmana-Forda, jest znacznie łatwiejszy i działa trochę wolniej ale poda tak samo optymalne rozwiązanie problemu.
Grafy to nic strasznego, ot zwykłe wierzchołki krawędzie ;]

0

Moze mi ktos powiedziec jak to zrobic uzywajac struktury "Kolejka" ? Nie moge krzystac z Queue, ale moge stworzyc strukture, ktora by sie tak zachowywala.
na razie mam tablice + wypelnienie na malloc. Ma zwracac tylko najkrotsza droge, wiec mozna nadpisywac juz zwiedzone.. Jakis pomysl jak najlatwiej?

0

Lista jednokierunkowa lub tablica.

0

No jak bardzo chcesz to możesz reprezentować graf za pomocą listy sąsiedzctwa, tzn masz tablicę o rozmiarze V (ilość wierzchołków grafu) i każdym elementem jest lista/kolejka wierzchołków z którymi dany wierzchołek jest połączony krawędzią.

0

A dlaczego się upieracie na tym, żeby grafowi w tym problemie nadawać jakąś specjalną strukturę? Każdy wierzchołek grafu jest punktem w labiryncie, krawędzie grafu są między sąsiednimi punktami w labiryncie, które nie są ścianą. Czyli jak byś był w wierzchołku, to żeby dostać krawędzie po prostu sprawdzasz 4 sąsiednie pola. Do przechowywania czy pole było odwiedzone można użyć tablicy dwuwymiarowej o tym samym rozmiarze, kolejka przyda się przy przechowywaniu pól do odwiedzenia, możesz to łatwo zrobić na buforze cyklicznym, lub liście cyklicznej.

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