Source code for submission s717

grasshop.cpp

  1.  
  2. /*
  3.  * File:   grasshop.c
  4.  * Author: cteam057
  5.  *
  6.  * Created on October 27, 2012, 11:02 AM
  7.  */
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <queue>
  12.  
  13. /*
  14.  *
  15.  */
  16.  
  17.  
  18.  
  19. int r, c, gr, gc, lr, lc;
  20. int i, j, begin, end, nalezeno, qsize;
  21. int ** pole;
  22. int *fronta;
  23.  
  24. int trysq(int a, int b) {
  25.     if(fronta[begin%qsize]+a>0 && fronta[begin%qsize]+a<=r && fronta[(begin+1)%qsize]+b>0 && fronta[(begin+1)%qsize]+b<=c
  26.             && pole[fronta[begin%qsize]+a][fronta[(begin+1)%qsize]+b]==-1) {
  27.         fronta[end%qsize] = fronta[begin%qsize]+a;
  28.         end++;
  29.         fronta[end%qsize] = fronta[(begin+1)%qsize]+b;
  30.         end++;
  31.         pole[fronta[begin%qsize]+a][fronta[(begin+1)%qsize]+b] = pole[fronta[begin]][fronta[begin+1]] +1;
  32.         if(fronta[begin%qsize]+a == lr && fronta[(begin+1)%qsize]+b == lc) {
  33.             printf("%d\n", pole[fronta[begin%qsize]+a][fronta[(begin+1)%qsize]+b]);
  34.             nalezeno = 1;
  35.             return 1;
  36.         }
  37.     }
  38.     return 0;
  39. }
  40.  
  41. int main(int argc, char** argv) {
  42.  
  43.     while(scanf("%d %d %d %d %d %d", &r, &c, &gr, &gc, &lr, &lc)==6) {
  44.         pole = (int **) malloc((r+1)*sizeof(int*));
  45.         for(i = 1; i <= r; i++) {
  46.             pole[i] = (int *) malloc((c+1)*sizeof(int));
  47.             for (j = 1; j <= c; j++) pole[i][j] = -1;
  48.         }
  49.  
  50.         begin = 0;
  51.         end = 2;
  52.         qsize = 4*r*c;
  53.         fronta = (int *) malloc (4*r*c*sizeof(int));
  54.         fronta[0] = gr;
  55.         fronta[1] = gc;
  56.  
  57.         pole[gr][gc] = 0;
  58.  
  59.         nalezeno = 0;
  60.  
  61.         while(begin!=end) {
  62.             if(trysq(-1, -2)) break;
  63.             if(trysq(1, -2)) break;
  64.             if(trysq(-1, 2)) break;
  65.             if(trysq(1, 2)) break;
  66.             if(trysq(-2, -1)) break;
  67.             if(trysq(-2, 1)) break;
  68.             if(trysq(2, -1)) break;
  69.             if(trysq(2, 1)) break;
  70.             begin+=2;
  71.         }
  72.  
  73.         if(!nalezeno) printf("impossible\n");
  74.  
  75.         free(fronta);
  76.         for(i = 1; i <=r; i++) {
  77.             free(pole[i]);
  78.         }
  79.         free(pole);
  80.     }
  81.  
  82.  
  83.     return 0;
  84. }
  85.  
  86.