Source code for submission s735

grasshop.cpp

  1. //
  2. // File: grasshop.cc
  3. // Author: cteam053
  4. //
  5. // Created on October 27, 2012, 10:55 AM
  6. //
  7.  
  8. #include <stdlib.h>
  9. #include <stdio.h>
  10. #include <cstdio>
  11. #include <cmath>
  12. #include <climits>
  13. #include <iostream>
  14. #include <list>
  15.  
  16. using namespace std;
  17.  
  18. int xmax, ymax;
  19.  
  20. bool code(int x, int y, int& ret){
  21. if(x <= 0 || y <= 0 || x > xmax || y > ymax)
  22. return false;
  23. ret = 1000*x + y;
  24. return true;
  25. }
  26.  
  27.  
  28.  
  29.  
  30. int main(int argc, char** argv) {
  31.  
  32. int R, C, Gr, Gc, Lr, Lc;
  33. list<int> sData;
  34. list<int> len;
  35. int length = -1;
  36. int tmp, x, y, ret, request;
  37.  
  38. while(1){
  39. int ret = scanf("%d%d%d%d%d%d", &R, &C, &Gr, &Gc, &Lr, &Lc);
  40. if(ret != 6)
  41. return 0;
  42.  
  43. xmax = R;
  44. ymax = C;
  45. code(Lr, Lc, request);
  46.  
  47. code(Gr, Gc, ret);
  48. len.clear();
  49. len.push_back(0);
  50. sData.clear();
  51. sData.push_back(ret);
  52. while(!sData.empty()){
  53. tmp = *(sData.begin());
  54. sData.pop_front();
  55. length = *(len.begin());
  56. len.pop_front();
  57. if(tmp == request)
  58. break;
  59. x = tmp / 1000;
  60. y = tmp % 1000;
  61.  
  62. if(code(x-2, y-1, ret)){
  63. sData.push_back(ret);
  64. len.push_back(length+1);
  65. }
  66.  
  67. if(code(x-2, y+1, ret)){
  68. len.push_back(length+1);
  69. sData.push_back(ret);}
  70.  
  71. if(code(x-1, y+2, ret)){
  72. len.push_back(length+1);
  73. sData.push_back(ret);}
  74.  
  75. if(code(x+1, y+2, ret)){
  76. len.push_back(length+1);
  77. sData.push_back(ret);}
  78.  
  79. if(code(x+2, y+1, ret)){
  80. len.push_back(length+1);
  81. sData.push_back(ret);}
  82.  
  83. if(code(x+2, y-1, ret)){
  84. len.push_back(length+1);
  85. sData.push_back(ret);}
  86.  
  87. if(code(x+1, y-2, ret)){
  88. len.push_back(length+1);
  89. sData.push_back(ret);}
  90.  
  91. if(code(x-1, y-2, ret)){
  92. len.push_back(length+1);
  93. sData.push_back(ret);}
  94. }
  95. if(length == 0)
  96. printf("impossible\n");
  97. else
  98. printf("%d\n", length);
  99. }
  100.  
  101.  
  102.  
  103. return (0);
  104. }
  105.  
  106.