Wykrywanie sekwencji węzłów w siatce

Biorąc pod uwagę poniższy obraz, muszę wykryć najbardziej optymalną sekwencję na planszy (zielona linia). Niebieskie / czerwone linie przedstawiają możliwe, ale nie najlepsze ruchy.

Oto zasady:

1. Możesz przejść do dowolnego kafelka, który jest taki sam i jest twoim sąsiadem (przekątna jest ważna)
2. Po odwiedzeniu kafelka nie można go ponownie odwiedzić.

Pomyślałem o zapętleniu każdego węzła i spojrzeniu na sąsiadów, a następnie przejściu rekurencyjnym. Gdy znajdę możliwy ruch, mogę umieścić go w strukturze. Po znalezieniu wszystkich możliwych ruchów wybieram ruch o największej liczbie węzłów. Staje się trudniejsze, gdy węzeł ma więcej niż jednego pasującego sąsiada.

Czy jest jakiś algorytm, którego mogę użyć? Myślałem o wypełnieniu powodziowym, ale to nie spełnia zasad # 2.

Zgodnie z życzeniem, oto film o podobnej rozgrywce. http://youtube.com/watch?v=eumnCTG0AE8

Możesz rozważyć każdą grupę połączonych identycznych symboli (a przez połączone mam na myśli, że możesz podróżować od jednego symbolu do drugiego) osobny wykres . Dla każdego takiego wykresu zastosuj głębokie pierwsze wyszukiwanie (DFS), rozpoczynając od każdego węzła na wykresie, który nie jest już częścią najdłuższej ścieżki dla tego wykresu . Za każdym razem, gdy dochodzisz do ślepej uliczki podczas stosowania DFS, sprawdź, czy ścieżka, którą właśnie przeszedłeś, jest dłuższa niż globalne maksimum, które znalazłeś do tej pory. Jeśli tak, zapisz go jako nową najdłuższą ścieżkę.

Zauważysz, że w poprzednim akapicie wspominałem o wielokrotnym stosowaniu DFS dla każdego wykresu. Pojedynczy DFS działający na wykresie nie wystarczy. Rozważ ten konkretny przypadek:

    1
1 1 1
    1
    1
    1
    1

Jeśli przypadkiem najpierw uruchomisz DFS na tym wykresie w najwyższym węźle, odkryjesz najdłuższą możliwą ścieżkę jako linię pionową, ale to nie byłoby poprawne. Dzieje się tak za każdym razem, gdy uruchamiasz algorytm DFS w węźle, który jest gdzieś wewnątrz ścieżki wynikowej lub w ogóle nie jest jego częścią. W tym konkretnym przykładzie musisz także uruchomić algorytm DFS od lewego najbardziej węzła w drugiej linii. To znajdzie właściwą ścieżkę. Ogólnie rzecz biorąc, musisz uruchomić algorytmy DFS w każdym węźle, który nie jest obecnie częścią najdłuższej ścieżki dla tego wykresu, jak wspomniano powyżej.

Absolutnie gorszym scenariuszem dla tego algorytmu byłaby tablica wypełniona lub w większości wypełniona jednym typem symbolu, jednak jest to mało prawdopodobne w grze. Uważaj też, jak przechowywać najdłuższe ścieżki dla każdego wykresu. Jeśli nie zoptymalizujesz tego bitu, lepiej byłoby po prostu wywołać DFS dla każdego węzła na scenie. Zakładając, że nie pracujesz z bardzo dużymi płytami i że prędkość nie jest tak dużym problemem, to rozwiązanie powinno być wystarczająco szybkie.

Technicznie rzecz biorąc, dzieląc tablicę na osobne wykresy, powstaje wiele „ problemów z najdłuższą ścieżką ”. Jak widać z twojego przykładu, możesz mieć cykle na swoim wykresie (na przykład mając wszystkie symbole na zewnątrz sceny tego samego typu), co oznacza, że ​​w tym konkretnym problemie musisz znaleźć najdłuższą ścieżkę na kilku cyklicznych niekierowanych grafach, czego nie można zrobić w czasie wielomianowym .

Jeśli okaże się, że jest to zbyt wolne, zapoznaj się z odpowiedzią na StackOverflow, aby uzyskać więcej informacji na temat optymalizacji poszczególnych „najdłuższych problemów z ścieżką”.