kburnik

C++ - Zadatak Zmija - rjesenje

Jan 9th, 2013
209
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3. Pripreme 2013 - C++ radionica
  4.  
  5. Zadatak: Zmija
  6.  
  7. Autor zadatka: HSIN
  8.  
  9. Ponudjeno rjesenje: Kristijan Burnik, udruga informaticara Bozo Tezak
  10.  
  11. Datum rjesavanja: 2013-01-10
  12.  
  13. */
  14.  
  15. #include <iostream>
  16. #include <cstdlib>
  17. #include <map>
  18. #include <list>
  19. #include <set>
  20.  
  21. using namespace std;
  22.  
  23. /////////////////////// malo prijevoda radi lakseg citanja ///////////////////
  24.  
  25. typedef pair < int, int > Pozicija;
  26. typedef pair < int, int > Smjer;
  27. typedef pair < Pozicija , Smjer > Clanak;
  28. typedef int Okret;
  29. typedef int Sekunda;
  30.  
  31. typedef list< Clanak >::iterator IT;
  32.  
  33. #define X first
  34. #define Y second
  35.  
  36. #define pozicija first
  37. #define smjer second
  38. #define mp make_pair
  39.  
  40. #define sadrzi count
  41.  
  42. #define glava front
  43.  
  44. #define stvori_glavu push_front
  45.  
  46. //////////////////////////////////////////////////////////////////////////////
  47.  
  48.  
  49. int N,K,L;
  50.  
  51. // maksimalna velicina ploce
  52. const int MAXN = 100;
  53.  
  54. // ploca na kojoj su smjestene jabuke
  55. int ploca[ MAXN ][ MAXN ];
  56.  
  57. // zmija je obicna vezana lista njezinih clanaka
  58. list< Clanak > zmija;
  59.  
  60. // mapiramo smjer i relativnu rotaciju sa novim smjerom
  61. map < pair< Smjer , Okret >, Smjer> rotiraj;
  62.  
  63. // da li je neka pozicija unutar ploce
  64. bool unutarPloce( Pozicija p ) {
  65.     return ( p.X >= 0 && p.Y >= 0 ) && ( p.X < N && p.Y < N );
  66. }
  67.  
  68. // definiramo okrete
  69. const Okret LIJEVO = -1;
  70. const Okret DESNO = 1 ;
  71.  
  72. // definiramo smjerove
  73. const Smjer SJEVER = mp(-1,0);
  74. const Smjer JUG = mp(1,0);
  75. const Smjer ZAPAD = mp(0,-1);
  76. const Smjer ISTOK = mp(0,1);
  77.  
  78. //////////////////////////////////////////////////////////////////////////////
  79.  
  80.  
  81.  
  82. // mapiramo nove smjerove kod rotiranja u lijevo ili desno
  83. void pripremiRotacije() {
  84.    
  85.     // rotacije u lijevo
  86.     rotiraj[ mp( ISTOK , LIJEVO ) ] = SJEVER ;
  87.     rotiraj[ mp( JUG , LIJEVO ) ] = ISTOK ;
  88.     rotiraj[ mp( ZAPAD , LIJEVO ) ] = JUG ;
  89.     rotiraj[ mp( SJEVER , LIJEVO ) ] = ZAPAD ;
  90.    
  91.      // rotacije u desno
  92.     rotiraj[ mp( ISTOK ,  DESNO ) ] = JUG ;
  93.     rotiraj[ mp( JUG ,  DESNO ) ] = ZAPAD ;
  94.     rotiraj[ mp( ZAPAD ,  DESNO ) ] = SJEVER ;
  95.     rotiraj[ mp( SJEVER ,  DESNO ) ] = ISTOK ;
  96.    
  97.     // primjer uporabe:
  98.     // ako je glava usmjerena prema istoku i treba ici lijevo,
  99.     // tada ce krenuti prema sjeveru
  100. }
  101.  
  102.  
  103. // da li zmija udara u sebe
  104. bool udaraUSebe() {
  105.     IT it = zmija.begin();
  106.     it++;
  107.    
  108.     for ( ; it != zmija.end(); it++) {
  109.         if ( zmija.glava().pozicija == it->pozicija )
  110.            return true;        
  111.     }
  112.  
  113.     return false;        
  114. }
  115.  
  116. // postavi jabuku na zadanu poziciju
  117. void postaviJabuku( Pozicija p ) {
  118.    ploca[ p.X ][ p.Y ] = 1;
  119. }
  120.  
  121. // ukloni jabuku na poziciji p
  122. void ukloniJabuku( Pozicija p ) {
  123.     ploca[ p.X ][ p.Y ] = 0;
  124. }
  125.  
  126. // da li imamo jabuku na poziciji p ?
  127. bool imaJabuke( Pozicija p ) {
  128.     return ploca[ p.X ][ p.Y ] == 1;
  129. }
  130.  
  131. //////////////////////////////////////////////////////////////////////////////
  132.  
  133.  
  134. int main() {
  135.    
  136.    
  137.     // mapiramo nove smjerove kod rotiranja
  138.     pripremiRotacije();
  139.    
  140.     // ulaz: velicina ploce i pozicije jabuka
  141.     cin >> N >> K;
  142.     for (int i = 0 ; i < K; i++) {
  143.         Pozicija p;
  144.         cin >> p.X >> p.Y ;
  145.         postaviJabuku( p );
  146.     }
  147.    
  148.    
  149.     // sekunda u kojoj se dogadja okret
  150.     Sekunda s;
  151.     // tekstualni opis okreta (L ili D)
  152.     string d;
  153.     // opis okreta unutar programa
  154.     Okret dir;
  155.    
  156.     // mapiramo okrete po sekundi
  157.     map < Sekunda , Okret > okretUSekundi;
  158.    
  159.     cin >> L;
  160.     for (int i = 0; i < L; i++) {
  161.         cin >> s >> d;    
  162.         okretUSekundi[ s ] = ( d == "D" ) ? DESNO : LIJEVO ;
  163.     }
  164.    
  165.     // stvori glavu na pozicij 0,0 i usmjeri prema ISTOKU
  166.    
  167.     zmija.stvori_glavu( Clanak( mp(0,0), ISTOK ) );
  168.    
  169.     Sekunda trenutnaSekunda = 0;
  170.    
  171.     // radi dok ne nastupi break;
  172.     for ( ; ; ) {
  173.        
  174.         // prati trajanje igre u sekundama
  175.         trenutnaSekunda++;
  176.        
  177.         // produlji zmiju u smjeru glave (kopiraj glavu)
  178.         zmija.stvori_glavu( zmija.glava() );
  179.  
  180.         // pomakni poziciju nove glave u njenom smjeru
  181.         zmija.glava().pozicija.X += zmija.glava().smjer.X;
  182.         zmija.glava().pozicija.Y += zmija.glava().smjer.Y;
  183.  
  184.         // ako nije ispravna pozicija gotovi smo
  185.         // ako zmija udara glavom u sebe gotovi smo
  186.         if ( !unutarPloce( zmija.glava().pozicija ) || udaraUSebe() ) {          
  187.             break;
  188.         }
  189.      
  190.         if ( imaJabuke( zmija.glava().pozicija ) ) {
  191.             // ukloni jabuku
  192.             ukloniJabuku( zmija.glava().pozicija );        
  193.         } else {
  194.             // ukloni rep
  195.             zmija.pop_back();
  196.         }
  197.      
  198.         // ako u ovoj sekundi imamo okret, obavimo ga
  199.         if ( okretUSekundi.sadrzi( trenutnaSekunda ) ) {
  200.             Okret okret = okretUSekundi[ trenutnaSekunda ];
  201.             Smjer smjerGlave = zmija.glava().smjer;
  202.            
  203.             // novi smjer glave je smjer koji nastaje rotacijom
  204.             // trenutnog smjera u neku stranu (L ili D)
  205.             Smjer noviSmjerGlave = rotiraj[ mp( smjerGlave ,  okret ) ];
  206.             zmija.glava().smjer = noviSmjerGlave;
  207.         }
  208.        
  209.     }
  210.    
  211.     Sekunda trajanjeIgre = trenutnaSekunda;
  212.    
  213.     cout << trajanjeIgre << endl;
  214.  
  215.     system("pause");
  216.     return 0;
  217. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×