'Twas brillig when Maciej Piechotka wrote:
> 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.

Dzięki Maćku za zainteresowanie.

Koncepcja brzmi dość ciekawie, ale (chyba?) nie spełnia moich oczekiwań.
Może spróbuję narysować o co chodzi?

Przykład I:
.___. .___.
| | | |
|1,1|2,1|3,1|
. .___. .
| |
|1,2 2,2 3,2|
.___.___. .


Przykład II:
. .___.___.
| |
|1,1 2,1 3,1|
. . . .
| |
|1,2 2,2 3,2|
.___.___. .

Z mojego punktu widzenia nie ma znaczenia czy brak linii wynika z ze stanu
"BRAK" czy ze stanu "NIE OZNACZONY" danej krawędzi kwadratu. W przykładzie
pierwszym umieszczenie linii na dole kwadratu 3,2 spowoduje zamknięcie pętli
(przy czym wszystkie kwadraty z wyjątkiem 2,1 będą wewnątrz tej pętli). W
drugim przypadku pętla pozostanie otwarta. Pętla nie rozgałęzia się
natomiast może na tym etapie rozwiązywania urywać się. Ogólnie można
powiedzieć, że chodzi o sprawdzenie czy istnieje jakakolwiek droga między
dwoma punktami.

Pozdrawiam,
Kiełpiś

--
Bzdr