'Twas brillig when bartekLTG wrote:
[...]
> Punkty siatki sa weirzcholkami grafu, oznaczone na 'tak'
> kreski są krawedziemi grafu.
> Zalozmy, ze dorysowujesz krawedz miedzy wierzcholkami
> a i b ( (n,m) --- [(n+1,m) lub (n,m+1)] )
> Kiedy zamykami petle? Wtedy, gdy _przed_ dodaniem
> naszej krawedzi istnieje polaczenie miedzy a i b.
> Wystarczy wiec, ze sprawdzisz, czy istnieje polaczenie
> miedzy a i b. Jest to dosc czesto spotykane zagadnienie;)
> Algorytm nazywa sie 'przeszukiwanie drzewa w szerz'
> (Breadth-first search, w skrócie BFS) jest dobrze
> opisany w ksiezkach i sieci. Dlaczego 'w szerz' a nie
> 'w glab'? ze wzgledu na pesymistyczna ilosc operacji.
> Jesli najkrotsza sciazka ma dlugosc L, to odwiedzisz
> nie wiecej niz max(4L^2,M) a M to liczba wierzcholkow
> do ktorych mozesz dojsc;)
> Algorytm zybszy i prostrzy w implementacji niz proponowana
> obok Dijkstra, potrzebujesz jedynie kolejki fifo, czyli
> zwyklej listy.
> Bieresz element z kolejki i wrzucasz do kolejki
> wszyskich sasiadow (wierzcholki, do ktorych masz bezposrednie
> polaczenie krawedzią 'tak'), przy okazji sprawdzajac,
> czy to nie jest nasz cel i czy nie byl 'odhaczony' (tych
> nie wrzucasz). Wrzucane wierzcholki zaznaczamy jako 'odhaczone'
> W pierwszym kroku wrzucasz do kolejki wierzcholek startowy.
> BTW, Mozna to jeszcze zbic (do 2L^/2) idac na zmiane jedno
> pietro z wierzcholka 'a' - jedno pietro z wierzcholka 'b'
> i czekac na spotkanie, ale algorytm robi sie ciut bardziej
> skomplikowany.
> pzodrawiam
> bartekltg

Bartku, Maćku,

Dzięki za cenne uwagi. Poczytałem o BFS (a przy okazji innych algorytmach
związanych z grafami) i przemyślałem wasze propozycje. W efekcie końcowym
zdecydowałem się na uproszczone (ze względu na zasady łamigłówki)
rozwiązanie. Poniżej pseudo algorytm:

1.Ustaw koordynaty wierzchołka A jako początkowe, wierzchołka B jako
końcowe. Wyklucz odcinek AB
2.PETLA:
- sprawdź wszystkie narysowane odcinki z początkowego wierzchołka.
- wybierz pierwszy niewykluczony
- jeśli nie ma niewykluczonego odcinka:
- jeśli koordynaty bieżącego wierzchołka i wierzchołka B są zgodne to
PETLA ZAMKNIĘTA,
jeśli nie to PETLA OTWARTA. Wyjdź z funkcji.
- w przeciwnym razie:
- przejdź do nowego wierzchołka
- wyklucz pokonany właśnie odcinek
- ustaw nowe koordynaty początkowe
- wróć na początek pętli

Pozdrawiam,
Kiełpiś




--
Był czas mrutszławy, ślibkie skrątwy Tomasz Kiełpiński
Na wałzach wiercząc świrypły, a.k.a. "Kiełpiś"
A mizgłe do cna borogłątwy Odpowiadając prywatnie,
I zdomne świszczury zgrzypły. usuń: FALSZYWY z adresu