Połączenie między punktami

pytanie zadane 27 listopada 2016 w Algorytmy przez ProgramistaStepek Nałogowiec (27,020 p.)

Witam. Szukam pomocy w sposobie rozwiązania problemu. Do rzeczy: Jak sprawdzić czy między dwoma punktami w układzie współrzędnych jest połączenie? Zasada jest taka, między dwoma punktami z tą samą pierwszą lub drugą współrzędną np.(1,2) i (1, 6). Jest połączenie a między (3,4) i (5,8) nie ma. Problem nie jest tak trywialny jakby się zdawał a google milczy (albo to ja nie wiem jak znaleźć).

Punktów podanych może być więcej niż dwa np. (1,2), (2,2), (2,3). Trzeba zauważyć, że mimo, iż teoretycznie między punktem pierwszym i trzecim nie ma połączenia, ale "łącznikiem" jest punkt drugi.

komentarz 27 listopada 2016 przez adrian17 Mentor (354,120 p.)

Czy jak masz dane punkty A, B, C, D, E to konkretnie pytanie brzmi "czy punkty A i E są połączone po kolei łącznikami B, C, D" czy "czy istnieje jakiekolwiek połączenie między A i E"?

komentarz 27 listopada 2016 przez ProgramistaStepek Nałogowiec (27,020 p.)

Pytanie: Czy istnieje połączenie między punktami A i B?

1	komentarz 27 listopada 2016 przez adrian17 Mentor (354,120 p.) I punktów może być dowolnie dużo (np. 10000), tak? No to ja bym skonstruował graf łączący "połączone" punkty po czym zastosował prosty algorytm szukania drogi, pewnie BFS.