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] = 999999999; 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 && !(akt == e && akt2 == f)) { 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] != 999999999) printf("%d\n", vrcholy[e][f]); else printf("impossible\n"); for (i = 0; i < heapSize; i++) heap[i].value = 999999999; } return 0; }
--- c4.s998.cteam079.grasshop.cpp.0.sablona.cc +++ c4.s1008.cteam079.grasshop.cpp.0.sablona.cc @@ -189,5 +189,5 @@ akt2 = pom.second; //printf("%d %d\n", akt, akt2); - if (akt != -1 && !(akt == c && akt2 == d)) { + if (akt != -1 && !(akt == e && akt2 == f)) { uz[akt][akt2] = 1; /*if (akt == 5 && akt2 == 3) @@ -241,4 +241,6 @@ else printf("impossible\n"); + for (i = 0; i < heapSize; i++) + heap[i].value = 999999999; }