Kolorowy wąż

Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Kolorowy wąż”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. W dużym skrócie: w zadaniu graliśmy w węża i zjadaliśmy kolorowe jedzenie z planszy. Gdy wąż zjadł jedzenie, zwiększał się o jeden segment z przodu i segment ten stawał się koloru tego jedzenia. Podczas gry otrzymywaliśmy pytania typu: jaki jest kolor segmentu węża na danym polu planszy.

Potrzebujemy trzech tablic:

• mapa[i][j] = kolor jedzenia na danym polu lub -1 jeśli pole jest puste.
• wąż[i] = kolor i-tego segmentu węża, gdzie wąż[0] oznacza jego ogon (łatwiej jest dodawać elementy z tyłu tablicy niż z przodu).
• pozycja_glowy[i][j] = ostatnia chwila w której głowa węża znajdowała się na polu [i][j].

Najpierw uzupełnijmy tablicę mapa, gdyż została ona podana na wejściu w innej formie.

for (int i = 0; i < p; i++)
{
    int w, k, c;

    cin >> w >> k >> c;
    mapa[w][k] = c;
}

Oprócz tablicy wąż[i] będziemy trzymać pozycję głowy węża w danym momencie: wąż_w oraz wąż_k (koordynaty głowy węża). Gdy przesuwamy węża na planszy, aktualizujemy zmienne wąż_w oraz wąż_k i jeśli wąż zjadł owoc, to wrzucamy odpowiedni kolor na koniec tablicy wąż, a następnie zaznaczamy na mapie, że owoc został zjedzony. Zapisujemy nowy czas w tablicy pozycja_głowy.

if (kierunek == 'G') wąż_w--;
if (kierunek == 'D') wąż_w++;
if (kierunek == 'L') wąż_k--;
if (kierunek == 'P') wąż_k++;

if (mapa[wąż_w][wąż_k] != -1)
{
    wąż[długość_węża++] = mapa[wąż_w][wąż_k];
    mapa[wąż_w][wąż_k] = -1;
}

czas++;
pozycja_głowy[wąż_w][wąż_k] = czas;

Gdy otrzymujemy zapytanie, sprawdzamy w tablicy pozycja_głowy ostatni czas w którym głowa była w tym miejscu. Odejmując od czasu tę wartość, otrzymujemy który segment węża jest na tym polu. Kolor tego segmentu odczytujemy z tablicy wąż.

int segment = czas - pozycja_głowy[w][k];

if (segment < długość_węża)
    cout << wąż[długość_węża - 1 - segment] << endl;
else
    cout << -1 << endl;

Rozwiązanie to działa w czasie liniowym.