Go to diff to previous submission
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <cstring> #include <sstream> #include <stdio.h> #include <ctype.h> #include <math.h> #include <string.h> #include <stdlib.h> using namespace std; #define X first #define Y second #define MP make_pair #define PB push_back #define SZ size int over(int akt, int akt2, int a, int b) { if (akt - 1 > 0 && akt2 - 2 > 0) return 1; if (akt - 2 > 0 && akt2 - 1 > 0) return 1; if (akt + 1 <= a && akt2 - 2 > 0) return 1; if (akt + 2 <= a && akt2 - 1 > 0) return 1; if (akt - 1 > 0 && akt2 +2 <= b) return 1; if (akt - 2 > 0 && akt2 +1 <= b) return 1; if (akt + 1 <= a && akt2 + 2 <= b) return 1; if (akt + 1 <= a && akt2 + 2 <= b) 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 { 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); } } return 0; }
--- 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; }