Szukanie ścieżki między bokami tablicy

0

Witam!
Mam problem z pewnym zagadnieniem.
Chcę napisać program, którego jedna z funkcji będzie sprawdzanie czy odpowiednie boki tablicy 2D są jakoś połączone ze sobą tymi samymi znakami.
Aby wszystko było jaśniejsze dołączam rysunek poglądowy w załączniku.
Chodzi o takie połączenia boków w tablicy dwuwymiarowej.
Szukałem podobnych tematów, ale żaden z nich specjalnie mi nie pomógł, chociaż pewnie dowiem się, że nie potrafię obsługiwać wyszukiwarki i zostanę obrzucony inwektywami proszę o choćby najmniejszy zalążek pomocy.

0

Generalnie to jest trywialny problem. Ta twoja tablica to jest graf nieskierowany w którym krawędź między dwoma wierzchołkami wystepuje jesli przylegają do siebie i mają tą samą liczbę. Musisz puścić sobie dowolny algorytm szukania ścieżki z punktów na boku i zobaczyć czy dojdziesz do drugiego. BFS pewnie będzie najłatwiejszy w implementacji tutaj.
http://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz

0

Dzięki za pomoc.
Jeśli mógłbym prosić o jeszcze o pomoc z rozpoczęciem.
Jak dokładnie trzeba zacząć, o co chodzi w tym algorytmie.
Zaczynam przygodę z algorytmami i dlatego początki mogą być dla mnie problematyczne.
Oto z czym potrzebuję pomocy:
Mam tablicę dwuwymiarową char, co trzeba zrobić z tym fantem, aby przystosować ją do BFS.
Z tego co wyczytałem muszę stworzyć nową tablicę gdzie będę zaznaczał odwiedzone komórki tablicy i dalej magicznie wyszukać drogę.
Rozwiązanie jest pewnie jak mówiłeś "trywialne", ale dotychczas nie potrzebowałem takich algorytmów, dlatego proszę o wyrozumiałość.

1

Druga tablica sie przyda, to fakt.
Potrzebujesz jeszcze dodatkowo listę (std::list) par (std::pair)
A sam algorytm będzie dość prosty.
Wybierasz sobie jakis wierzchołek początkowy (x,y) i dodajemy go do naszej listy.

Następnie w pętli, dopóki w liście jest jeszcze jakis element:

  • zabierasz element z listy
  • oznaczasz go jako "odwiedzony" w tej dodatkowej tablicy
  • sprawdzasz sobie warunek "końca", tzn w twoim przypadku czy to co właśnie zdjęliśmy z listy nie jest "po drugiej stronie", jeśli jest to koniec a jeśli nie:
  • rozchodzisz się z niego tam gdzie możesz, czyli do tablica[x-1][y], tablica[x][y-1], tablica[x+1][y], tablica[x][y+1]. Jeśli taki element tablicy istnieje (tzn na przykład x-1 nie jest mniejsze od 0 etc) i jednocześnie ma taką samą liczbę jak wierzchołek z którego przyszliśmy to dodajemy sobie do naszej listy współrzedne tego wierzchołka.

Oczywiście po zakończeniu tej pętli powinieneś sprawdzić w tablicy odwiedzonych czy nie ma jeszcze jakiegoś innego potencjalnego wierzchołka startowego i jeśli jest to odpalasz algorytm na nowo z niego.

1

Powiedz jak brzmi zadanie.
Czy szukasz tą ścieżkę bo tak brzmi zadanie czy realizujesz tą grę?
Bo jeżeli realizujesz grę to algorytm jest bardzo prosty.

  1. Kolorów czerwonych są trzy ten górny C1, ten dolny C2 i nowy wstawiany C3 (na ekranie mogą być takie same)
  2. Kolorów niebieskich są trzy ten lewy N1, ten prawy N2 i nowy wstawiany N3 (na ekranie mogą być takie same)
  3. Jeżeli kolejny wstawiony x3 (x to C lub N) ma sąsiadów:
    • x1 oraz x2 to koniec - wygrana
    • tylko x1 - sam się staje koloru x1 i rekurencyjnie farbuje wszystkich sąsiadów x3 na x1
    • tylko x2 - sam się staje koloru x2 i rekurencyjnie farbuje wszystkich sąsiadów x3 na x2
      koniec algorytmu.
0

