Question

PROSZĘ O POMOC

"Napisz program, który znajdzie najkrótszą drogę prowadzącą od wczytanego pola do wyjścia z labiryntu oraz wypisze planszę ze znalezioną drogą. Jeśli droga prowadząca do wyjścia nie istnieje, program wyświetli (wtedy) odpowiedni komunikat." PROGRAM C++

ćwicz.4 str. 44

"Informatyka na czasie 3" (podręcznik dla absolw. szkół podstawowych, zakres rozszerzony)

Answer 1

Nie jest dla mnie jasne z polecenia co mają robić/zwracać dane funkcje czy struktury w tym fragmencie programu ani w jakiej formie, więc to co wyslalem w zalaczniku to po prostu program ktory znajduje najkrotsze sciezki przez wywolanie bfs i wypisuje labirynt z zaznaczona jedna z najkrotszych sciezek.

Krotkie objasnienie funkcji jesli nie sa jasne:

printpair() - nie uzywana nigdzie, wypisuje 2d vector par

is_valid() - sprawdza czy dana pozycja jest poprawna, tzn czy nie wyszedłem poza labirynt, czy nie wszedłem w ścianę itp.

bfs() - w miarę standardowa implementacja bfs,

move_vectors, zawiera wszystkie mozliwe ruchy(zakladajac, ze nie moge poruszac się "na skos" ) zeby nie musieć w głównej pętli pisać 4 warunków, a po prostu iterować po możliwych ruchach {for(pair<int, int> move : move_vectors) }

shortest_path_position() - przechodzę po brzegu labiryntu i znajduje w distance_tab (utworzoną przez wywołanie bfs) najmniejszą odleglosc

print_shortest_path() - "główna" funkcja która wywołuje bfs i shortest_path_position, wypisuje labirynt z zaznaczona najkrotsza sciezka unordered_map jest tu uzyte ponieważ pozwala na wkładanie elementów w czasie stałym oraz sprawdzanie czy istnieje dany element w czasie stałym, można zamienić na tablice 2 wymiarową on_path[a][b],

w której on_path[x][y] mówi nam czy pozycja (x,y) znajduje się na najkrótszej ścieżce

Jakby coś było nie jasne to chętnie odpowiem na pytania :)