Algorytmika - grafy i oś współrzednych

pytanie zadane 10 listopada 2016 w Algorytmy przez BlueWee Użytkownik (730 p.)

Cześć.

Mamy podane przykładowe punkty na osi współrzędnych x,y:

Przechodzić między punktami można tylko chodząc w poziomie lub pionie. Czyli przykładowo z miejsca 1,2 mogę dojść do 2,3, ale do 3,4 nie dojdę już z żadnego punktu.

Jak sprawdzić czy z punktu o współrzędnych x,y dojdę do punktu x, y?

2 odpowiedzi

odpowiedź 10 listopada 2016 przez Evelek Nałogowiec (28,960 p.)
wybrane 11 listopada 2016 przez BlueWee

Najlepsza

Może w ten sposób:

Wybieramy punkt początkowy (x,y), np. (1,1) i ustawiamy go jako np. "obecny punkt w którym się znajdujemy". Sprawdzamy czy na pozycjach obok niego, czyli możliwych ruchach, czyli: (1+x, y) lub (x, y+1) lub (x-1, y) lub (x, y-1) leży jakiś punkt i sprawdzamy jednocześnie czy punkt który otrzymamy jest równy naszemu punktowi końcowemu. Jeśli tak jest, to mamy koniec algorytmu. Jeśli nie, to sprawdzamy czy na którymś z tych czterech możliwych do otrzymania ruchów leży kolejna kropka. Jeśli nie, to mamy po zadaniu, mamy brak dalszych ruchów. Jeśli leży tak jak w Twoim przykładzie i jest nią punkt (1,2) to przypisujemy zmiennej "obecny punkt w którym się znajdujemy" te właśnie wartości (1,2). Potem deklarujemy, że nie będzie możliwy powrót do punktu (1,1), czyli: jeśli (x, y+1) == "punkt_znajdujący_się_na_osi to --> przy następnym sprawdzaniu możliwych ruchów nie bierzemy pod uwagę ruchu (x, y-1). Dodatkowo zapamiętujemy, które kropki były już sprawdzane. Jest to warunek konieczny, bo jeśli kropki będą ustawione w kwadracie jedna obok drugiej to jedna będzie ciągle znajdować tę samą.

Dalej mamy powtarzanie się tych czynności aż do momentu, kiedy znajdziemy kropkę końcową lub tak jak w Twoim przykładzie, dojdziemy do kropki (2,3) i okaże się, że po sprawdzeniu ruchów (1+x, y) lub (x, y+1) lub (x, y-1) nie znajdziemy żadnej kropki lub tą, po której się poruszaliśmy już wcześniej.

komentarz 11 listopada 2016 przez BlueWee Użytkownik (730 p.)

Powiem szczerze, że nie do końca rozumiem. :D

A czy na początku jeśli punkty będą z dwóch stron to algorytm chyba przejdzie tylko do jednego z nich?

komentarz 11 listopada 2016 przez Evelek Nałogowiec (28,960 p.)

Hmm jak to z dwóch stron? Podaj przykład. I czy ten algorytm ma być napisany w jakimś języku czy opisany słownie?

komentarz 11 listopada 2016 przez BlueWee Użytkownik (730 p.)

Algorytm ma być napisany w języku C++.

Przykładowo punkt startowy to 2,1, a dwa najbliższe punkty to 1,1 oraz 3,1. I w pierwszym kroku mamy punkty z dwóch stron. :D

komentarz 11 listopada 2016 przez Evelek Nałogowiec (28,960 p.)

Tego nie uwzględniłem. Czyli będą 2 możliwe drogi. Będzie trzeba to odpowiednio zaplanować w programie, reszta się nie zmieni.

komentarz 11 listopada 2016 przez BlueWee Użytkownik (730 p.)

Właśnie zastanawiam się jak.
Ale dziękuję za pomoc, jest już jakiś postęp.

1	komentarz 11 listopada 2016 przez Evelek Nałogowiec (28,960 p.) Pomógłbym napisać ten algorytm, bo lubię takie rzeczy, ale kolokwia na uczelni mam w ten weekend. Powodzenia!

komentarz 11 listopada 2016 przez Paweł Głomski Obywatel (1,650 p.)

Najkrótsza droga

Nie wiem, czy potrzebna Ci akurat najkrótsza droga, ale na pewno nie zaszkodzi Ci przejrzenie działania tych algorytmów.

komentarz 11 listopada 2016 przez Evelek Nałogowiec (28,960 p.)

Myślałem o tym, aby to podpowiedzieć koledze, ale raczej zbyt skomplikowane to będzie np. http://eduinf.waw.pl/inf/alg/001_search/0138.php Algorytm Dijkstry.

komentarz 11 listopada 2016 przez Paweł Głomski Obywatel (1,650 p.)

Na youtube jest pełno wyjaśnień działania tych algorytmów, a i implementacja na pewno się gdzieś znajdzie. Jeśli autor tematu ogarnia w miarę tego C++, to powinien dać radę stworzyć własną implementację jednego z tych algorytmów z samą listą kroków.