Omówienie zadania Zamek (II etap XXIV OI)

Na początek zdefiniujemy kilka tablic, w których będziemy przechowywali wczytane dane. Na wejściu każda komnata jest reprezentowana przez współrzędne przeciwległych wierzchołków prostokąta. Nie jest jednak powiedziane, które są to wierzchołki, a wygodniej nam będzie pracować, jeśli będziemy to wiedzieć. Oznaczmy zatem przez \((x_L[i], y_D[i])\) lewy-dolny wierzchołek prostokąta \(i\)-tej komnaty, a przez \((x_P[i], y_G[i])\) prawy-górny wierzchołek. Wyznaczenie ich jest bardzo proste i możemy to zrobić podczas wczytywania danych prostokątów.

Z kolei położenie \(i\)-tego miejsca niebezpiecznego będziemy trzymali w komórce \((x_N[i], y_N[i])\). Wygodnie nam też będzie zapisać punkt początkowy w tych tablicach pod indeksem \(m+1\), a punkt ze skarbem pod indeksem \(m+2\). Wszystkie te \(m+2\) pozycji będziemy po prostu nazywali punktami.

Cała procedura wczytywania danych wygląda zatem następująco:

Zaczniemy od omówienia kilku rozwiązań nieoptymalnych. Każde z nich zakłada, że któreś z ograniczeń na wielkość danych jest niewielkie.

Rozwiązanie dla niedużych wymiarów mapy

Mapę zamku możemy reprezentować w prostokątnej tablicy \(d\) o wymiarach \(h \times w\). Komórka \(d[y,x]\) tej tablicy (dla \(0 \leq y < h\) i \(0 \leq x < w\)) odpowiada na mapie jednostkowemu kwadratowi o współrzędnych \((x,y)\) i \((x+1,y+1)\). Chcemy, aby w tej komórce znalazł się numer komnaty, do której należy ten kwadrat.

Najprostsze rozwiązanie przegląda poszczególne komnaty i dla każdej z nich wypełnia odpowiadające jej komórki w tablicy:

Następnie, używając tablicy \(d\), dla każdego z \(m+2\) punktów wyznaczamy numer komnaty, w którym znajduje się ten punkt. Dla punktu \((x,y)\) będzie to numer zapisany w komórce \(d[y,x]\). Możemy dzięki temu wyznaczyć tablicę, gdzie \(\mathit{bezpieczna}[i]\) oznaczać będzie, że do komnaty o numerze \(i\) można wejść:

W zadaniu musimy znaleźć drogę pomiędzy zadanymi punktami. Przy czym droga musi być w pewnym sensie „najkrótsza", tzn. przechodzić przez jak najmniejszą liczbę komnat. Gdy pojawia się problem najkrótszej drogi, naturalnym pomysłem jest użycie jakiegoś algorytmu przeszukiwania grafu. Tylko skąd wziąć graf?

Zwykle wierzchołki grafu reprezentują położenia, w których możemy się znaleźć, a krawędzie — możliwość przejścia między tymi położeniami. Moglibyśmy zatem skonstruować graf, którego wierzchołkami są wszystkie punkty na mapie albo wszystkie kwadraty jednostkowe. Byłoby to jednak dość kosztowne i to niepotrzebnie. Zauważmy bowiem, że jeśli jesteśmy w pewnym punkcie komnaty, to przejście do każdego innego punktu tej komnaty mamy „za darmo", tzn. nie zwiększa ono długości naszej drogi. Jedyny koszt, który ponosimy, to przejście pomiędzy różnymi komnatami, bo wtedy potencjalnie odwiedzamy nową komnatę.

Zatem nasz graf będzie miał \(n\) wierzchołków reprezentujących komnaty (wierzchołek \(v_i\) reprezentuje \(i\)-tą komnatę), a dla każdej pary komnat \(i\), \(j\), między którymi istnieje bezpośrednie przejście, dodamy do grafu nieskierowaną krawędź pomiędzy wierzchołkami \(v_i\) a \(v_j\). Robimy to w ten sposób, że dla każdej pary sąsiednich komórek tablicy o różnych numerach komnat dodajemy krawędź do grafu:

