[J.....n]

Chyba mam jakieś braki w myśleniu, ale próbuję zrobić przeszukiwanie w głąb na tablicy n*m dla punktu x, y.
Wiem, że to jest tak, że sprawdzam sobie sąsiadów dookoła, nazwijmy ich: 1,2,3,4. Potem sprawdzam sąsiadów 1, potem sąsiadów 2, potem 3 i 4. Później sąsiadów sąsiadów 1, 2, 3, 4 itd. Wiadomo, że tylko te nieodwiedzone i inne tam zależności. Algorytm zdaje mi się, że znam, ale nie potrafię go zaimplementować. Pierwsza na myśl przychodzi mi rekurencja, ale jeśli zrobię coś takiego:
http://pastebin.com/a69QSjgV (na szybko napisane)
to to według mojego myślenia sprawdza najpierw 1, 2, 3, 4. Potem sąsiadów 1, np. 5, 6, 7, 8. Potem sąsiadów 5. Potem pierwszego sąsiada 5 itd... Mylę się? Jak to powinno być :I

#informatyka #programowanie #algorytmy

[Deggial]

@JustMMan: Algorytm dziala dobrze. Zamiast myslec o rekurencji mozesz pomyslec ze wkladasz wierzcholki na stos i kiedy skonczysz przetwarzac sasiadow odwiedzasz wierzcholek ktory jest na gorze stosu (i sciagasz go ze stosu).

[J.....n]

@Deggial: Tzn. ten algorytm co dałem działa w tym wypadku tak jak mówisz? tj. jak stos

[Deggial]

Tak. Zobacz te animacje to moze Ci pomoga (DFS to przeszukiwanie w glab). https://codeaccepted.wordpress.com/2014/04/08/depth-and-breadth-first-search/

[achr]

@JustMMan: To co napisałeś na początku to BFS. Jak sama nazwa wskazuje, w tym algorytmie chcesz iść 'wszerz', więc odwiedzasz sąsiadów w kolejności first-in first-out.