Source code for submission s1351

grasshop.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4.  
  5. typedef struct POS {
  6. int x;
  7. int y;
  8. double d;
  9.  
  10. POS(int _x = -1, int _y = -1, double _d = -1) {
  11. x = _x;
  12. y = _y;
  13. d = _d;
  14. }
  15. } POS;
  16.  
  17. int r, c, gr, gc, lr, lc;
  18.  
  19. const int results_max = 10;
  20. int results[results_max];
  21. int results_iter;
  22. int min_jmp;
  23.  
  24. bool out_of_grid(int x, int y) {
  25. if (x > r || x < 0 || y > c || y < 0) {
  26. return true;
  27. } else {
  28. return false;
  29. }
  30. }
  31.  
  32. /**
  33.  * @return distance from x,y to L
  34.  */
  35. int distance(int x, int y) {
  36. return sqrt(abs(lr-x)*abs(lr-x) + abs(lc-y)*abs(lc-y));
  37. }
  38.  
  39. POS jump(int x, int y, int dx, int dy) {
  40. int nx, ny;
  41.  
  42. nx = x + dx;
  43. ny = y + dy;
  44.  
  45. if (out_of_grid(nx, ny)) {
  46. return POS(-1, -1, -1);
  47. }
  48.  
  49. return POS(nx, ny, distance(nx, ny));
  50. }
  51.  
  52. int sgn (double x) {
  53. if (x > 0.)
  54. return 1;
  55. if (x < 0.)
  56. return -1;
  57. return 0;
  58. }
  59.  
  60. int pos_cmp (const void *a, const void *b) {
  61. const POS *p1 = (const POS *) a;
  62. const POS *p2 = (const POS *) b;
  63. return sgn (p2->d - p1->d);
  64. }
  65.  
  66. void m_jump(int x, int y, int jumps) {
  67.  
  68. if (jumps > 10) {
  69. return;
  70. }
  71.  
  72. if (results_iter == results_max) {
  73. return;
  74. }
  75.  
  76. POS p[8];
  77. int iter = 0;
  78. POS tmp;
  79.  
  80. // printf("a");
  81.  
  82. for (int i = -1; i <= 1; i += 1) {
  83. for (int j = -1; j <= 1; j += 1) {
  84. if (i == 0 && j == 0) {
  85. continue;
  86. }
  87.  
  88. p[iter++] = jump(x, y, i, j);
  89. //printf("x: %d, y: %d, i:%d, j: %d, px: %d, py: %d\n", x, y, i, j, p[iter - 1].x, p[iter -1].y);
  90. }
  91. }
  92.  
  93. // printf("b");
  94.  
  95. // qsort (p, 8, sizeof *p, pos_cmp);
  96.  
  97. //printf("c");
  98.  
  99. for (int i = 0; i < 8; i += 1) {
  100.  
  101.  
  102. if (p[i].x == -1) {
  103. continue;
  104. }
  105.  
  106. // printf("jmp: %d, i:%d, px: %d, py: %d\n", jumps, i, p[i].x, p[i].y);
  107.  
  108. if (p[i].x == lr && p[i].y == lc) {
  109. if (jumps + 1 < min_jmp) {
  110. printf("yay %d\n", jumps);
  111. min_jmp = jumps + 1;
  112. results[results_iter++] = jumps + 1;
  113. if (results_iter == results_max) {
  114. return;
  115. }
  116. }
  117. }
  118. }
  119.  
  120. // printf("d");
  121.  
  122. for (int i = 7; i >= 0; i -= 1) {
  123. if (p[i].x == -1) {
  124. continue;
  125. }
  126. m_jump(p[i].x, p[i].y, jumps + 1);
  127. }
  128. }
  129.  
  130. int tabulka[7][7] = { { 0, 3, 2, 3, 2, 3, 4},
  131. { 3, 2, 1, 2, 3, 4, 0},
  132. { 2, 1, 4, 3, 2, 0, 0},
  133. { 3, 2, 3, 2, 0, 0, 0},
  134. { 2, 3, 2, 0, 0, 0, 0},
  135. { 3, 4, 0, 0, 0, 0, 0},
  136. { 4, 0, 0, 0, 0, 0, 0}};
  137.  
  138. int main(int argc, char** argv) {
  139. while (scanf("%d%d%d%d%d%d", &r, &c, &gr, &gc, &lr, &lc) == 6) {
  140. int jumps = 0;
  141. int orig_gr = gr;
  142. int orig_gc = gc;
  143. while(abs(gr - lr) + abs(gc - lc) > 6)
  144. {
  145. if (abs(gr - lr) > abs(gc - lc))
  146. {
  147. if (gr > lr)
  148. {
  149. gr -= 2;
  150. if (gc > lc)
  151. {
  152. gc--;
  153. }
  154. else gc++;
  155. }
  156. jumps++;
  157. }
  158. else
  159. {
  160. if (gc > lc)
  161. {
  162. gc -= 2;
  163. if (gr > lr)
  164. {
  165. gr--;
  166. }
  167. else gr++;
  168. }
  169. jumps++;
  170. }
  171. }
  172. if ( r < 3 || c < 3)
  173. {
  174. printf("impossible\n");
  175. continue;
  176. }
  177. jumps += tabulka[abs(gr - lr)][abs(gc - lc)];
  178. printf("%d\n", jumps);
  179.  
  180. }
  181.  
  182. return 0;
  183. }
  184.