Omówienie zadania Bomberman (II etap XXIX OI)

Planszę można opisać przy pomocy grafu, w którym wierzchołki reprezentują puste pola, a krawędzie są pomiędzy polami sąsiadującymi bokiem. Taki graf będzie miał co najwyżej \(n^2\) wierzchołków, natomiast liczba jego krawędzi będzie ograniczona przez \(2 n^2\).

Podzadanie 1

Plansza nie zawiera żadnych murów z cegły, wobec tego jedynymi przeszkodami są pola z litą skałą, których nie będziemy mogli usunąć niezależnie od umiejscowienia bomby. Wystarczy zatem, że znajdziemy najkrótszą ścieżkę z wierzchołka początkowego do końcowego, przy pomocy algorytmu przeszukiwania wszerz. Złożoność czasowa jest liniowa od wielkości grafu, czyli będzie wynosić \(O(n^2)\). Jeśli w każdym wierzchołku będziemy jeszcze pamiętali dodatkowo poprzednik w drzewie najkrótszych ścieżek, to będziemy mogli również odzyskać całą ścieżkę.

Należy pamiętać, że choć nie potrzebujemy bomby, to przy wypisywaniu odpowiedzi jednak musimy jakąś postawić. Można to zrobić w dowolnym pustym polu, na przykład polu początkowym.

Podzadanie 2

Zastanówmy się, jak postawienie bomby może nam pomóc w przypadku plansz zawierających mury z cegieł. Najprostszy sposób to rozpatrzenie wszystkich możliwości stawiania bomby. Zatem przeiterujemy się po wszystkich polach niezawierających litej skały, czyli tych, w których możemy postawić bombę. Jeżeli ustalimy już wybór pola, to kopiujemy sobie całą planszę, a następnie uaktualniamy na niej wszystkie pola zamienione przez wybuch bomby. Najprościej będzie dla każdego z czterech kierunków poruszać się od pola z bombą i zmieniać pola na puste, aż do napotkania pola z litą skałą lub krańca planszy.

Następnie na tak uaktualnionej planszy wykonujemy algorytm BFS, który znajduje nam długość najkrótszej ścieżki. Jeżeli będzie ona mniejsza niż dotychczasowe minimum, to uaktualniamy najlepszą znalezioną pozycję bomby. Na końcu wypisujemy długość najkrótszej znalezionej ścieżki oraz pozycję bomby, dla której ta ścieżka była zrealizowana.

Aby odzyskać całą ścieżkę, na końcu, po znalezieniu najlepszej pozycji bomby, jeszcze raz uruchamiamy BFS dla planszy z bombą umieszczoną właśnie w tej pozycji. Tym razem jednak dla każdego pola wyznaczamy też poprzedników w drzewie najkrótszych ścieżek.

Złożoność tego algorytmu to będzie \(O(n^4)\), ponieważ dla \(n^2\) kandydatów na pozycję bomby musimy uruchomić algorytm BFS działający w czasie \(O(n^2)\).

Podzadanie 3

Nietrudno się domyślić, że rozwiązanie trzeciego podzadania będzie wymagało algorytmu o złożoności co najwyżej \(O(n^3)\). W dotychczasowym algorytmie dość kosztowne było sprawdzanie pojedynczej bomby, dla której wykonywaliśmy kopiowanie planszy i algorytm BFS działający w czasie \(O(n^2)\), przy czym bomba zmieniała jedynie \(O(n)\) pól na planszy. Spróbujmy zatem wyznaczyć długość najkrótszej ścieżki dla ustalonej bomby w czasie \(O(n)\).

Popatrzmy na optymalną ścieżkę z pola początkowego do końcowego. Można pokazać, że w ogólnym przypadku dzieli się ona na cztery fragmenty (przy czym osobno należy rozważyć symetryczny przypadek, gdy najpierw idziemy pionowym, a potem poziomym fragmentem):

• od pola początkowego po pustych polach do pierwszego pola w zasięgu bomby,

• następnie poziomym fragmentem przez pola leżące w zasięgu bomby, aż do pola z bombą,

• potem pionowym fragmentem przez pola leżące w zasięgu bomby,

• i dalej po pustych polach do pola końcowego.

Jeżeli bowiem ścieżka przecina zbiór pól leżących w zasięgu bomby więcej niż raz (mamy więcej niż jeden taki spójny kawałek, w którym chodzi ona po polach ze zbioru), to możemy ją zastąpić ścieżką, która zawiera tylko jeden taki spójny kawałek (jeżeli ścieżka gdzieś wychodzi z naszego zbioru, a potem znowu do niego wchodzi, to cały ten kawałek możemy zastąpić przejściem wewnątrz zbioru i nie będzie to przejście dłuższe, ponieważ korzystamy tutaj z metryki miejskiej, a możemy chodzić po wszystkich polach ze zbioru).

