-
Data: 2009-01-23 10:00:19
Temat: Re: Zamknięta pętla
Od: Tomasz Kiełpiński <F...@p...onet.pl> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]'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
Następne wpisy z tego wątku
- 23.01.09 16:17 Maciej Piechotka
- 24.01.09 05:49 bartekLTG
- 29.01.09 10:42 Tomasz Kiełpiński
Najnowsze wątki z tej grupy
- Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- We Wrocławiu ruszyła Odra 5, pierwszy w Polsce komputer kwantowy z nadprzewodzącymi kubitami
- Ada-Europe - AEiC 2025 early registration deadline imminent
- John Carmack twierdzi, że gdyby gry były optymalizowane, to wystarczyły by stare kompy
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2025
- Linuks od wer. 6.15 przestanie wspierać procesory 486 i będzie wymagać min. Pentium
- ,,Polski przemysł jest w stanie agonalnym" - podkreślił dobitnie, wskazując na brak zamówień.
- Rewolucja w debugowaniu!!! SI analizuje zrzuty pamięci systemu M$ Windows!!!
- Brednie w wiki - hasło Dehomag
- Perfidne ataki krakerów z KRLD na skrypciarzy JS i Pajton
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- U nas propagują modę na SI, a w Chinach naukowcy SI po kolei umierają w wieku 40-50lat
- C++. Podróż Po Języku - komentarz
Najnowsze wątki
- 2025-07-05 Shrek, wzrośnie cena prądu :-)
- 2025-07-05 Warszawa => Senior Frontend Developer (React + React Native) <=
- 2025-07-05 Środa Wielkopolska => SAP FI/CO Internal Consultant <=
- 2025-07-05 Środa Wielkopolska => SAP FI/CO Konsultant wewnętrzny <=
- 2025-07-06 Płacić za wodę ze studni
- 2025-07-06 Kolejny inżynier...
- 2025-07-05 UE ustępuje pod presją Trumpa. Socjaldemokraci: oddaliśmy miliardy
- 2025-07-04 od kiedy można obrażać Plastusia i do kiedy Batyra?
- 2025-07-05 UE ustępuje pod presją Trumpa. Socjaldemokraci: oddaliśmy miliardy
- 2025-07-03 Trybik
- 2025-07-04 Renault Symbioz
- 2025-07-04 Architektura IIIRP: Wyjątkowa, a prymitywniejsza niż stodoła pod zaborami
- 2025-07-04 Warszawa => International Freight Forwarder <=
- 2025-07-04 Wrocław => SAP ABAP Developer <=
- 2025-07-04 Warszawa => Mid/Senior IT Recruiter <=