Source code for submission s655

grasshop.cpp

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <deque>
  4.  
  5. struct Point {
  6. int x, y;
  7.  
  8. Point(int x_, int y_) : x(x_), y(y_) {}
  9. };
  10.  
  11. int r, c, gr, gc, lr, lc;
  12. std::deque<Point> q;
  13.  
  14. void addPoint(int x, int y, bool* seen) {
  15. if (!seen[y * c + x] && x >= 0 && y >= 0 && x < c && y < r) {
  16. q.push_back(Point(x, y));
  17. seen[y * c + x] = true;
  18. }
  19. }
  20.  
  21. int main() {
  22. while (scanf("%d %d %d %d %d %d\n", &r, &c, &gr, &gc, &lr, &lc) != EOF) {
  23. --gr;
  24. --gc;
  25. --lr;
  26. --lc;
  27.  
  28. bool seen[r * c];
  29. memset(seen, 0, r * c);
  30.  
  31. q.push_back(Point(gc, gr));
  32. seen[gr * c + gc] = true;
  33.  
  34. q.push_back(Point(-5, -5));
  35.  
  36. int count = 0;
  37.  
  38. while (q.size() > 1) {
  39. Point p = q.front();
  40. q.pop_front();
  41. int x = p.x;
  42. int y = p.y;
  43. if (x == lc && y == lr) {
  44. printf("%d\n", count);
  45. goto clearLabel;
  46. } else if (x == -5) {
  47. ++count;
  48. q.push_back(Point(-5, -5));
  49. continue;
  50. }
  51.  
  52. addPoint(x - 2, y - 1, seen);
  53. addPoint(x - 1, y - 2, seen);
  54. addPoint(x + 1, y - 2, seen);
  55. addPoint(x + 2, y - 1, seen);
  56. addPoint(x + 2, y + 1, seen);
  57. addPoint(x + 1, y + 2, seen);
  58. addPoint(x - 1, y + 2, seen);
  59. addPoint(x - 2, y + 1, seen);
  60. }
  61.  
  62. printf("impossible\n");
  63.  
  64. clearLabel:
  65. q.clear();
  66. }
  67.  
  68. return 0;
  69. }
  70.