Z kolei jeśli ścieżka nie przechodzi przez pole z bombą, to możemy przesunąć bombę na jedną z pozycji, w których ścieżka przecina pola ze zbioru.

Zauważmy, że algorytm BFS znajduje najkrótsze ścieżki z ustalonego pola do wszystkich pozostałych pól. Wobec tego możemy jednym przejściem algorytmu BFS obliczyć odległości od pola początkowego dla wszystkich możliwych wyborów pola kończącego pierwszy fragment. Zatem zrobimy to w czasie \(O(n^2)\) w trakcie obliczeń wstępnych jeszcze przed wyborem pozycji bomby. Niech \(dist[v]\) oznacza zatem odległość od pola początkowego do pola \(v\), jeśli przechodzimy po pustych polach.

Najpierw wyznaczmy najkrótszą ścieżkę od pola początkowego do pola z bombą. Zaczynamy od pola z bombą i idziemy w lewo po polach leżących w zasięgu bomby (co odpowiada poruszaniu się drugim fragmentem), za każdym razem sprawdzając, jaka jest długość ścieżki, gdyby aktualne pole było pierwszym polem drugiego fragmentu. Jeśli przeszliśmy \(i\) pól i znajdujemy się na polu \(v\), to długość tej ścieżki to \(i + dist[v]\). Ta faza zajmie czas \(O(n)\).

Symetrycznie sprawdzamy pozostałe trzy kierunki, z których można wyjść od pola z bombą.

Następnie wykonujemy podobny algorytm dla najkrótszej ścieżki od bomby do pola końcowego.

Całkowity czas działania tego algorytmu to będzie \(O(n^2)\) na obliczenia wstępne (dwa BFS-y) oraz \(O(n)\) dla każdego z \(n^2\) kandydatów na bombę. W sumie \(O(n^3)\).

Rozwiązanie wzorcowe

Zbudujemy graf stanów, w którym będziemy kodowali nie tylko pozycję na naszej ścieżce, ale również to, którym fragmentem ścieżki idziemy. Zatem wierzchołki grafu będą zawierały w sobie pozycję pola \((r,c)\) oraz typ fragmentu ścieżki \(t\), którym aktualnie możemy się poruszać (będzie to liczba od \(1\) do \(4\)). Krawędzie w naszym grafie będą dwojakiego rodzaju: będą to krawędzie, które idą w obrębie jednego typu fragmentu ścieżki, oraz takie krawędzie, które będą zmieniać typ ścieżki.

Pierwszy typ krawędzi \((r_1,c_1,t) \to (r_2,c_2,t)\) będzie prowadził pomiędzy dwoma sąsiadującymi polami, przy czym muszą to być pola puste lub z cegłami i krawędź taka będzie miała wagę \(1\). Musimy liczyć się tutaj z pewnymi ograniczeniami wynikającymi z typów ścieżek:

• Jeżeli jest to pierwszy fragment (\(t=1\)), to wtedy pole \((r_1,c_1)\), z którego idziemy, musi być puste.

• Jeżeli jest to drugi fragment (\(t=2\)), to wtedy możemy poruszać się jedynie w lewo i w prawo (\(r_1=r_2\)).

• W przypadku trzeciego fragmentu (\(t=3\)) możemy iść tylko w górę i w dół (\(c_1=c_2\)).

• A w przypadku czwartego fragmentu (\(t=4\)) pole docelowe \((r_2,c_2)\) musi być puste.

Drugi rodzaj krawędzi \((r,c,t) \to (r,c,t+1)\) będzie nam umożliwiał przeskoczenie na kolejny fragment naszej ścieżki. Ale ponieważ chcemy, żeby to odbyło się bez zmiany pola, na którym się znajdujemy, te krawędzie będą miały wagę \(0\).

Na takim grafie uruchomimy algorytm szukania najkrótszej ścieżki z pola początkowego i typu ścieżki \(1\) do pola końcowego i typu ścieżki \(4\).

Ponieważ graf jest ważony, nie będziemy mogli uruchomić zwykłego algorytmu BFS, ale na przykład algorytm Dijkstry. Ale ponieważ wagi w naszym grafie to jedynie liczby \(0\) i \(1\), efektywniej będzie uruchomić algorytm 0–1 BFS, który jest wersją algorytmu BFS uwzględniającym wagi \(0\). Działa on w takiej samej złożoności jak zwykły algorytm BFS, ale 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.

Ponieważ liczba wierzchołków w naszym grafie jest ograniczona przez \(4 n^2\), a krawędzi jest również kwadratowo wiele, wobec tego cały algorytm będzie działał w czasie \(O(n^2)\). Ścieżkę odzyskujemy standardowo, przy czym ignorujemy przejścia o wadze \(0\). Do odzyskania pozycji bomby patrzymy na którym polu zrobiliśmy przejście z typu ścieżki \(2\) na typ ścieżki \(3\).