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 #define LEFT(i) 2*(i) #define RIGHT(i) 2*(i)+1 #define PARENT(i) (i)/2 struct HeapVrchol { pair<int, int> vrchol; int value; }; struct HeapVrchol heap[10000]; int heapSize = 0; void vymenCisla(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } void heapify(struct HeapVrchol *heap, int i, int heapSize) { int najvacsi; pair<int, int> tmp; int l = LEFT(i); int r = RIGHT(i); najvacsi = (((l <= heapSize) && (heap[l].value < heap[i].value)) ? l : i); if((r <= heapSize) && (heap[r].value < heap[najvacsi].value)) najvacsi = r; if(najvacsi != i) { vymenCisla(&(heap[i].value), &(heap[najvacsi].value)); tmp = heap[i].vrchol; heap[i].vrchol = heap[najvacsi].vrchol; heap[najvacsi].vrchol = tmp; heapify(heap, najvacsi, heapSize); } } void heapInsert(pair<int, int> vrchol, int dlzka) { heapSize++; int i = heapSize; if(heapSize == 1) { heap[i].vrchol = vrchol; heap[i].value = dlzka; return ; } while(i > 1 && heap[PARENT(i)].value > dlzka) { heap[i].value = heap[PARENT(i)].value; heap[i].vrchol = heap[PARENT(i)].vrchol; i = PARENT(i); } heap[i].vrchol = vrchol; heap[i].value = dlzka; } pair<int, int> heapNajmensiVrchol() { pair<int, int> min; //printf("%d\n", heapSize); if (heapSize > 0) { min = heap[1].vrchol; heap[1] = heap[heapSize]; heapSize--; heapify(heap, 1, heapSize); return min; } min = MP(-1, -1); return min; } 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]; pair <int, int> pom; while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) > 0) { heapSize = 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] && uz[akt - 1][akt2 - 2] == -1) { vrcholy[akt - 1][akt2 - 2] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt-1, akt2 - 2), vrcholy[akt][akt2] + 1); } if (akt - 2 > 0 && akt2 - 1 > 0) if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 - 1] == -1) { vrcholy[akt - 2][akt2 - 1] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt-2, akt2 - 1), vrcholy[akt][akt2] + 1); } if (akt + 1 <= a && akt2 - 2 > 0) if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 - 2] == -1) { vrcholy[akt + 1][akt2 - 2] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt+1, akt2-2), vrcholy[akt][akt2] + 1); } if (akt + 2 <= a && akt2 - 1 > 0) if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 - 1] == -1) { vrcholy[akt + 2][akt2 - 1] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt+2, akt2-1), vrcholy[akt][akt2] + 1); } if (akt - 1 > 0 && akt2 +2 <= b) if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 + 2] == -1) { vrcholy[akt - 1][akt2 + 2] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt-1, akt2+2), vrcholy[akt][akt2] + 1); } if (akt - 2 > 0 && akt2 +1 <= b) if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 +1] == -1) { vrcholy[akt - 2][akt2 +1] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt-2, akt2+1), vrcholy[akt][akt2] + 1); } if (akt + 1 <= a && akt2 + 2 <= b) if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 + 2] == -1) { vrcholy[akt + 1][akt2 + 2] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt+1, akt2+2), vrcholy[akt][akt2] + 1); } if (akt + 2 <= a && akt2 + 1 <= b) if (vrcholy[akt + 2][akt2 + 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 + 1] == -1) { vrcholy[akt + 2][akt2 + 1] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt+2, akt2+1), vrcholy[akt][akt2] + 1); } int ok = 1; while (ok == 1) { 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; } } }*/ pom = heapNajmensiVrchol(); akt = pom.first; akt2 = pom.second; //printf("%d %d\n", akt, akt2); if (akt != -1) { uz[akt][akt2] = 1; /*if (akt == 5 && akt2 == 3) printf("uch %d %d %d\n", uz[3][2], vrcholy[3][2], heapSize);*/ if (akt - 1 > 0 && akt2 - 2 > 0) if (vrcholy[akt - 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 - 2] == -1) { vrcholy[akt - 1][akt2 - 2] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt-1, akt2 - 2), vrcholy[akt][akt2] + 1); } if (akt - 2 > 0 && akt2 - 1 > 0) if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 - 1] == -1) { vrcholy[akt - 2][akt2 - 1] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt-2, akt2 - 1), vrcholy[akt][akt2] + 1); } if (akt + 1 <= a && akt2 - 2 > 0) if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 - 2] == -1) { vrcholy[akt + 1][akt2 - 2] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt+1, akt2-2), vrcholy[akt][akt2] + 1); } if (akt + 2 <= a && akt2 - 1 > 0) if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 - 1] == -1) { vrcholy[akt + 2][akt2 - 1] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt+2, akt2-1), vrcholy[akt][akt2] + 1); } if (akt - 1 > 0 && akt2 +2 <= b) if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 + 2] == -1) { vrcholy[akt - 1][akt2 + 2] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt-1, akt2+2), vrcholy[akt][akt2] + 1); } if (akt - 2 > 0 && akt2 +1 <= b) if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 +1] == -1) { vrcholy[akt - 2][akt2 +1] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt-2, akt2+1), vrcholy[akt][akt2] + 1); } if (akt + 1 <= a && akt2 + 2 <= b) if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 + 2] == -1) { vrcholy[akt + 1][akt2 + 2] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt+1, akt2+2), vrcholy[akt][akt2] + 1); } if (akt + 2 <= a && akt2 + 1 <= b) if (vrcholy[akt + 2][akt2 + 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 + 1] == -1) { vrcholy[akt + 2][akt2 + 1] = vrcholy[akt][akt2] + 1; heapInsert(MP(akt+2, akt2+1), vrcholy[akt][akt2] + 1); } } else { ok = 0; } } if (vrcholy[e][f] != 9999999) printf("%d\n", vrcholy[e][f]); else printf("impossible\n"); } return 0; }
--- c4.s761.cteam079.grasshop.cpp.0.hop.cc +++ c4.s983.cteam079.grasshop.cpp.0.sablona.cc @@ -24,64 +24,224 @@ #define PB push_back #define SZ size +#define LEFT(i) 2*(i) +#define RIGHT(i) 2*(i)+1 +#define PARENT(i) (i)/2 -int over(int akt, int akt2, int a, int b) { - if (akt - 1 > 0 && akt2 - 2 > 0) - return 1; +struct HeapVrchol +{ + pair<int, int> vrchol; + int value; +}; + +struct HeapVrchol heap[10000]; +int heapSize = 0; + +void vymenCisla(int *a, int *b) +{ + int tmp = *a; + + *a = *b; + *b = tmp; +} + +void heapify(struct HeapVrchol *heap, int i, int heapSize) +{ + int najvacsi; + pair<int, int> tmp; + + int l = LEFT(i); + int r = RIGHT(i); + + najvacsi = (((l <= heapSize) && (heap[l].value < heap[i].value)) ? l : i); + + if((r <= heapSize) && (heap[r].value < heap[najvacsi].value)) + najvacsi = r; + + if(najvacsi != i) + { + vymenCisla(&(heap[i].value), &(heap[najvacsi].value)); + tmp = heap[i].vrchol; + heap[i].vrchol = heap[najvacsi].vrchol; + heap[najvacsi].vrchol = tmp; + + heapify(heap, najvacsi, heapSize); + } +} + + +void heapInsert(pair<int, int> vrchol, int dlzka) +{ + heapSize++; + int i = heapSize; + + if(heapSize == 1) + { + heap[i].vrchol = vrchol; + heap[i].value = dlzka; + + return ; + + } + + while(i > 1 && heap[PARENT(i)].value > dlzka) + { + heap[i].value = heap[PARENT(i)].value; + heap[i].vrchol = heap[PARENT(i)].vrchol; + i = PARENT(i); + } + + + heap[i].vrchol = vrchol; + heap[i].value = dlzka; +} + +pair<int, int> heapNajmensiVrchol() +{ + pair<int, int> min; + //printf("%d\n", heapSize); + if (heapSize > 0) { + min = heap[1].vrchol; + heap[1] = heap[heapSize]; + + heapSize--; + + heapify(heap, 1, heapSize); + + return min; + } + min = MP(-1, -1); + return min; + +} + +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]; + pair <int, int> pom; + while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) > 0) { + heapSize = 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] && uz[akt - 1][akt2 - 2] == -1) { + vrcholy[akt - 1][akt2 - 2] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt-1, akt2 - 2), vrcholy[akt][akt2] + 1); + } if (akt - 2 > 0 && akt2 - 1 > 0) - return 1; + if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 - 1] == -1) { + vrcholy[akt - 2][akt2 - 1] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt-2, akt2 - 1), vrcholy[akt][akt2] + 1); + } if (akt + 1 <= a && akt2 - 2 > 0) - return 1; + if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 - 2] == -1) { + vrcholy[akt + 1][akt2 - 2] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt+1, akt2-2), vrcholy[akt][akt2] + 1); + } if (akt + 2 <= a && akt2 - 1 > 0) - return 1; + if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 - 1] == -1) { + vrcholy[akt + 2][akt2 - 1] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt+2, akt2-1), vrcholy[akt][akt2] + 1); + } if (akt - 1 > 0 && akt2 +2 <= b) - return 1; + if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 + 2] == -1) { + vrcholy[akt - 1][akt2 + 2] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt-1, akt2+2), vrcholy[akt][akt2] + 1); + } if (akt - 2 > 0 && akt2 +1 <= b) - return 1; + if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 +1] == -1) { + vrcholy[akt - 2][akt2 +1] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt-2, akt2+1), vrcholy[akt][akt2] + 1); + } if (akt + 1 <= a && akt2 + 2 <= b) - return 1; + if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 + 2] == -1) { + vrcholy[akt + 1][akt2 + 2] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt+1, akt2+2), vrcholy[akt][akt2] + 1); + } + if (akt + 2 <= a && akt2 + 1 <= b) + if (vrcholy[akt + 2][akt2 + 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 + 1] == -1) { + vrcholy[akt + 2][akt2 + 1] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt+2, akt2+1), vrcholy[akt][akt2] + 1); + } + int ok = 1; + while (ok == 1) { + 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; + } + } + }*/ + pom = heapNajmensiVrchol(); + akt = pom.first; + akt2 = pom.second; + //printf("%d %d\n", akt, akt2); + if (akt != -1) { + uz[akt][akt2] = 1; + /*if (akt == 5 && akt2 == 3) + printf("uch %d %d %d\n", uz[3][2], vrcholy[3][2], heapSize);*/ + if (akt - 1 > 0 && akt2 - 2 > 0) + if (vrcholy[akt - 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 - 2] == -1) { + vrcholy[akt - 1][akt2 - 2] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt-1, akt2 - 2), vrcholy[akt][akt2] + 1); + } + if (akt - 2 > 0 && akt2 - 1 > 0) + if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 - 1] == -1) { + vrcholy[akt - 2][akt2 - 1] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt-2, akt2 - 1), vrcholy[akt][akt2] + 1); + } + if (akt + 1 <= a && akt2 - 2 > 0) + if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 - 2] == -1) { + vrcholy[akt + 1][akt2 - 2] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt+1, akt2-2), vrcholy[akt][akt2] + 1); + } + if (akt + 2 <= a && akt2 - 1 > 0) + if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 - 1] == -1) { + vrcholy[akt + 2][akt2 - 1] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt+2, akt2-1), vrcholy[akt][akt2] + 1); + } + if (akt - 1 > 0 && akt2 +2 <= b) + if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 + 2] == -1) { + vrcholy[akt - 1][akt2 + 2] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt-1, akt2+2), vrcholy[akt][akt2] + 1); + } + if (akt - 2 > 0 && akt2 +1 <= b) + if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 +1] == -1) { + vrcholy[akt - 2][akt2 +1] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt-2, akt2+1), vrcholy[akt][akt2] + 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; + if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 + 2] == -1) { + vrcholy[akt + 1][akt2 + 2] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt+1, akt2+2), vrcholy[akt][akt2] + 1); + } + if (akt + 2 <= a && akt2 + 1 <= b) + if (vrcholy[akt + 2][akt2 + 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 + 1] == -1) { + vrcholy[akt + 2][akt2 + 1] = vrcholy[akt][akt2] + 1; + heapInsert(MP(akt+2, akt2+1), vrcholy[akt][akt2] + 1); + } } else { - if (j > 0) - j = j - 1; - else - j = j + 1; - k = k - 2; + ok = 0; } - 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; }