Source code for submission s1007

Go to diff to previous submission

grasshop.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. bool ** bitmap;
  8. int R, C, Gr, Gc, Lr, Lc, steps, min_;
  9.  
  10. bool rek(int x, int y, int steps)
  11. {
  12. //bitmap[x][y];
  13. if (x == Lr && y == Lc)
  14. {
  15. if (min_ > steps) min_ = steps;
  16. return true;
  17. }
  18. bool ret = false;
  19. steps++;
  20. if ((R > C && steps > R/2+2) || (C >= R && steps > C/2+2)) return false;
  21. if (x+2 < R && y+1 < C && bitmap[x+2][y+1]) ret |= rek(x+2, y+1, steps);
  22. if (x+2 < R && y-1 >= 0 && bitmap[x+2][y-1]) ret |= rek(x+2, y-1, steps);
  23. if (x-2 >= 0 && y+1 < C && bitmap[x-2][y+1]) ret |= rek(x-2, y+1, steps);
  24. if (x-2 >= 0 && y-1 >= 0 && bitmap[x-2][y-1]) ret |= rek(x-2, y-1, steps);
  25.  
  26. if (y+2 < C && x+1 < R && bitmap[x+1][y+2]) ret |= rek(x+1, y+2, steps);
  27. if (y+2 < C && x-1 >= 0 && bitmap[x-1][y+2]) ret |= rek(x-1, y+2, steps);
  28. if (y-2 >= 0 && x+1 < R && bitmap[x+1][y-2]) ret |= rek(x+1, y-2, steps);
  29. if (y-2 >= 0 && x-1 >= 0 && bitmap[x-1][y-2]) ret |= rek(x-1, y-2, steps);
  30. return ret;
  31. }
  32.  
  33. int main()
  34. {
  35. while (cin >> R >> C >> Gr >> Gc >> Lr >> Lc)
  36. {
  37. bitmap = (bool **) malloc(sizeof(bool *) * R);
  38. for (int i=0; i<R; i++)
  39. {
  40. bitmap[i] = (bool *) malloc(sizeof(bool) * C);
  41. for (int j=0; j<C; j++)
  42. bitmap[i][j] = true;
  43. }
  44. Gr--; Gc--; Lr--; Lc--;
  45. min_ = R+C;
  46. if (!rek(Gr, Gc, 0)) cout << "impossible" << endl;
  47. else cout << min_ << endl;
  48. for (int i=0; i<R; i++)
  49. free(bitmap[i]);
  50. free(bitmap);
  51. }
  52. return 0;
  53. }
  54.  
  55.  

Diff to submission s1004

grasshop.cpp

--- c4.s1004.cteam045.grasshop.cpp.0.grasshop.cpp
+++ c4.s1007.cteam045.grasshop.cpp.0.grasshop.cpp
@@ -18,5 +18,5 @@
         bool ret = false;
         steps++;
-        if ((R > C && steps > R) || (C >= R && steps > C)) return false;
+        if ((R > C && steps > R/2+2) || (C >= R && steps > C/2+2)) return false;
         if (x+2 <  R && y+1 <  C && bitmap[x+2][y+1]) ret |= rek(x+2, y+1, steps);
         if (x+2 <  R && y-1 >= 0 && bitmap[x+2][y-1]) ret |= rek(x+2, y-1, steps);