Zauważmy, że tak stworzony graf może mieć krawędzie wielokrotne (np. w przykładzie dodamy trzy krawędzie pomiędzy wierzchołkami \(v_1\) i \(v_5\)). Na razie jednak nie będzie to nam przeszkadzać, więc się tym nie przejmujmy.

Droga na mapie będzie odpowiadała teraz ścieżce w tym grafie. Chcemy więc znaleźć ścieżkę, która przechodzi przez jak najmniejszą liczbę wierzchołków. Zauważmy, że musi to być ścieżka prosta, tzn. taka, na której wierzchołki się nie powtarzają. Istotnie: gdyby bowiem najlepsza była ścieżka, na której dany wierzchołek występuje wielokrotnie, to moglibyśmy usunąć część ścieżki pomiędzy wystąpieniami tego wierzchołka, i dalej byłaby dobra.

Zatem ścieżka o najmniejszej liczbie wierzchołków to będzie tak naprawdę standardowa najkrótsza ścieżka w grafie. Do znalezienia jej możemy użyć zwykłego algorytmu przeszukiwania wszerz (BFS), korzystającego z kolejki \(Q\) i przechowującego najkrótsze odległości w tablicy \(\mathit{dist}\). Musimy przy tym pomijać wierzchołki komnat niebezpiecznych:

Oszacujmy złożoność czasową tego rozwiązania. Wczytywanie danych zajmuje czas \(O(n+m)\). Wypełnienie tablicy \(d\) kosztuje czas \(O(wh)\), gdyż każde pole wypełniamy raz (komnaty są rozłączne). Wyznaczanie komnat bezpiecznych to czas \(O(n+m)\). Konstrukcja grafu zajmuje czas \(O(wh)\), bo rozważamy każde pole tablicy \(d\). Utworzony graf ma \(n\) wierzchołków i potencjalnie aż \(O(wh)\) krawędzi (licząc krawędzie wielokrotne), zatem algorytm BFS będzie działał w czasie \(O(n+wh)\). Ostatecznie całkowita złożoność czasowa algorytmu to \(O(wh + n + m)\). To rozwiązanie liniowo zależy od wielkości mapy, zatem przechodzi jedynie podzadania 1 i 2.

Rozwiązanie dla niedużej liczby komnat i punktów

Zauważmy, że wąskim gardłem naszego poprzedniego algorytmu były operacje wymagające przejrzenia całej tablicy \(d\) oraz przeszukiwanie grafu komnat, który mógł mieć bardzo dużo wielokrotnych krawędzi. Zastanówmy się teraz, czy zastąpienie wielokrotnych krawędzi pojedynczymi ma szansę poprawić złożoność przeszukiwania grafu.

Kluczowe jest zaobserwowanie, że graf komnat jest grafem planarnym, czyli że możemy go narysować na płaszczyźnie w taki sposób, żeby jego krawędzie się nie przecinały. Nie jest to zaskoczenie: jeśli naniesiemy rysunek tego grafu na mapę, zaznaczając każdy wierzchołek wewnątrz odpowiadającej mu komnaty, to bez problemu narysujemy nieprzecinające się krawędzie. To jest miła wiadomość, bo znany jest fakt, że w grafie planarnym o \(n\) wierzchołkach liczba krawędzi nie przekracza \(3n\). Tak więc algorytm BFS zadziała w tym grafie w czasie \(O(n)\).

Potrzebujemy zatem innego sposobu wyznaczania grafu komnat, niewymagającego kosztownego przeglądania tablicy \(d\). Spróbujmy zatem inaczej sprawdzić, czy dla danej pary wierzchołków \(v_i\) i \(v_j\) istnieje pomiędzy nimi krawędź. Wprost z treści zadania dostajemy, że jest tak wtedy, gdy prostokąty komnat odpowiadających tym wierzchołkom dotykają się bokami. A jak sprawdzić takie dotykanie się?

