Tomasz Kiełpiński <F...@p...onet.pl> writes:

> 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.
>
> Pozdrawiam,
> Kiełpiś

Hmm. Czy nie dało by się potraktować tego jak grafu gdzie koszt
przejścia przez nieoznaczoną krawędz jest duży (np. X*Y*1000) a koszt
przejścia na przez zaznaczoną mały (np. 1)? Teraz szukasz optymalnej
drogi dla każdych z par punktów (tzn. 4 punkty więc 6 dróg) i znajdujesz
miminum. Jeśli wynosi ono X*Y*1000 (tzn przejście jest przez ten punkt)
to nie ma takiej pętli. Jeśli jest mniejsza to taka pętla istnieje.

Pozdrawiam

PS. Piszę tak jak rozumiem problem - nie znam tej łamigłówki.
--
I've probably left my head... somewhere. Please wait untill I find it.
Homepage (pl_PL): http://uzytkownik.jogger.pl/
(GNU/)Linux User: #425935 (see http://counter.li.org/)