Mam napisać program, który dostaje przykładową mapę np.
---
--< r >--
--< r >-< b >--
--< r >-< >-< b >--
--< r >-< >-< b >-< b >--
--< r >-< r >-< b >-< >-< b >--
--< b >-< r >-< r >-< b >-< r >-< b >--
--< b >-< r >-< r >-< r >-< r >-< r >-< b >--
--< r >-< b >-< >-< >-< r >-< b >-< >-< b >--
--< r >-< b >-< b >-< b >-< >-< r >-< r >-< b >-< r >--
--< b >-< b >-< r >-< r >-< >-< b >-< r >-< b >-< r >-< >--
< >-< >-< r >-< b >-< b >-< r >-< b >-< r >-< r >-< b >-< r >
--< r >-< b >-< b >-< >-< r >-< b >-< r >-< r >-< >-< b >--
--< >-< b >-< r >-< >-< r >-< b >-< b >-< r >-< b >--
--< r >-< b >-< b >-< r >-< r >-< r >-< r >-< b >--
--< >-< r >-< b >-< b >-< b >-< >-< r >--
--< r >-< r >-< r >-< b >-< r >-< b >--
--< b >-< r >-< b >-< b >-< b >--
--< b >-< >-< r >-< r >--
--< b >-< b >-< r >--
--< r >-< b >--
--< b >--
---
Ta akurat ma max. możliwy rozmiar 11x11.
Jednym z zadań jest funkcja znajdowania czy gra się skończyła, czyli czy istnieje ścieżka od jednego do drugiego boku.
Taką mapkę wczytuję do tablicy 2D z pktem. [0][0] w rogu z lewej.
Następna funkcja to sprawdzanie, czy gracz podanego koloru może wygrać w 1-2 ruchach przy najgorszych/najlepszych ruchach i tam chyba się przyda jakieś wstawianie, a z tego co do mnie napisałeś zrozumiałem tylko tyle, że to o co zapytałem jest śmiesznie łatwe i mogę sobie kolorować klocki. :)

0

No to:

  1. Dla wiersza 0 każdą b zastępujesz na 1
  2. Dla wiersza 10 każdą b zastępujesz na 2
  3. Każdą b sąsiadującą z 1 zamieniasz na 1, powtarzasz to dopóki możesz zamieniać
  4. Każdą b sąsiadującą z 2 zamieniasz na 2, powtarzasz to dopóki możesz zamieniać
  5. Jeżeli jakaś 1 sąsiaduje z 2 to jest wygrana
  6. Każdą 1 zamieniasz na b
  7. Każdą 2 zamieniasz na b
    Tak samo dla r
0

Dziękuję za pomoc. Faktycznie było to łatwe, ale skoro miałem z takim problemem pierwszy raz do czynienia to mogło mi to sprawiać kłopot.
Przy okazji zapytam jeszcze, jak można znajdować kiedy na takie mapie są np. więcej niż jedna ścieżka wygrywająca?
Przykładowa mapa:
---
--< b >--
--< b >-< b >--
--< b >-< r >-< r >--
--< r >-< b >-< b >-< b >--
--< b >-< r >-< r >-< r >-< b >--
--< r >-< b >-< r >-< r >-< r >-< b >--
--< b >-< b >-< r >-< r >-< r >-< b >-< r >--
--< b >-< r >-< b >-< r >-< r >-< b >-< b >-< b >--
--< b >-< b >-< b >-< b >-< r >-< r >-< r >-< b >-< b >--
--< r >-< b >-< r >-< r >-< b >-< r >-< b >-< b >-< r >-< r >--
< r >-< b >-< b >-< b >-< b >-< b >-< b >-< r >-< b >-< r >-< r >
--< b >-< b >-< r >-< r >-< b >-< r >-< r >-< r >-< b >-< b >--
--< b >-< b >-< b >-< r >-< r >-< r >-< b >-< r >-< r >--
--< b >-< r >-< r >-< b >-< r >-< r >-< r >-< b >--
--< b >-< r >-< r >-< r >-< r >-< r >-< b >--
--< b >-< r >-< b >-< b >-< b >-< r >--
--< r >-< r >-< r >-< b >-< r >--
--< b >-< r >-< b >-< b >--
--< r >-< b >-< r >--
--< b >-< r >--
--< r >--
---
W jaki sposób można w takiej mapie, gdzie są 2 czerwone wygrywające ścieżki wyszukiwać ile tych ścieżek jest?

0

Sposób jest bardzo skomplikowany, jeżeli nie dajesz rady ze znalezieniem algorytmu dla sprawdzenia połączenia to nawet po jego przedstawieniu nie dasz rady go zaimplementować.

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