Omówienie zadania Kolorowy wąż (I etap XXX OI)

Treść zadania

Pomysł na zadanie wywodzi się z Gry w węża stworzonej na dawne telefony Nokia, w której wąż przemieszcza się po dwuwymiarowej planszy, po drodze zjadając przekąski. W każdej jednostce czasu wąż może poruszyć się w górę, w dół, w prawo lub w lewo, przy czym o kierunku ruchu decyduje gracz. Kiedy wąż zjada przekąskę, wydłuża się o pole, na którym znajdowała się przekąska. Po szczegóły dotyczące tego, jak przemieszcza się wąż w tej grze, odsyłamy do treści zadania.

W przeciwieństwie od oryginalnej Gry w węża, w naszym zadaniu rozmiar planszy (\(m\)) może być bardzo duży, podobnie jak liczba przekąsek (\(p\)). Co więcej, w zadaniu każda przekąska ma pewien kolor. Kiedy wąż zjada przekąskę, jego nowa głowa przejmuje kolor przekąski. Stąd tytuł naszego zadania, Kolorowy wąż.

Naszym zadaniem jest symulacja ruchu węża na planszy – czyli nie my musimy decydować, jakie ruchy wykonuje wąż, tylko mamy je już podane. Podczas symulacji musimy umieć odpowiadać na pytania, w których dostajemy współrzędne pola na planszy i mamy stwierdzić, czy na tym polu znajduje się jakiś fragment węża, a jeśli tak, jaki jest jego kolor. Podobnie jak liczba przekąsek, łączna liczba operacji (\(n\)), czyli ruchów węża i pytań, jest potencjalnie duża.

Oryginalna Gra w węża

Rozwiązanie zadania rozpoczniemy nietypowo, od podzadania 3, które naprowadzi nas na rozwiązanie wzorcowe. W tym podzadaniu, podobnie jak w oryginalnej Grze w węża, wszystkie przekąski mają ten sam kolor. Wówczas w odpowiedzi na pytanie wystarczy stwierdzić, czy na danym polu planszy znajduje się jakiś fragment węża, czy nie.

Kluczową kwestią jest zastanowić się nad najbardziej dogodną reprezentacją planszy i węża. Plansza ma wymiary \(m \times m\) dla \(m \le 2000\), więc możemy ją reprezentować w postaci boolowskiej tablicy dwuwymiarowej przekaski. Założymy, że przekaski[i][j]=true wtedy i tylko wtedy, gdy na polu w wierszu i i kolumnie j znajduje się przekąska.

Gdy wąż przesuwa się, zbiór zajmowanych przez niego pól zmienia się bardzo nieznacznie – dochodzi nowe pole, na którym znajdzie się głowa węża, a znika pole, na którym był koniec jego ogona – chyba że wąż zjada przekąskę, to wtedy ogon nie znika. Wąż funkcjonuje zatem jak struktura danych o nazwie kolejka.

Wykorzystamy strukturę danych queue z języka C++, która udostępnia następujące metody:

• pop(): usuwa element z początku kolejki
• push(x): wstawia element x na koniec kolejki
• front(): daje w wyniku element na początku kolejki
• back(): daje w wyniku element na końcu kolejki.

Nasz wąż będzie kolejką par liczb oznaczających współrzędne kolejnych fragmentów węża (queue<pair<int, int> > waz). W przypadku naszego węża, początek kolejki będzie odpowiadał ogonowi, a koniec głowie. Do odpowiadania na pytania przyda się boolowska tablica dwuwymiarowa gdzie_waz reprezentująca zbiór pól zajmowanych przez węża. Wtedy ruch węża w przypadku, gdy, powiedzmy, użytkownik wykonuje ruch w górę, wygląda następująco:

  auto glowa = waz.back();
  if (znak == 'G') --glowa.first; // głowa przesuwa się w górę
  else if (znak == 'D') ++glowa.first; // w dół
  else if (znak == 'L') --glowa.second; // w lewo
  else ++glowa.second; // w prawo: znak == 'P'
  waz.push(glowa);
  bool &przekaska = przekaski[glowa.first][glowa.second]; // referencja pozwala łatwo "wyzerować" przekąskę
  if (przekaska) {
    przekaska = false; // przekąska znika z planszy
  } else {
    auto ogon = waz.front();
    waz.pop(); // ogon przesuwa się
    gdzie_waz[ogon.first][ogon.second] = false;
  }
  gdzie_waz[glowa.first][glowa.second] = true;

