Pełna izolacja

5 lipca 2010
Marek Penszko

W komentarzach do poprzedniego wpisu Karzymowi „coś nie pasuje” 🙂 . I słusznie. Podejrzewam, że wielu osobom nie pasuje umieszczone w regułach nurikabe stwierdzenie: grobla stanowi jeden wielokąt, skoro w tym wielokącie są otwory w postaci stawów. Jeśli przyjąć „klasyczną” definicję wielokąta (figura płaska ograniczona linią łamaną zamkniętą, nie przecinającą samej siebie), to znajdujący się w nim otwór gryzie się z definicją. Aby przestał się gryźć, należałoby uwzględnić, że powyższa definicja dotyczy tzw. wielokąta prostego – jego dwa boki mają punkt wspólny tylko wówczas, gdy są kolejnymi odcinkami łamanej. Jeżeli nie ma tego ograniczenia, czyli dowolne odcinki łamanej mogą mieć punkty wspólne, wówczas pojawiają się wielokąty złożone, czyli np. taki:

Ten wielokąt odpowiada grobli w zadaniach nurikabe. Zawiera otwory, które stykają się z jego brzegiem lub/i ze sobą.

Może się jednak zdarzyć, że jakiś staw nie będzie dotykał ani innego stawu, ani brzegu grobli, czyli jego odpowiednikiem będzie otwór w wielokącie:

Czy szary obszar to wielokąt? W geometrii obliczeniowej, ściśle związanej z grafiką komputerową, odpowiedź jest twierdząca. Taki „twór”  zawierający otwór zalicza się do wielokątów złożonych. Można nawet sprytnie wykazać, że stanowi figurę płaską ograniczoną linią łamaną zamkniętą, ale… inaczej:

Gdy połączymy dwa czerwone i dwa zielone punkty powstanie wielokąt jak na poprzednim rysunku. „Pępowina” łącząca otwór z obwodem nie jest istotna, bo można uznać, że należy ona, podobnie jak cała łamana, do wielokąta.

Mimo powyższych „spekulacji” byłoby jednak lepiej (mea culpa i ukłon w stronę Karzyma) nie kojarzyć grobli z wielokątem, tylko napisać: grobla tworzy spójny obszar.
Staw lub grupa stawów (stykających się rogami) w nurikabe bardzo rzadko nie dotyka brzegu grobli, czyli jest przez nią całkowicie otoczona. Jeśli tak się zdarza, to z reguły w pełni odizolowane stawy są małe, złożone z jednej lub dwóch kratek (tak jest np. w dwu z trzech zadań zamieszczonych w Omnibusie). Poniżej znajdują się dwa inne zadania ze stawami-otworami w grobli, także z większymi. Duże nurikabe jest trudne, a małe też nie pestka, więc daję Państwu (i sobie) nieco więcej czasu, czyli następny wpis w piątek.

W rozwiązaniu każdego zadania wystarczy podać wielkość i położenie stawów i grup stawów całkowicie odizolowanych groblą.

Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3-4 dni.