Możemy sprawdzić, która z czterech par boków jest kandydatem na dotykanie (takie boki muszą leżeć na jednej prostej), a następnie możemy sprowadzić zadanie do sprawdzenia, czy odcinki boków zawarte w tej prostej przecinają się:

Przyda nam się zatem pomocnicza funkcja, która dla dwóch odcinków \((a_1, a_2)\) oraz \((b_1, b_2)\) leżących na prostej stwierdzi, czy mają one część wspólną dodatniej długości. W praktyce łatwiej jest sprawdzić, czy przecięcie nie jest puste:

Skonstruowanie grafu jest już teraz bardzo proste i działa w czasie \(O(n^2)\), gdyż sprawdzamy po prostu dla każdej pary wierzchołków, czy są one połączone krawędzią:

Pozostała kwestia wyznaczenia numerów komnat dla punktów. Skorzystamy tu z faktu, że również miejsc niebezpiecznych jest mało, i dla każdej pary komnata–miejsce sprawdzimy, czy punkt jest w prostokącie odpowiadającym komnacie. Takie wyznaczenie numerów komnat będzie oczywiście działać w czasie \(O(mn)\):

Czyli konstrukcja grafu i zaznaczanie komnat niebezpiecznych będzie działać w czasie \(O(n^2 + mn)\), a przeszukiwanie grafu w czasie \(O(n)\). Cały algorytm zadziała w czasie \(O((n+m)n)\) i przejdzie podzadania 1 i 3.

Rozwiązanie dla niedużej mapy lub niedużej liczby komnat

Powyżej przedstawiliśmy dwa niezależne rozwiązania, które łącznie pozwalają na zaliczenie testów z podzadań 1, 2 i 3. Niestety, wymaga to zaimplementowania obu tych rozwiązań i wybierania, które uruchomić, na podstawie wielkości danych wejściowych.

Okazuje się jednak, że można zaproponować jedno rozwiązanie, które będzie przechodzić te trzy podzadania. Powróćmy do pierwszego pomysłu z trzymaniem mapy w tablicy. W przypadku małej mapy sprawdza się on bardzo dobrze, ale dla dużej mapy będzie zbyt wolny. Jednak jeśli nawet mapa jest duża, ale komnat i punktów jest mało, to, intuicyjnie rzecz biorąc, w wielu miejscach mapy będzie po prostu „pusto". Może zatem jesteśmy w stanie jakoś z tego skorzystać?

Spróbujmy sformalizować to pojęcie „pustości". Powiemy, że pionowa prosta o całkowitej współrzędnej jest ciekawa, jeśli zawiera jakiś pionowy bok komnaty lub punkt. Zauważmy, że jeśli prosta \(x\) jest nieciekawa, to moglibyśmy skompresować naszą tablicę \(d\), zastępując kolumny o numerach \(x\) oraz \(x+1\) pojedynczą kolumną. Taka zmiana w żaden sposób nie wpłynie na postać konstruowanego grafu komnat. Jest tak, bo nieistotne są wielkości komnat, a jedynie ich położenie względem siebie i względem punktów.

I teraz najważniejsza obserwacja: ciekawych prostych jest co najwyżej \(2n+m+2\) (a być może mniej), bo mamy co najwyżej \(2n\) różnych współrzędnych dla pionowych boków komnat oraz co najwyżej \(m+2\) różnych współrzędnych dla punktów. Zatem skompresowana tablica będzie zawierała co najwyżej \(2n+m+1\) kolumn.

Analogicznie możemy mówić o ciekawych i nieciekawych prostych poziomych, i po wykonaniu kompresji na wierszach tablicy będzie ona miała co najwyżej \(2n+m+1\) wierszy. Zatem po kompresji tablicy \(d\) będzie ona miała rozmiar \(\min(h, 2n+m+1) \times \min(w, 2n+m+1)\), więc algorytm wyznaczania grafu, przeszukujący tablicę \(d\), będzie działał w czasie \(O(\min(w, n+m) \cdot \min(h, n+m))\).

