Konkurs

> Zadanie

Poszukiwacz skarbów

Kierujesz poszukiwaczem skarbów, twoim zadaniem jest zebrać jak najwięcej cennego kruszcu możliwie jak najmniejszym kosztem. Poszukiwanie prowadzisz na planszy 500 x 500 pól. Większość pól jest pusta, ale na niektórych znajdują się cenne minerały, a na części - samorodki złota!

Poruszanie

Obszar jest przedstawiony w postaci 24 bitowego obrazu RGB (jeden piksel to jedno pole). Każde pole posiada wysokość - od 0 do 200. Wysokość jest podana w postaci koloru RGB o równych składowych - przykładowo polu o wysokości 120 odpowiada piksel RGB = (120, 120, 120). Wyjątkami są kwadraty symbolizujące pole startowe, minerały i samorodki - w tych polach wysokość wynosi 0.

Poszukiwacz może poruszać się w jednym z czterech kierunków: lewo, prawo, góra i dół, oznaczonych odpowiednio literami: L, R, U, D. Koszt ruchu jest zależny od różnicy poziomów pola docelowego i źródłowego - pokonanie jednego metra w górę kosztuje 0,02, jednego metra w dół - 0,01. Przykładowo - przejście z pola o wysokości 20 na pole o wysokości 10 kosztuje 0,10 punktów, a przejście na pole o wysokości 30 - 0,20. Koszt jest odejmowany od zdobytych punktów bezpośrednio po ruchu.

Maksymalnie można wykonać 10000 ruchów, pozostałe zostaną zignorowane. W przypadku próby zrobienia nieprawidłowego ruchu (błędny symbol, ruch poza planszę) poszukiwacz pozostanie w miejscu. Ruchy są zapisywane w postaci łańcucha tekstowego (patrz przykładowe rozwiązanie).

Minerały

Obszar poszukiwań zawiera 1000 minerałów, oznaczonych kwadratami o rozmiarze 3x3 i kolorze RGB = (255, 0, 0). Aby zebrać minerał należy przejść przez środkowe pole symbolizującego go kwadratu. Minerał można zebrać tylko jeden raz - za każdy poszukiwacz dostaje 10 punktów, dodawanych do jego wyniku bezpośrednio po zebraniu.

Samorodki

Na planszy znajduje się dodatkowo 50 samorodków złota. Są oznaczone kwadratami 3x3 o kolorze RGB = (255, 255, 0), zbieranie odbywa się analogicznie jak dla minerałów. Samorodek w momencie zebrania zwiększa liczbę punktów o 1% - wartość ta jest dodawana do wyniku zaraz po zebraniu.

Pole startowe

Polem startowym jest środek kwadratu 3x3 o kolorze RGB = (0, 255, 0). Na planszy znajduje się dokładnie jeden taki kwadrat. W polu tym zawsze znajduje się minerał (1 z 1000) i jest on automatycznie w posiadaniu poszukiwacza - stąd zaczynając przygodę posiada on 10 punktów.

Ocena rozwiązania

Oceną rozwiązania jest liczba punktów zdobyta po wykonaniu ostatniego ruchu, zaokrąglona do dwóch miejsc po przecinku. Na każdy zestaw obowiązuje limit czasu 5 sekund oraz limit pamięci 32MB. W przypadku przekroczenia któregoś z limitów bądź błędu wykonania rozwiązania ocena za zestaw wynosi 0.

Ocena końcowa

Końcową oceną zawodnika jest średnia arytmetyczna ocen ze 100 zestawów przygotowanych przez organizatorów, zaokrąglona do dwóch miejsc po przecinku.

Przykładowe rozwiązanie

W pliku pod adresem http://www.adaptive-vison.com/konkurs/avs_konkurs.zip znajduje się szablon projektu TreasureHunter dla środowiska Microsoft Express C++ 2008. Rozwiązanie powinno znaleźć się w pliku TreasureHunter.cpp w funkcji bool TreasureHunter::Invoke().

  /** Treasure hunter function */
  bool TreasureHunter::Invoke()
  {
    /** Get source image */
    Image* image = (Image*)Get("map");
    /* How to retreive image data - pixel: x=10, y=50 */
    UInt8 r = image->GetR(10, 50);
    UInt8 g = image->GetG(10, 50);
    UInt8 b = image->GetB(10, 50);
    /* Example solution */
    std::string moves;
    const int MOVES[4] = { 'L', 'U', 'R', 'D' };
    for (int i = 1; i <= 100; ++i)
      for (int j = 1; j <= i; ++j)
        moves.push_back(MOVES[i % 4]);
    /** Set moves */
    Set("moves", new String(moves));
    return true;
  }
  

Testowanie

Do testowania rozwiązania można wykorzystać pakiet Adaptive Vision Studio, dostępny na stronie konkursu. Po kompilacji rozwiązania należy uruchomić aplikację i otworzyć program TreasureHunter.avp. Po uruchomieniu programu w oknie podglądu zostanie zaprezentowana trasa przebyta przez poszukiwacza wraz z zaznaczonymi zebranymi skarbami oraz rezultat końcowy.

Kliknij tutaj aby przejść do strony głównej konkursu.