Witam!
TO NIE JEST ŻADNE ZADANIE NA ZALICZENIE
Jest sobie powierzchnia, załóżmy płaska, utworzona z punktów równomiernie rozłożonych po X i po Y (jak kartka w kratke :) ), wybieram na niej dwa dowolne punkty z siatki. Jak obliczyć wszystkie możliwe trasy z jednego punktu do drugiego? Można przemieszczać się po bokach kwadracików i po przekątnych. Jakie macie pomysły?
Jeśli nie zabraniasz odwiedzać ponownie tych samych punktów lub powierzchnia jest nieograniczona, to jest liczba ścieżek.
Powierzchnia jest ograniczona. Jedna trasa - to droga z punktu A do B, która może się przecinać, a więc mieć punkty, które powtarzają się. Odcinki drogi nie mogą się powtarzać.
"Trochę" tych możliwości jest, ale przy ograniczonej powierzchni, nie ma ich nieskończenie wiele. Tylko jak napisać algorytm do wyliczenia wszystkich tras?
Twoja powierzchnia to nic innego jak skończony, planarny graf nieskierowany. Takie grafy daje się przeszukiwać standardowymi algorytmami DFS (wgłąb) i BFS (w szerz). Do Twojego celu dobrze będzie się nadawał DFS, tyle że trzeba go troszkę zmodyfikować. Przede wszystkim musisz wywalić zaznaczanie i sprawdzanie odwiedzonych węzłów, żeby możliwe były przecięcia oraz żeby w wyniku zwrócił Ci wszystkie możliwe ścieżki (ścieżka nr 2 może mieć przecież te same niektóre węzły co ścieżka 1, itd.).
Musisz też dodać sprawdzanie, aby nie próbował tworzyć ścieżki z powtórzonymi krawędziami. To jest proste do zrobienia, bo na stosie masz zawsze zapisaną całą bieżącą ścieżkę, czyli wiesz jakie krawędzie już są.
Ostatnia modyfikacja to w miejscu, gdzie jest warunek stopu klasycznego DFS, czyli że został znaleziony węzeł docelowy, umieszczasz zapisanie bieżącej ścieżki do zbioru wyników oraz nie zatrzymujesz algorytmu, tylko jedziesz dalej dopóki się da.
Uwaga: algorytm ma złożoność wykładniczą O(a^n), bo liczba ścieżek rozwiązazania rośnie wykładniczo ze wzrostem grafu. Czyli zapomnij o grafach 100 x 100. Jest to niestety złożoność optymalna. Ale taki postawiłeś problem.
Dzięki za pomoc! Tak właśnie myślałem, tylko nie wiedziałem się jak to się nazywa :)