Source code for submission s642

grasshop.cpp

  1. #include <cstdio>
  2. #define MAX 10100
  3.  
  4. int qx[MAX];
  5. int qy[MAX];
  6. int qb,qe;
  7. int n;
  8. int visited[110][110];
  9.  
  10. int mx,my,gx,gy,lx,ly,resx,resy;
  11.  
  12. bool jumpUUR(int xx,int yy){
  13. int x = xx+1;
  14. int y = yy+2;
  15. if((x == lx) && (y == ly)){
  16. visited[x][y] = visited[xx][yy]+1 ;
  17. resx = x;
  18. resy = y;
  19. return true;
  20. }
  21.  
  22. if((x <= mx ) && (y <= my)){
  23. if(visited[x][y] == -1){
  24. visited[x][y] = visited[xx][yy]+1 ;
  25. qx[qe]=x;
  26. qy[qe++]=y;
  27. }
  28.  
  29. }
  30. return false;
  31. }
  32.  
  33. bool jumpURR(int xx,int yy){
  34. int x = xx+2;
  35. int y = yy+1;
  36. if((x == lx) && (y == ly)){
  37. visited[x][y] = visited[xx][yy]+1 ;
  38. resx = x;
  39. resy = y;
  40. return true;
  41. }
  42.  
  43. if((x <= mx ) && (y <= my)){
  44. if(visited[x][y] == -1){
  45. visited[x][y] = visited[xx][yy]+1 ;
  46. qx[qe]=x;
  47. qy[qe++]=y;
  48. }
  49.  
  50. }
  51. return false;
  52. }
  53. bool jumpUUL(int xx,int yy){
  54. int x = xx-1;
  55. int y = yy+2;
  56. if((x == lx) && (y == ly)){
  57. visited[x][y] = visited[xx][yy]+1 ;
  58. resx = x;
  59. resy = y;
  60. return true;
  61. }
  62.  
  63. if((x > 0 ) && (y <= my)){
  64. if(visited[x][y] == -1){
  65. visited[x][y] = visited[xx][yy]+1 ;
  66. qx[qe]=x;
  67. qy[qe++]=y;
  68. }
  69.  
  70. }
  71. return false;
  72. }
  73. bool jumpULL(int xx,int yy){
  74. int x = xx-2;
  75. int y = yy+1;
  76. if((x == lx) && (y == ly)){
  77. visited[x][y] = visited[xx][yy]+1 ;
  78. resx = x;
  79. resy = y;
  80. return true;
  81. }
  82.  
  83. if((x > 0 ) && (y <= my)){
  84. if(visited[x][y] == -1){
  85. visited[x][y] = visited[xx][yy]+1 ;
  86. qx[qe]=x;
  87. qy[qe++]=y;
  88. }
  89.  
  90. }
  91. return false;
  92. }
  93. bool jumpDLL(int xx,int yy){
  94. int x = xx-2;
  95. int y = yy-1;
  96. if((x == lx) && (y == ly)){
  97. visited[x][y] = visited[xx][yy]+1 ;
  98. resx = x;
  99. resy = y;
  100. return true;
  101. }
  102.  
  103. if((x > 0 ) && (y > 0)){
  104. if(visited[x][y] == -1){
  105. visited[x][y] = visited[xx][yy]+1 ;
  106. qx[qe]=x;
  107. qy[qe++]=y;
  108. }
  109. }
  110. return false;
  111. }
  112. bool jumpDDL(int xx,int yy){
  113. int x = xx-1;
  114. int y = yy-2;
  115. if((x == lx) && (y == ly)){
  116. visited[x][y] = visited[xx][yy]+1 ;
  117. resx = x;
  118. resy = y;
  119. return true;
  120. }
  121.  
  122. if((x > 0 ) && (y > 0)){
  123. if(visited[x][y] == -1){
  124. visited[x][y] = visited[xx][yy]+1 ;
  125. qx[qe]=x;
  126. qy[qe++]=y;
  127. }
  128.  
  129. }
  130. return false;
  131. }
  132. bool jumpDDR(int xx,int yy){
  133. int x = xx+1;
  134. int y = yy-2;
  135. if((x == lx) && (y == ly)){
  136. visited[x][y] = visited[xx][yy]+1 ;
  137. resx = x;
  138. resy = y;
  139. return true;
  140. }
  141.  
  142. if((x <= mx ) && (y > 0)){
  143. if(visited[x][y] == -1){
  144. visited[x][y] = visited[xx][yy]+1 ;
  145. qx[qe]=x;
  146. qy[qe++]=y;
  147. }
  148.  
  149. }
  150. return false;
  151. }
  152. bool jumpDRR(int xx,int yy){
  153. int x = xx+2;
  154. int y = yy-1;
  155. if((x == lx) && (y == ly)){
  156. visited[x][y] = visited[xx][yy]+1 ;
  157. resx = x;
  158. resy = y;
  159. return true;
  160. }
  161.  
  162. if((x <= 100 ) || (y > 0)){
  163. if(visited[x][y] == -1){
  164. visited[x][y] = visited[xx][yy]+1 ;
  165. qx[qe]=x;
  166. qy[qe++]=y;
  167. }
  168.  
  169. }
  170. return false;
  171. }
  172.  
  173. bool enqueue(){
  174. int x,y;
  175. x = qx[qb];
  176. y = qy[qb++];
  177.  
  178. if(jumpUUR(x,y))
  179. return true;
  180. if(jumpURR(x,y))
  181. return true;
  182. if(jumpDRR(x,y))
  183. return true;
  184. if(jumpDDR(x,y))
  185. return true;
  186. if(jumpDDL(x,y))
  187. return true;
  188. if(jumpDLL(x,y))
  189. return true;
  190. if(jumpULL(x,y))
  191. return true;
  192. if(jumpUUL(x,y))
  193. return true;
  194.  
  195. return false;
  196. }
  197.  
  198. int main(int argc, char ** argv)
  199. {
  200. while(scanf("%d %d %d %d %d %d",&mx,&my,&gx,&gy,&lx,&ly) == 6){
  201. qb = qe = 0;
  202. qx[qe] = gx;
  203. qy[qe++] = gy;
  204. n = 0;
  205. for(int i=1;i<=100;i++)
  206. for(int ii=1;ii<=100;ii++)
  207. visited[i][ii]= -1;
  208. visited[gx][gy]=n;
  209. while(1){
  210. if(qb == qe){
  211. printf("impossible\n");
  212. break;
  213. }
  214.  
  215. if(enqueue() == true){
  216. printf("%d\n",visited[resx][resy]);
  217. break;
  218. }
  219. }
  220. }
  221. return 0;
  222. }
  223.