• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Połączenie między punktami

VPS Starter Arubacloud
0 głosów
463 wizyt
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 Ekspert (348,220 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 Ekspert (348,220 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.
komentarz 27 listopada 2016 przez ProgramistaStepek Nałogowiec (27,020 p.)
O właśnie o to mi chodziło :) Dzięki ☺️
komentarz 28 listopada 2016 przez Jakub Śliż Użytkownik (940 p.)

A jak miałby wyglądać owy graf? frown

 

komentarz 29 listopada 2016 przez playerony Pasjonat (15,220 p.)

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
1 odpowiedź 544 wizyt
0 głosów
3 odpowiedzi 2,978 wizyt
pytanie zadane 6 lipca 2017 w Python przez DODO Bywalec (2,950 p.)
0 głosów
1 odpowiedź 1,206 wizyt
pytanie zadane 15 kwietnia 2017 w JavaScript przez Neespa Początkujący (300 p.)

92,838 zapytań

141,780 odpowiedzi

320,843 komentarzy

62,171 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...