Source code for submission s602

grasshop.c

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. int q[120000];
  6. int qrp;
  7. int qwp;
  8. int visited[200][200];
  9. int r,c;
  10.  
  11. void qi(int x, int y, int d) {
  12. if (visited[x][y]) return;
  13. if (x < 1 || y < 1) return;
  14. if (x > r || y > c) return;
  15. visited[x][y] = 1;
  16. q[qwp++] = x;
  17. q[qwp++] = y;
  18. q[qwp++] = d;
  19. }
  20.  
  21. void qr(int *x, int *y, int *d) {
  22. *x = q[qrp++];
  23. *y = q[qrp++];
  24. *d = q[qrp++];
  25. }
  26.  
  27. int main(int argc, char **argv)
  28. {
  29. int gr,gc,lr,lc;
  30.  
  31. int cr,cc,cd;
  32.  
  33. while (1) {
  34. scanf("%d %d %d %d %d %d", &r, &c, &gr, &gc, &lr, &lc);
  35. if (feof(stdin))
  36. break;
  37. qrp = 0;
  38. qwp = 0;
  39. memset(visited, 0, sizeof(int)*200*200);
  40. qi(gr,gc,0);
  41. while (qrp < qwp) {
  42. qr(&cr,&cc,&cd);
  43. if (cr==lr && cc==lc) {
  44. printf("%d\n", cd);
  45. break;
  46. }
  47. qi(cr-2, cc-1, cd+1);
  48. qi(cr-1, cc-2, cd+1);
  49. qi(cr-2, cc+1, cd+1);
  50. qi(cr-1, cc+2, cd+1);
  51. qi(cr+2, cc-1, cd+1);
  52. qi(cr+1, cc-2, cd+1);
  53. qi(cr+2, cc+1, cd+1);
  54. qi(cr+1, cc+2, cd+1);
  55. }
  56. if (qrp >= qwp) printf("impossible\n");
  57. }
  58. return 0;
  59. }
  60.