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

> '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ś

To dobrze chyba zrozumiałem. Przejściu po linii daj koszt równy np. 1 a po
braku X*Y*1000 (albo nie dawaj - to zapewne zależy od konkretnego
algorytmu

Jak masz taką sytłację:

.__. .__.
| | | |
| | | |
. .__. .
| |
| |
.__.__. .

I sprawdzasz dla dolnego kwadratu czy istnieje droga poza tą krawędzią i
jaką ma długość (istnieje inna droga <=> jest pętla).

Tutaj jest droga o długości 11 < 3*4*1000 = 12000 więc zamykamy pętle.

. .__.__.
| |
| |
. . . .
| |
| |
.__.__. .

Tutaj najkrótszą drogą jest 3*4*1000 (dokładnie przez 'nowo zaznaczone'
pole [Albo - nie ma drogi]) więc nie zamyka to pętli.

A algorytmów wyszukiwania drogi w grafie jest mnówtwo - choćby na
wikipedii.

Pozdrawiam

PS. Brak rozgałęzień to wiedza czy wymóg? Jeśli wiedza to można iść po
koleji zaznaczonymi krawędziami aż do końca. Jeśli wymóg to przypisz
drogom z rozgałęzienia koszt 3*4*1000/uczyń nieprzechadzalnymi.
--
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/)