Source code for submission s761

Go to diff to previous submission

hop.cc

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstdlib>
  10. #include <cstring>
  11. #include <sstream>
  12.  
  13. #include <stdio.h>
  14. #include <ctype.h>
  15. #include <math.h>
  16. #include <string.h>
  17. #include <stdlib.h>
  18.  
  19. using namespace std;
  20.  
  21. #define X first
  22. #define Y second
  23. #define MP make_pair
  24. #define PB push_back
  25. #define SZ size
  26.  
  27. int over(int akt, int akt2, int a, int b) {
  28.             if (akt - 1 > 0 && akt2 - 2 > 0)
  29.                return 1;
  30.             if (akt - 2 > 0 && akt2 - 1 > 0)
  31.                return 1;
  32.             if (akt + 1 <= a && akt2 - 2 > 0)
  33.                return 1;
  34.             if (akt + 2 <= a && akt2 - 1 > 0)
  35.                return 1;
  36.             if (akt - 1 > 0 && akt2 +2 <= b)
  37.                return 1;
  38.             if (akt - 2 > 0 && akt2 +1 <= b)
  39.                return 1;
  40.             if (akt + 1 <= a && akt2 + 2 <= b)
  41.                return 1;
  42.             if (akt + 1 <= a && akt2 + 2 <= b)
  43.                return 1;
  44.             return 0;
  45. }
  46.  
  47. int main(void) {
  48.    int a, b, c, d, e, f, g, aa, i, ii, akt, akt2, j, k, tah;
  49.    while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) > 0) {
  50.       if (over(c, d, a, b) == 0) {
  51.          j = abs(c - e);
  52.          k = abs(d - f);
  53.          if (j + k == 0)
  54.             printf("0\n");
  55.          else
  56.             printf("impossible\n");
  57.       } else {
  58.          j = abs(c - e);
  59.          k = abs(d - f);
  60.          tah = 0;
  61.          while (j + k > 2) {
  62.             if (j > k) {
  63.                j = j - 2;
  64.                if (k > 0)
  65.                   k = k - 1;
  66.                else
  67.                   k = k + 1;
  68.             } else {
  69.                if (j > 0)
  70.                   j = j - 1;
  71.                else
  72.                   j = j + 1;
  73.                k = k - 2;
  74.             }
  75.             tah++;
  76.          }
  77.          if (j == 1 && k == 1)
  78.             tah = tah + 2;
  79.          if (j + k == 1)
  80.             tah = tah + 3;
  81.          if ((j == 0 && k == 2) || (j == 2 && k == 0))
  82.             tah = tah + 2;
  83.          printf("%d\n", tah);
  84.       }
  85.    }
  86.    return 0;
  87. }
  88.  

Diff to submission s687

sablona.cc

--- c4.s687.cteam079.grasshop.cpp.0.sablona.cc
+++ c4.s761.cteam079.grasshop.cpp.0.hop.cc
@@ -25,94 +25,63 @@
 #define SZ size
 