Tak więc każdy ruch węża obsługujemy w czasie stałym. Na pytanie o dane pole odpowiadamy również w czasie stałym na podstawie komórki tablicy gdzie_waz. Tablicę przekaski wypełniamy w czasie \(O(m^2+p)\). Złożoność czasowa rozwiązania podzadania 3 to zatem \(O(m^2+p+n)\).

Rozwiązanie wzorcowe

Pola planszy zajmowane przez węża działają na zasadzie kolejki, natomiast kolory tych pól, w kierunku od ogona do głowy, działają jak stos. Aby uzyskać rozwiązanie wzorcowe, musimy węża reprezentować nie wprost, pamiętając osobno kolejkę i stos.

Aby odpowiadać na pytania, musimy jakoś zmodyfikować tablicę gdzie_waz. Nie możemy sobie pozwolić na trzymanie w niej koloru fragmentu węża aktualnie zajmującego dane pole, jako że wtedy każdy ruch węża wymagałby wykonania tylu zmian w tej tablicy, ile wynosi aktualna długość węża. Łącznie otrzymalibyśmy rozwiązanie o złożoności \(\Omega(n^2)\), które miałoby szansę przejść tylko pierwsze podzadanie.

Zamiast tego możemy wpaść na pomysł, żeby gdzie_waz[i][j] przechowywało moment, w którym wąż wszedł na pole w wierszu i i kolumnie j, o ile wąż się tam aktualnie znajduje. Na tej podstawie, znając aktualny moment oznaczony zmienną ruch i mając do dyspozycji stos kolory reprezentujący kolory pól węża, jesteśmy w stanie podać kolor fragmentu węża znajdującego się obecnie na tym polu.

Będziemy musieli być w stanie powiedzieć, jaki kolor znajduje się w danym miejscu stosu reprezentującego węża. Tej funkcjonalności nie zapewnia kontener stack z C++. Do reprezentacji stosu należy użyć np. kontenera vector, który wspiera nadzbiór operacji tego poprzedniego.

Poniżej umieszczamy kod odpowiadający za symulację ruchu głowy w górę. Zaznaczyliśmy w nim zmiany w stosunku do kodu dla jednokolorowego węża. W szczególności teraz tablica przekaski zawiera kolor przekąski lub -1, jeśli na danym polu nie ma przekąski.

  auto glowa = waz.back();
  if (znak == 'G') --glowa.first; // głowa przesuwa się w górę
  else if (znak == 'D') ++glowa.first; // w dół
  else if (znak == 'L') --glowa.second; // w lewo
  else ++glowa.second; // w prawo: znak == 'P'
  waz.push(glowa);
  int &przekaska = przekaski[glowa.first][glowa.second]; // NOWE
  if (przekaska != -1) {
    kolory.push_back(przekaska); // NOWE; przekąska trafia na stos
    przekaska = -1; // NOWE; przekąska znika z planszy
  } else {
    auto ogon = waz.front();
    waz.pop(); // ogon przesuwa się
    gdzie_waz[ogon.first][ogon.second] = -1; // NOWE
  }
  gdzie_waz[glowa.first][glowa.second] = ruch++; // NOWE, numer aktualnego ruchu

Aby odpowiedzieć na pytanie o kolor fragmentu węża znajdującego się w wierszu w i kolumnie k, możemy teraz użyć następującego fragmentu kodu.

  if (gdzie_waz[w][k] == -1) {
    cout << "-1\n";
  } else {
    int ktory_od_poczatku = ruch - gdzie_waz[w][k];
    cout << kolory[(int)kolory.size() - 1 - ktory_od_poczatku] << '\n';
  }

Złożoność czasowa rozwiązania wzorcowego to także \(O(m^2+p+n)\).