Jak jednak zrobić taką kompresję? Musimy każdemu punktowi przypisać nową współrzędną. Zilustrujemy to na przykładzie współrzędnych \(x\). Najpierw wszystkie współrzędne \(x\) (dla wierzchołków prostokątów i punktów) wrzucamy do tablicy \(X\). Następnie sortujemy tę tablicę w czasie \(O((n+m) \log (n+m))\) i usuwamy z niej duplikaty w czasie \(O(n+m)\). W tym momencie tablica \(X\) zawiera posortowane współrzędne \(x\) ciekawych prostych pionowych. Po kompresji (czyli wyrzuceniu prostych nieciekawych) te proste powinny dostać kolejne współrzędne.

Dlatego też starą współrzędną \(x\) każdego wierzchołka prostokąta i każdego punktu zastępujemy nową współrzędną, którą jest numer komórki tablicy \(X\), w której zapisana jest stara współrzędna. Numer komórki możemy wyznaczyć wyszukiwaniem binarnym w czasie \(O(\log(n+m))\) (np. używając funkcji lower_bound z biblioteki standardowej języka C++):

Użyta tutaj technika nazywa się kompresją współrzędnych. Ostatecznie cały algorytm zadziała w czasie \(O((n+m) \log (n+m) + \min(w, n+m) \cdot \min(h, n+m))\) i przechodzi trzy podzadania.

Wzorcowe rozwiązanie dla komnat

Przejdziemy teraz do szybszego rozwiązania konstrukcji grafu komnat, przy czym wrócimy tu do pomysłu z algorytmem, w którym sprawdzamy stykanie się prostokątów. Tamten algorytm był kwadratowy, ponieważ sprawdzał wszystkie możliwe pary komnat, nie biorąc pod uwagę tego, że wynikowy graf będzie planarny.

Spróbujmy zatem szybciej operować na komnatach. Możemy przyjrzeć się jeszcze raz implementacji funkcji \(\mathit{czySasiednie}\) i zauważyć, że dwie komnaty mogą być sąsiednie tylko wtedy, gdy ich pewne przeciwległe boki znajdują się na tej samej prostej. Ustalmy zatem pewną prostą poziomą \(y\) i rozważmy zbiór komnat, które dotykają tej prostej bokiem. Zbiór dzieli się na dwa podzbiory: górny (dla prostokątów dotykających prostej bokiem dolnym) oraz dolny (dla prostokątów dotykających górnym bokiem). W przykładzie dla \(y=3\) mamy górny zbiór 6 i 8 oraz dolny zbiór 2 i 4.

Teraz możemy posortować wszystkie prostokąty ze zbiorów rosnąco po współrzędnych \(x\) i przejść po nich kolejno, utrzymując wskaźnik na aktualny prostokąt górny i aktualny dolny. Na początku oba wskaźniki wskazują na skrajnie lewe prostokąty ze zbiorów. W każdej iteracji przesuwamy jeden ze wskaźników: ten, którego nowo wskazywany prostokąt ma mniejszą współrzędną lewego boku. Zauważmy, że dzięki temu w grafie mogą być połączone krawędzią jedynie te pary prostokątów, które w pewnym momencie algorytmu były wskazywane przez wskaźniki.

Jeśli wykonamy taki algorytm dla wszystkich prostych poziomych, to znajdziemy wszystkie krawędzie grafu, które odpowiadają przejściom pomiędzy poziomymi bokami komnat.

Każdej prostej poziomej przypiszmy prostokąty, które dotykają jej górnym lub dolnym bokiem. Niech \(G[y]\) oznacza prostokąty dotykające prostej poziomej \(y\) dolnym bokiem, zaś niech \(D[y]\) oznacza prostokąty dotykające prostej poziomej \(y\) górnym bokiem. Aby wykonać takie pogrupowanie możemy skorzystać ze standardowej struktury w C++ (map), lub wcześniej wykonać kompresję i operować na małych współrzędnych.