-int main(void)
-{
-   int a, b, c, d, e, f, g, aa, i, ii, akt, akt2, j, k;
-   int vrcholy[110][110];
-   int uz[110][110];
-   while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) > 0) {
-      for (i = 1; i <= a; i++) {
-         for (ii = 1; ii <= b; ii++) {
-            vrcholy[i][ii] = 9999999;
-            uz[i][ii] = -1;
-         }
-      }
-      vrcholy[c][d] = 0;
-      uz[c][d] = 1;
-      akt = c;
-      akt2 = d;
-      if (akt - 1 > 0 && akt2 - 2 > 0)
-               if (vrcholy[akt - 1][akt2 - 2] > vrcholy[akt][akt2])
-                  vrcholy[akt-1][akt2 - 2] = vrcholy[akt][akt2] + 1;
-            if (akt - 2 > 0 && akt2 - 1 > 0)
-               if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2])
-                  vrcholy[akt-2][akt2 - 1] = vrcholy[akt][akt2] + 1;
-            if (akt + 1 <= a && akt2 - 2 > 0)
-               if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2])
-                  vrcholy[akt+1][akt2 - 2] = vrcholy[akt][akt2] + 1;
-            if (akt + 2 <= a && akt2 - 1 > 0)
-               if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2])
-                  vrcholy[akt+2][akt2 - 1] = vrcholy[akt][akt2] + 1;
-            if (akt - 1 > 0 && akt2 +2 <= b)
-               if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2])
-                  vrcholy[akt-1][akt2 + 2] = vrcholy[akt][akt2] + 1;
-            if (akt - 2 > 0 && akt2 +1 <= b)
-               if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2])
-                  vrcholy[akt-2][akt2 +1] = vrcholy[akt][akt2] + 1;
-            if (akt + 1 <= a && akt2 + 2 <= b)
-               if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2])
-                  vrcholy[akt+1][akt2 + 2] = vrcholy[akt][akt2] + 1;
-            if (akt + 1 <= a && akt2 + 2 <= b)
-               if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2])
-                  vrcholy[akt+1][akt2 + 2] = vrcholy[akt][akt2] + 1;
-      for (i = 1; i <= a; i++) {
-         for (ii = 1; ii <= b; ii++) {
-            akt = -1;
-            akt2 = -1;
-            for (j = 1; j <= a; j++) {
-               for (k = 1; k <= b; k++) {
-                  if (uz[j][k] == -1 && (akt == -1 || vrcholy[j][k] < vrcholy[akt][akt2]) && vrcholy[j][k] != 9999999) {
-                     akt = j;
-                     akt2 = k;
-                  }
-               }
-            }
-            if (akt != -1) {
-            uz[akt][akt2] = 1;
+int over(int akt, int akt2, int a, int b) {
             if (akt - 1 > 0 && akt2 - 2 > 0)
-               if (vrcholy[akt - 1][akt2 - 2] > vrcholy[akt][akt2])
-                  vrcholy[akt-1][akt2 - 2] = vrcholy[akt][akt2] + 1;
+               return 1;
             if (akt - 2 > 0 && akt2 - 1 > 0)
-               if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2])
-                  vrcholy[akt-2][akt2 - 1] = vrcholy[akt][akt2] + 1;
+               return 1;
             if (akt + 1 <= a && akt2 - 2 > 0)
-               if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2])
-                  vrcholy[akt+1][akt2 - 2] = vrcholy[akt][akt2] + 1;
+               return 1;
             if (akt + 2 <= a && akt2 - 1 > 0)
-               if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2])
-                  vrcholy[akt+2][akt2 - 1] = vrcholy[akt][akt2] + 1;
+               return 1;
             if (akt - 1 > 0 && akt2 +2 <= b)
-               if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2])
-                  vrcholy[akt-1][akt2 + 2] = vrcholy[akt][akt2] + 1;
+               return 1;
             if (akt - 2 > 0 && akt2 +1 <= b)
-               if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2])
-                  vrcholy[akt-2][akt2 +1] = vrcholy[akt][akt2] + 1;
+               return 1;
             if (akt + 1 <= a && akt2 + 2 <= b)
-               if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2])
-                  vrcholy[akt+1][akt2 + 2] = vrcholy[akt][akt2] + 1;
+               return 1;
             if (akt + 1 <= a && akt2 + 2 <= b)
-               if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2])
-                  vrcholy[akt+1][akt2 + 2] = vrcholy[akt][akt2] + 1;
+               return 1;
+            return 0;
+}
+
+int main(void) {
+   int a, b, c, d, e, f, g, aa, i, ii, akt, akt2, j, k, tah;
+   while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) > 0) {
+      if (over(c, d, a, b) == 0) {
+         j = abs(c - e);
+         k = abs(d - f);
+         if (j + k == 0)
+            printf("0\n");
+         else
+            printf("impossible\n");
+      } else {
+         j = abs(c - e);
+         k = abs(d - f);
+         tah = 0;
+         while (j + k > 2) {
+            if (j > k) {
+               j = j - 2;
+               if (k > 0)
+                  k = k - 1;
+               else
+                  k = k + 1;
             } else {
-               break;
+               if (j > 0)
+                  j = j - 1;
+               else
+                  j = j + 1;
+               k = k - 2;
             }
+            tah++;
          }
+         if (j == 1 && k == 1)
+            tah = tah + 2;
+         if (j + k == 1)
+            tah = tah + 3;
+         if ((j == 0 && k == 2) || (j == 2 && k == 0))
+            tah = tah + 2;
+         printf("%d\n", tah);
       }
-      if (vrcholy[e][f] != 9999999)
-         printf("%d\n", vrcholy[e][f]);
-      else
-         printf("impossible\n");
    }
-
-
    return 0;
 }