Maski bitowe

03.10.2009 - Damian Rusak
TrudnośćTrudnośćTrudność

Płytki na planszy

Kolejnym rozpatrywanym zadaniem będzie zadanie następującej treści:


Na zadanej prostokątnej szachownicy niektóre pola wypełniono płytkami $ 1 \times 1 $. Nazwijmy te pola "zablokowanymi". Twoim zadaniem jest wypełnić całą pozostałą przestrzeń płytkami rozmiaru $ 2 \times 2 $ i $ 1 \times 1 $, tak by nie kolidowały ze sobą i z polami zablokowanymi. Za każdą umieszczoną płytkę rozmiaru $ 2 \times 2 $ otrzymujesz $ 16 $ punktów, a za każdą płytkę rozmiaru $ 1 \times 1 $ $ 1 $ punkt. Ile najwięcej punktów możesz uzyskać? Rozmiar szachownicy nie przekroczy w żadnym z wymiarów dwudziestu.


Przykład:


 
Przede wszystkim musimy zauważyć, że rozwiązanie zachłanne nie jest poprawne - nie możemy umieszczać płytek $ 2 \times 2 $ wszędzie tam, gdzie się da, gdyż jedną taką płytką możemy zablokować miejsce dla kilku innych.


W takim razie powstaje pomysł na rozwiązanie dynamiczne. Najistotniejszą częścią rozwiązania tego zadania jest znalezienie sposobu na sprytną reprezentację stanów, które chcemy wykorzystać w dynamicznym rozwiązaniu.


Niech plansza ma wymiary $ H $ na $ W $ (wysokość na szerokość). Zauważmy, że największa z możliwych do użycia płytek ma rozmiar $ 2 \times 2 $, więc jest niewielka. Dlatego możemy szukać rozwiązań częściowych, wypełniając planszę np. z lewa na prawo, przeglądając kolejne kolumny. Gdy koncentrujemy się na piątej kolumnie, możemy już zapomnieć o kolumnach 1,2, 3 - płytki, które pokrywają jakiekolwiek pola z piątej kolumny nie mogą już mieć wpływu na kolumny oddalone o co najmniej 2 jednostki. W obec tego w rozwiązaniu dynamicznym będziemy zakładać, że gdy rozpatrujemy pewną kolumnę, to wszystkie kolumny oddalone o co najmniej 2 w lewo są już w pełni pokryte. Dzięki temu nasza reprezentacja stanu będzie brała pod uwagę jedynie dwie ostatnie kolumny rozpatrywanego fragmentu szachownicy.

Teraz zastanówmy się, jak reprezentować stan tych dwóch kolumn. Musimy pamiętać o tym, że gdy rozpatrujemy kolumny $ k $ i $ k+1 $, to musimy pokryć w całości kolumnę $ k $. Za to kolumna $ k+1 $ może mieć pozostawione puste pola - do pokrycia przez płytkę 2x2 w momencie rozpatrywania kolumn $ k+1 $ i $ k+2 $. Musimy pamiętać też o polach zablokowanych.

Zauważmy, że jeśli rozpatrywalibyśmy każdą kolumnę z góry na dół, to w momencie, gdy przeglądneliśmy pewien górny fragment $ k+1 $ -ej kolumny (rozpatrujemy kolumny $ k $ i $ k+1 $), to pola w kolumnie $ k $ leżące na lewo od tego framentu muszą już być pokryte.
W takim razie moglibyśmy jako stan w tych dwóch kolumnach przyjąć sytuację, gdy podjeliśmy już decyzję, co zrobić z górnym fragmentem $ k+1 $ -ej kolumny (nazwijmy go $ F $), aż do pewnego wiersza $ w $. Wtedy musimy brać też pod uwagę pozostały fragment $ k $-tej kolumny (nazwijmy go $ G $), ale ten fragment „dopełnia” długość $ F $ do $ H $ (wysokości kolumny).

W takim razie możemy za pomocą maski bitowej reprezentować to, które pola z czerwonej części są pokryte, a które nie. Przez częściowe pokrycie będziemy rozumieli pokrycie, które dopuszcza niezajętość niektórych pól (do późniejszego pokrycia). Oznaczmy więc:

$ D\left[k\right]\left[w\right]\left[Y\right] $ - najlepsze (suma punktów) częściowe pokrycie fragmentu planszy, który jest całkowicie pokryty w kolumnach od 1 do $ k-1 $, oraz w kolumnie $ k $ od wiersza 1 do $ w $, oraz jego pokryciue w wierszach od $ w+1 $ do $ H $ w kolumnie $ k $ i wierszach od 1 do $ w $ kolumny $ k+1 $ wyznacza maska bitowa $ Y $.

Przykład maski bitowej na obrazku kilka wierszy niżej.


Oczywiście można wprowadzić łatwą optymalizację i pamiętać tylko wyniki dla ostatnich kolumn, ale dla uproszczenia rozumowania wprowadzimy tu pełną tablicę.


Teraz, jeśli będziemy przeglądali wiersze od góry, przy ustalonej kolumnie, będziemy mogli w łatwy sposób wyliczać dynamicznie najlepszy wynik dla każdej możliwej maski bitowej $ Y $.  Mamy bowiem dla każdego górnego fragmentu $ k+1 $-ej kolumny trzy możliwości - albo zakończył się płytką $ 2 \times 2 $ albo zakończył się płytką $ 1 \times 1 $, albo zakończył się pustym polem. Każda z tych możliwości wymaga dwóch rzeczy :


1. Sprawdzenia, czy to możliwe (tj. czy nie kolidowałoby to z polem zablokowanym), albo czy płytka $ 2 \times 2 $ mieści się w planszy (dla $ w = 1 $)
2. Obliczenia najlepszego wyniku, korzystając z wcześniej wyliczonych wartości dla poprzednich wierszy.


Rozwiązanie, którego szukamy, to $ D\left[W\right]\left[H\right]\left[2^{H-1}-1\right] $, czyli wypełniona plansza.


Szczegóły techniczne rozwiązania zostawiamy Czytelnikowi. Są one podobne do metod stosowanych w poprzedznich zadaniach - generowanie masek bitowych i operowanie na nich nie powinno sprawić większego problemu.


Przedstawione metody radzenia sobie z reprezentacją podzbiorów za pomocą masek bitowych często przydzają się przy rozwiązywaniu problemów algorytmicznych. Zachęcamy do wypróbowania tej metody!

 

Na następnych stronach znajdziesz dokładne treści zadań, których rozwiązania można wysłać do oceny!

 

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
5
Twoja ocena: Brak Ocena: 5 (7 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com