Source code for submission s716

Go to diff to previous submission

grasshop.cpp

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <queue>
  4. #include <set>
  5.  
  6. #define getc() getc(stdin)
  7. typedef unsigned int uint;
  8. using namespace std;
  9.  
  10. struct pos {
  11. int r;
  12. int c;
  13. int jumps;
  14. };
  15.  
  16. int main()
  17. {
  18. int rMod[8] = {2,2,1,-1,-2,-2,-1,1};
  19. int cMod[8] = {-1,1,2,2,1,-1,-2,-2};
  20.  
  21. int R = 0, C = 0, GR = 0, GC = 0, LR = 0, LC = 0;
  22. while (scanf("%d%d%d%d%d%d", &R, &C, &GR, &GC, &LR, &LC) != EOF) {
  23. queue<pos> q;
  24. pos start;
  25. set<pair<int, int> > positions;
  26. start.r = GR;
  27. start.c = GC;
  28. start.jumps = 0;
  29. q.push(start);
  30. positions.insert(make_pair(start.r, start.c));
  31. bool done = false;
  32. while (!q.empty() && !done) {
  33. pos oldPos = q.front();
  34. q.pop();
  35. oldPos.jumps++;
  36. for (int i = 0; i < 8; i++) {
  37. pos newPos;
  38. newPos.jumps = oldPos.jumps;
  39. newPos.r = oldPos.r + rMod[i];
  40. newPos.c = oldPos.c + cMod[i];
  41. if (newPos.c == LC && newPos.r == LR) {
  42. printf("%d\n", newPos.jumps);
  43. done = true;
  44. break;
  45. }
  46. if (newPos.r <= R && newPos.r >= 1 &&
  47. newPos.c <= C && newPos.c >= 1) {
  48. if (positions.insert(make_pair(newPos.r, newPos.c)).second)
  49. {
  50. q.push(newPos);
  51. }
  52. }
  53. }
  54. }
  55.  
  56. if (!done) {
  57. printf("impossible\n");
  58. }
  59. }
  60. return 0;
  61. }
  62.  
  63.  

Diff to submission s689

grasshop.cpp

--- c4.s689.cteam093.grasshop.cpp.0.grasshop.cpp
+++ c4.s716.cteam093.grasshop.cpp.0.grasshop.cpp
@@ -24,28 +24,26 @@
         pos start;
         set<pair<int, int> > positions;
-        start.c = GC;
         start.r = GR;
+        start.c = GC;
         start.jumps = 0;
         q.push(start);
-        positions.insert(make_pair(GR, GC));
-
-        while (!q.empty()) {
-
+        positions.insert(make_pair(start.r, start.c));
+        bool done = false;
+        while (!q.empty() && !done) {
             pos oldPos = q.front();
             q.pop();
-
-            if (oldPos.c == LC && oldPos.r == LR) {
-                printf("%d\n", oldPos.jumps);
-                break;
-            }
-
             oldPos.jumps++;
             for (int i = 0; i < 8; i++) {
-                if (oldPos.r + rMod[i] <= R && oldPos.r + rMod[i] >= 1 &&
-                        oldPos.c + cMod[i] <= C && oldPos.c + cMod[i] >= 1) {
-                    pos newPos;
-                    newPos.jumps = oldPos.jumps;
-                    newPos.r = oldPos.r + rMod[i];
-                    newPos.c = oldPos.c + cMod[i];
+                pos newPos;
+                newPos.jumps = oldPos.jumps;
+                newPos.r = oldPos.r + rMod[i];
+                newPos.c = oldPos.c + cMod[i];
+                if (newPos.c == LC && newPos.r == LR) {
+                    printf("%d\n", newPos.jumps);
+                    done = true;
+                    break;
+                }
+                if (newPos.r <= R && newPos.r >= 1 &&
+                        newPos.c <= C && newPos.c >= 1) {
                     if (positions.insert(make_pair(newPos.r, newPos.c)).second)
                     {
@@ -56,9 +54,8 @@
         }
 
-        if (q.empty()) {
+        if (!done) {
             printf("impossible\n");
         }
     }
-    // cout << "Hello World!" << endl;
     return 0;
 }