Source code for submission s1104

grasshop.c

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. #define NOT_VISITED -1
  5.  
  6. int R, C, GR, GC, LR, LC;
  7. /* R, C ... area size */
  8. int area[102][102]; /* R-major */
  9.  
  10. typedef struct {unsigned char r, c;} point;
  11. typedef struct {point list[102*102]; int len;} data;
  12.  
  13. data aa, bb;
  14.  
  15. int in_grid(point x)
  16. {
  17. return x.r >= 1 && x.r <= R && x.c >= 1 && x.c <= C;
  18. }
  19.  
  20. int main(void)
  21. {
  22. int i, step, row, col, j;
  23. point *p;
  24. int *len_ptr;
  25. point dest[8];
  26. int flag;
  27. data *a, *b, *tmp;
  28.  
  29. while (scanf("%d %d %d %d %d %d ", &R, &C, &GR, &GC, &LR, &LC) == 6) {
  30. a = &aa;
  31. b = &bb;
  32. for (i = 0; i < 102*102; ++i)
  33. ((int*)(area))[i] = NOT_VISITED;
  34. area[GR][GC] = 0;
  35.  
  36. a->len = 0;
  37. b->len = 0;
  38.  
  39. a->list[0].r = GR;
  40. a->list[0].c = GC;
  41. a->len = 1;
  42.  
  43. for (step = 1; ; ++step)
  44. {
  45. b->len = 0;
  46. flag = 0;
  47. for (i = 0; i < a->len; ++i)
  48. {
  49. row = a->list[i].r;
  50. col = a->list[i].c;
  51. /*
  52. dest = { {row+1, col+2}, {row+1, col-2}, {row-1, col+2}, {row-1, col-2},
  53. {row+2, col+1}, {row+2, col-1}, {row-2, col+1}, {row-2, col-1} };
  54. */
  55. dest[0].r = row+1;
  56. dest[0].c = col+2;
  57.  
  58. dest[1].r = row-1;
  59. dest[1].c = col+2;
  60.  
  61. dest[2].r = row+1;
  62. dest[2].c = col-2;
  63.  
  64. dest[3].r = row-1;
  65. dest[3].c = col-2;
  66.  
  67. dest[4].r = row+2;
  68. dest[4].c = col+1;
  69.  
  70. dest[5].r = row-2;
  71. dest[5].c = col+1;
  72.  
  73. dest[6].r = row+2;
  74. dest[6].c = col-1;
  75.  
  76. dest[7].r = row-2;
  77. dest[7].c = col-1;
  78.  
  79.  
  80. for (j = 0; j < 8; ++j)
  81. {
  82. if (in_grid(dest[j])) {
  83. if (area[ dest[j].r ][ dest[j].c ] == NOT_VISITED) {
  84. area[ dest[j].r ][ dest[j].c ] = step;
  85. flag = 1;
  86. b->list[ b->len++ ] = dest[j];
  87. if (dest[j].r == LR && dest[j].c == LC) {
  88. printf("%d\n", step);
  89. goto endloop;
  90. }
  91. }
  92. }
  93. }
  94.  
  95. }
  96. if (flag == 0) {
  97. printf("impossible\n");
  98. goto endloop;
  99. }
  100. tmp = b;
  101. b = a;
  102. a = tmp;
  103. }
  104. endloop:
  105. ;
  106. }
  107. return 0;
  108. }
  109.  
  110.