Tomasz Kiełpiński wrote:
> Witam,
>
> Przejrzałem archiwum grupy, pogooglałem, ale wszystko wskazuje na to
> że googlać nie umiem, bo nie wierzę żeby podobny temat nie był
> poruszany :)
> Szukam algorytmu albo wręcz metody matematycznej (mam cały czas
> nieodparte wrażenie, że problem da się rozwiązać na poziomie
> pierwszej klasy liceum) na sprawdzenie zamkniętej pętli. Chodzi o
> jeden z elementów progamu rozwiązującego łamigłówki SlitherLink
> (znane również jako Fences lub Pokropek)
>
> Mam daną tablicę dwuwymiarową, zawierającą informacje o każdym
> kwadraciku. Wymiary x,y określają położenie kwadracika na
> płaszczyźnie, natomiast w wartości zakodowane jest położenie kwadratu
> względem pętli (na zewnątrz lub wewnątrz) i stan każdego z jego boków
> (Jedna z trzech wartości: jest/nie ma/nie jest oznaczone)
>
> Jak sprawdzić/policzyć czy np. narysowanie górnej krawędzi w
> kwadraciku na pozycji 1,1 spowoduje domknięcie pętli.


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