Omówienie zadania Gra platformowa (I etap XXVIII OI)

Podzadanie 1

Trzymamy całą planszę w postaci grafu, którego wierzchołkami są wszystkie możliwe pozycje postaci \((i,x)\). Z ograniczeń podzadania wynika, że wierzchołków jest co najwyżej \(nX \leq 10^6\).

Krawędzie w grafie odpowiadają wszystkim ruchom zdefiniowanym w treści zadania, przy czym krawędzie dla ruchów klawisza F mają wagę 0, a pozostałe krawędzie mają wagę 1. Z każdego wierzchołka wychodzą co najwyżej 4 krawędzie, więc rozmiar grafu to \(O(nX)\).

Dla pojedynczego zapytania mamy znaleźć najtańszą ścieżkę w grafie z początkowego wierzchołka \((i,1)\) do dowolnego wierzchołka \((\cdot,X)\). Można to zrobić algorytmem Dijkstry w czasie \(O(nX \log(nX))\) lub algorytmem 0–1 BFS w czasie \(O(nX)\). Ten drugi to wersja BFS dla grafów z wagami 0 i 1, przy czym wierzchołki, do których weszliśmy krawędziami o wadze \(1\) wrzucamy na koniec kolejki, natomiast wierzchołki z krawędzi o wadze \(0\) wrzucamy na początek kolejki.

Złożoność czasowa to \(O(nXz)\).

Wszystkie zapytania na raz

Możemy przyspieszyć algorytm, szukając najkrótszych ścieżek w tył. Wszystkie wierzchołki postaci \((\cdot,X)\) wrzucamy na kolejkę (ustawiając im odległość 0), a następnie uruchamiamy algorytm 0–1 BFS na grafie transponowanym (z odwróconymi kierunkami krawędzi). Dzięki temu po jednym przeszukaniu grafu dostaniemy długości najkrótszych ścieżek do wszystkich wierzchołków \((i,1)\). Tak więc teraz na każde zapytanie możemy odpowiedzieć w czasie stałym.

Złożoność czasowa to \(O(nX + z)\).

Podzadanie 2

Kompresujemy nasz graf. Wierzchołki nowego grafu to skrajnie lewe pozycje na każdym spójnym kawałku platformy (czyli pozycje \((\cdot,1)\) oraz pozycje za każdą dziurą), pozycje pod każdą dziurą, oraz pozycje \((\cdot,X)\).

Konstruujemy graf, analizując kolejne platformy. Dla platformy \(i\) przeglądamy dziury na niej oraz na platformie \(i-1\) (leżącej powyżej). Będąc w wierzchołku \((i,x)\) patrzymy na najbliższą dziurę po prawej:

• jeśli jest ona na platformie \(i\) na pozycji \(x'\), to robimy krawędź o wadze 0 do wierzchołka \((i+1,x')\) oraz krawędź o wadze 1 do wierzchołka \((i,x'+1)\),

• jeśli jest ona na platformie \(i-1\) na pozycji \(x'\), to robimy krawędź o wadze 0 do wierzchołka \((i,x')\) oraz krawędź o wadze 1 do wierzchołka \((i-1,x'+1)\).

Graf ma rozmiar \(O(n+K)\), gdzie \(K\) jest ograniczeniem na liczbę dziur. Na takim grafie uruchamiamy algorytm 0–1 BFS. Złożoność czasowa rozwiązania to \(O((n+K)z)\).

Podzadanie 3

Szukając w skompresowanym grafie ścieżek w tył, dostajemy złożoność czasową \(O(n+K+z)\).