Dla pojedynczej prostej i dwóch zbiorów o wielkościach \(g\) i \(d\) sortowanie zadziała w czasie \(O(g\log g + d\log d)\), a wyznaczanie krawędzi w czasie \(O(g+d)\). Przyporządkowanie prostokątów do prostych poziomych zajmuje czas \(O(n\log n)\) (wykorzystanie mapy lub kompresja współrzędnych). Sumaryczna wielkość wszystkich zbiorów \(G[y]\) i \(D[y]\) to \(2n\) (każda komnata należy do jednego zbioru górnego i jednego dolnego), więc cały algorytm będzie działał w czasie \(O(n\log n)\). Użyliśmy tutaj metody zamiatania w jednym wymiarze (można sobie wyobrażać, że nasze dwa wskaźniki „zamiatały" zbiór prostokątów od lewej do prawej).

Jeśli wykonamy symetryczny algorytm dla prostych pionowych, to zbudujemy graf komnat w czasie \(O(n \log n)\). Takie rozwiązanie pozwala nam przejść podzadanie 4.

Wzorcowe rozwiązanie dla punktów

Jeśli w rozwiązaniu z poprzedniej sekcji wyznaczanie miejsc niebezpiecznych zrobimy brutalnie (przez rozważanie wszystkich komnat), to dodatkowo przejdzie ono podzadania 1 i 3. Do podzadania 5 potrzebujemy jednak czegoś lepszego.

Znowu użyjemy metody zamiatania, ale tym razem w dwóch wymiarach. Wyobraźmy sobie, że przesuwamy poziomą prostą (zwaną miotłą) od dołu do góry i utrzymujemy zbiór prostokątów, które przecinają tę prostą. Dla testu przykładowego, jeśli prosta znajduje się w położeniu \(y=4\), to przecina prostokąty 5, 6 i 8. Każdy prostokąt pojawi się w tym zbiorze, gdy prosta wejdzie na jego dolny bok, a zostanie usunięty ze zbioru, gdy prosta opuści jego górny bok.

Ponadto za każdym razem, gdy prosta przejdzie przez punkt, będziemy chcieli wyszukać na miotle prostokąt, który go zawiera. Prostokąty będą zatem trzymane na miotle w kolejności rosnących współrzędnych \(x\), a wyznaczenie, który z prostokątów przecinanych prostą zawiera szukany punkt, będziemy mogli zrobić wyszukiwaniem binarnym.

Nie będziemy rozważać wszystkich położeń miotły, a jedynie te, w których dzieje się coś interesującego. Takie interesujące położenia nazywamy zdarzeniami. Zdarzenia będą opisywane przez czwórkę \((y, typ, x, i)\), gdzie \(typ\) jest jednym z trzech typów zdarzenia: dolnybok, gornybok albo punkt. Dla zdarzeń odnoszących się do boków współrzędna \(y\) oznacza prostą, współrzędna \(x\) oznacza prawy bok komnaty, natomiast \(i\) oznacza numer komnaty. Komnaty na miotle będziemy przechowywać jako pary \((x,i)\), gdzie \(x\) jest prawym bokiem komnaty, a \(i\) jej numerem. Pary będą posortowane po współrzędnej \(x\) (w języku C++ możemy wykorzystać do implementacji miotły kontener set).

Dla punktów wartości \(y\) i \(x\) są jego współrzędnymi, natomiast \(i\) jest nieistotne. Gdy napotkamy na punkt, będziemy chcieli wyznaczyć na miotle parę \((x',i')\), która ma najmniejsze \(x'\) większe od \(x\) (taka para na pewno istnieje, bo każdy punkt jest zawarty we wnętrzu jakiejś komnaty, zatem współrzędna prawego boku — która jest większa od \(x\) — będzie w zbiorze). Wartość \(i'\) jest oczywiście numerem komnaty, która zawiera punkt \((x,y)\). Takie wyszukiwanie w kontenerze set udostępnia funkcja lower_bound.

Sortowanie zbioru zdarzeń \(E\) działa w czasie \(O((n+m) \log (n+m))\), natomiast obsługa każdego z \(O(n+m)\) zdarzeń sprowadza się do jednej operacji na kontenerze set i działa w czasie \(O(\log n)\). Ostatecznie cały algorytm działa w czasie \(O((n+m) \log (n+m))\) i przechodzi wszystkie podzadania.