Szukanie ścieżki między bokami tablicy

Szukanie ścieżki między bokami tablicy
MA
  • Rejestracja:prawie 11 lat
  • Ostatnio:prawie 11 lat
  • Postów:8
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.

Shalom
  • Rejestracja:około 21 lat
  • Ostatnio:prawie 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
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


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
MA
  • Rejestracja:prawie 11 lat
  • Ostatnio:prawie 11 lat
  • Postów:8
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ść.

Shalom
  • Rejestracja:około 21 lat
  • Ostatnio:prawie 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
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.


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
_13th_Dragon
To heksy, więc: - "... tablica[x-1][y], tablica[x][y-1], tablica[x+1][y], tablica[x][y+1] ..." - jest nieścisłe oraz nie pełne.
Shalom
Przeoczyłem to :) ale to w sumie trywialna zmiana i autor sam powinien na nią wpaść jak tylko zrozumie algorytm :)
_13th_Dragon
  • Rejestracja:ponad 19 lat
  • Ostatnio:2 miesiące
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.

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
MA
  • Rejestracja:prawie 11 lat
  • Ostatnio:prawie 11 lat
  • Postów:8
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. :)

_13th_Dragon
  • Rejestracja:ponad 19 lat
  • Ostatnio:2 miesiące
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

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
MA
  • Rejestracja:prawie 11 lat
  • Ostatnio:prawie 11 lat
  • Postów:8
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?

edytowany 1x, ostatnio: maniuteq
_13th_Dragon
  • Rejestracja:ponad 19 lat
  • Ostatnio:2 miesiące
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ć.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)