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;
 }