C++ - Zadatak Zmija - rjesenje

/*

Pripreme 2013 - C++ radionica

Zadatak: Zmija

Autor zadatka: HSIN

Ponudjeno rjesenje: Kristijan Burnik, udruga informaticara Bozo Tezak

Datum rjesavanja: 2013-01-10

*/

#include <iostream>
#include <cstdlib>
#include <map>
#include <list>
#include <set>

using namespace std;

/////////////////////// malo prijevoda radi lakseg citanja ///////////////////

typedef pair < int, int > Pozicija;
typedef pair < int, int > Smjer;
typedef pair < Pozicija , Smjer > Clanak;
typedef int Okret;
typedef int Sekunda;

typedef list< Clanak >::iterator IT;

#define X first
#define Y second

#define pozicija first
#define smjer second
#define mp make_pair

#define sadrzi count

#define glava front

#define stvori_glavu push_front

//////////////////////////////////////////////////////////////////////////////


int N,K,L;

// maksimalna velicina ploce
const int MAXN = 100;

// ploca na kojoj su smjestene jabuke
int ploca[ MAXN ][ MAXN ];

// zmija je obicna vezana lista njezinih clanaka
list< Clanak > zmija;

// mapiramo smjer i relativnu rotaciju sa novim smjerom
map < pair< Smjer , Okret >, Smjer> rotiraj;

// da li je neka pozicija unutar ploce
bool unutarPloce( Pozicija p ) {
    return ( p.X >= 0 && p.Y >= 0 ) && ( p.X < N && p.Y < N );
}

// definiramo okrete
const Okret LIJEVO = -1;
const Okret DESNO = 1 ;

// definiramo smjerove
const Smjer SJEVER = mp(-1,0);
const Smjer JUG = mp(1,0);
const Smjer ZAPAD = mp(0,-1);
const Smjer ISTOK = mp(0,1);

//////////////////////////////////////////////////////////////////////////////



// mapiramo nove smjerove kod rotiranja u lijevo ili desno
void pripremiRotacije() {

    // rotacije u lijevo
    rotiraj[ mp( ISTOK , LIJEVO ) ] = SJEVER ;
    rotiraj[ mp( JUG , LIJEVO ) ] = ISTOK ;
    rotiraj[ mp( ZAPAD , LIJEVO ) ] = JUG ;
    rotiraj[ mp( SJEVER , LIJEVO ) ] = ZAPAD ;

     // rotacije u desno
    rotiraj[ mp( ISTOK ,  DESNO ) ] = JUG ;
    rotiraj[ mp( JUG ,  DESNO ) ] = ZAPAD ;
    rotiraj[ mp( ZAPAD ,  DESNO ) ] = SJEVER ;
    rotiraj[ mp( SJEVER ,  DESNO ) ] = ISTOK ;

    // primjer uporabe:
    // ako je glava usmjerena prema istoku i treba ici lijevo,
    // tada ce krenuti prema sjeveru
}


// da li zmija udara u sebe
bool udaraUSebe() {
    IT it = zmija.begin();
    it++;

    for ( ; it != zmija.end(); it++) {
        if ( zmija.glava().pozicija == it->pozicija )
           return true;
    }

    return false;
}

// postavi jabuku na zadanu poziciju
void postaviJabuku( Pozicija p ) {
   ploca[ p.X ][ p.Y ] = 1;
}

// ukloni jabuku na poziciji p
void ukloniJabuku( Pozicija p ) {
    ploca[ p.X ][ p.Y ] = 0;
}

// da li imamo jabuku na poziciji p ?
bool imaJabuke( Pozicija p ) {
    return ploca[ p.X ][ p.Y ] == 1;
}

//////////////////////////////////////////////////////////////////////////////


int main() {


    // mapiramo nove smjerove kod rotiranja
    pripremiRotacije();

    // ulaz: velicina ploce i pozicije jabuka
    cin >> N >> K;
    for (int i = 0 ; i < K; i++) {
        Pozicija p;
        cin >> p.X >> p.Y ;
        postaviJabuku( p );
    }


    // sekunda u kojoj se dogadja okret
    Sekunda s;
    // tekstualni opis okreta (L ili D)
    string d;
    // opis okreta unutar programa
    Okret dir;

    // mapiramo okrete po sekundi
    map < Sekunda , Okret > okretUSekundi;

    cin >> L;
    for (int i = 0; i < L; i++) {
        cin >> s >> d;
        okretUSekundi[ s ] = ( d == "D" ) ? DESNO : LIJEVO ;
    }

    // stvori glavu na pozicij 0,0 i usmjeri prema ISTOKU

    zmija.stvori_glavu( Clanak( mp(0,0), ISTOK ) );

    Sekunda trenutnaSekunda = 0;

    // radi dok ne nastupi break;
    for ( ; ; ) {

        // prati trajanje igre u sekundama
        trenutnaSekunda++;

        // produlji zmiju u smjeru glave (kopiraj glavu)
        zmija.stvori_glavu( zmija.glava() );

        // pomakni poziciju nove glave u njenom smjeru
        zmija.glava().pozicija.X += zmija.glava().smjer.X;
        zmija.glava().pozicija.Y += zmija.glava().smjer.Y;

        // ako nije ispravna pozicija gotovi smo
        // ako zmija udara glavom u sebe gotovi smo
        if ( !unutarPloce( zmija.glava().pozicija ) || udaraUSebe() ) {
            break;
        }

        if ( imaJabuke( zmija.glava().pozicija ) ) {
            // ukloni jabuku
            ukloniJabuku( zmija.glava().pozicija );
        } else {
            // ukloni rep
            zmija.pop_back();
        }

        // ako u ovoj sekundi imamo okret, obavimo ga
        if ( okretUSekundi.sadrzi( trenutnaSekunda ) ) {
            Okret okret = okretUSekundi[ trenutnaSekunda ];
            Smjer smjerGlave = zmija.glava().smjer;

            // novi smjer glave je smjer koji nastaje rotacijom
            // trenutnog smjera u neku stranu (L ili D)
            Smjer noviSmjerGlave = rotiraj[ mp( smjerGlave ,  okret ) ];
            zmija.glava().smjer = noviSmjerGlave;
        }

    }

    Sekunda trajanjeIgre = trenutnaSekunda;

    cout << trajanjeIgre << endl;

    system("pause");
    return 0;
}