Source code for submission s998

Go to diff to previous submission

sablona.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. #define LEFT(i) 2*(i)
  27. #define RIGHT(i) 2*(i)+1
  28. #define PARENT(i) (i)/2
  29.  
  30. struct HeapVrchol
  31. {
  32.    pair<int, int> vrchol;
  33.    int value;
  34. };
  35.  
  36. struct HeapVrchol heap[10000];
  37. int heapSize = 0;
  38.  
  39. void vymenCisla(int *a, int *b)
  40. {
  41.    int tmp = *a;
  42.  
  43.    *a = *b;
  44.    *b = tmp;
  45. }
  46.  
  47. void heapify(struct HeapVrchol *heap, int i, int heapSize)
  48. {
  49.    int najvacsi;
  50.    pair<int, int> tmp;
  51.  
  52.    int l = LEFT(i);
  53.    int r = RIGHT(i);
  54.  
  55.    najvacsi = (((l <= heapSize) && (heap[l].value < heap[i].value)) ? l : i);
  56.  
  57.    if((r <= heapSize) && (heap[r].value < heap[najvacsi].value))
  58.       najvacsi = r;
  59.  
  60.    if(najvacsi != i)
  61.    {
  62.       vymenCisla(&(heap[i].value), &(heap[najvacsi].value));
  63.       tmp = heap[i].vrchol;
  64.       heap[i].vrchol = heap[najvacsi].vrchol;
  65.       heap[najvacsi].vrchol = tmp;
  66.  
  67.       heapify(heap, najvacsi, heapSize);
  68.    }
  69. }
  70.  
  71.  
  72. void heapInsert(pair<int, int> vrchol, int dlzka)
  73. {
  74.    heapSize++;
  75.    int i = heapSize;
  76.  
  77.    if(heapSize == 1)
  78.    {
  79.       heap[i].vrchol = vrchol;
  80.       heap[i].value = dlzka;
  81.  
  82.       return ;
  83.  
  84.    }
  85.  
  86.    while(i > 1 && heap[PARENT(i)].value > dlzka)
  87.    {
  88.       heap[i].value = heap[PARENT(i)].value;
  89.       heap[i].vrchol = heap[PARENT(i)].vrchol;
  90.       i = PARENT(i);
  91.    }
  92.  
  93.  
  94.    heap[i].vrchol = vrchol;
  95.    heap[i].value = dlzka;
  96. }
  97.  
  98. pair<int, int> heapNajmensiVrchol()
  99. {
  100.    pair<int, int> min;
  101.    //printf("%d\n", heapSize);
  102.    if (heapSize > 0) {
  103.       min = heap[1].vrchol;
  104.       heap[1] = heap[heapSize];
  105.  
  106.       heapSize--;
  107.  
  108.       heapify(heap, 1, heapSize);
  109.  
  110.       return min;
  111.    }
  112.    min = MP(-1, -1);
  113.    return min;
  114.  
  115. }
  116.  
  117. int main(void)
  118. {
  119.    int a, b, c, d, e, f, g, aa, i, ii, akt, akt2, j, k;
  120.    int vrcholy[110][110];
  121.    int uz[110][110];
  122.    pair <int, int> pom;
  123.    while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) > 0) {
  124.       heapSize = 0;
  125.       for (i = 1; i <= a; i++) {
  126.          for (ii = 1; ii <= b; ii++) {
  127.             vrcholy[i][ii] = 999999999;
  128.             uz[i][ii] = -1;
  129.          }
  130.       }
  131.       vrcholy[c][d] = 0;
  132.       uz[c][d] = 1;
  133.       akt = c;
  134.       akt2 = d;
  135.       if (akt - 1 > 0 && akt2 - 2 > 0)
  136.                if (vrcholy[akt - 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 - 2] == -1) {
  137.                   vrcholy[akt - 1][akt2 - 2] = vrcholy[akt][akt2] + 1;
  138.                   heapInsert(MP(akt-1, akt2 - 2), vrcholy[akt][akt2] + 1);
  139.                }
  140.             if (akt - 2 > 0 && akt2 - 1 > 0)
  141.                if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 - 1] == -1) {
  142.                   vrcholy[akt - 2][akt2 - 1] = vrcholy[akt][akt2] + 1;
  143.                   heapInsert(MP(akt-2, akt2 - 1), vrcholy[akt][akt2] + 1);
  144.                }
  145.             if (akt + 1 <= a && akt2 - 2 > 0)
  146.                if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 - 2] == -1) {
  147.                   vrcholy[akt + 1][akt2 - 2] = vrcholy[akt][akt2] + 1;
  148.                   heapInsert(MP(akt+1, akt2-2), vrcholy[akt][akt2] + 1);
  149.                }
  150.             if (akt + 2 <= a && akt2 - 1 > 0)
  151.                if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 - 1] == -1) {
  152.                   vrcholy[akt + 2][akt2 - 1] = vrcholy[akt][akt2] + 1;
  153.                   heapInsert(MP(akt+2, akt2-1), vrcholy[akt][akt2] + 1);
  154.                }
  155.             if (akt - 1 > 0 && akt2 +2 <= b)
  156.                if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 + 2] == -1) {
  157.                   vrcholy[akt - 1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  158.                   heapInsert(MP(akt-1, akt2+2), vrcholy[akt][akt2] + 1);
  159.                }
  160.             if (akt - 2 > 0 && akt2 +1 <= b)
  161.                if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 +1] == -1) {
  162.                   vrcholy[akt - 2][akt2 +1] = vrcholy[akt][akt2] + 1;
  163.                   heapInsert(MP(akt-2, akt2+1), vrcholy[akt][akt2] + 1);
  164.                }
  165.             if (akt + 1 <= a && akt2 + 2 <= b)
  166.                if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 + 2] == -1) {
  167.                   vrcholy[akt + 1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  168.                   heapInsert(MP(akt+1, akt2+2), vrcholy[akt][akt2] + 1);
  169.                }
  170.             if (akt + 2 <= a && akt2 + 1 <= b)
  171.                if (vrcholy[akt + 2][akt2 + 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 + 1] == -1) {
  172.                   vrcholy[akt + 2][akt2 + 1] = vrcholy[akt][akt2] + 1;
  173.                   heapInsert(MP(akt+2, akt2+1), vrcholy[akt][akt2] + 1);
  174.                }
  175.                int ok = 1;
  176.       while (ok == 1) {
  177.             akt = -1;
  178.             akt2 = -1;
  179.             /*for (j = 1; j <= a; j++) {
  180.                for (k = 1; k <= b; k++) {
  181.                   if (uz[j][k] == -1 && (akt == -1 || vrcholy[j][k] < vrcholy[akt][akt2]) && vrcholy[j][k] != 9999999) {
  182.                      akt = j;
  183.                      akt2 = k;
  184.                   }
  185.                }
  186.             }*/
  187.             pom = heapNajmensiVrchol();
  188.             akt = pom.first;
  189.             akt2 = pom.second;
  190.             //printf("%d %d\n", akt, akt2);
  191.             if (akt != -1 && !(akt == c && akt2 == d)) {
  192.             uz[akt][akt2] = 1;
  193.             /*if (akt == 5 && akt2 == 3)
  194.                printf("uch %d %d %d\n", uz[3][2], vrcholy[3][2], heapSize);*/
  195.             if (akt - 1 > 0 && akt2 - 2 > 0)
  196.                if (vrcholy[akt - 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 - 2] == -1) {
  197.                   vrcholy[akt - 1][akt2 - 2] = vrcholy[akt][akt2] + 1;
  198.                   heapInsert(MP(akt-1, akt2 - 2), vrcholy[akt][akt2] + 1);
  199.                }
  200.             if (akt - 2 > 0 && akt2 - 1 > 0)
  201.                if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 - 1] == -1) {
  202.                   vrcholy[akt - 2][akt2 - 1] = vrcholy[akt][akt2] + 1;
  203.                   heapInsert(MP(akt-2, akt2 - 1), vrcholy[akt][akt2] + 1);
  204.                }
  205.             if (akt + 1 <= a && akt2 - 2 > 0)
  206.                if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 - 2] == -1) {
  207.                   vrcholy[akt + 1][akt2 - 2] = vrcholy[akt][akt2] + 1;
  208.                   heapInsert(MP(akt+1, akt2-2), vrcholy[akt][akt2] + 1);
  209.                }
  210.             if (akt + 2 <= a && akt2 - 1 > 0)
  211.                if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 - 1] == -1) {
  212.                   vrcholy[akt + 2][akt2 - 1] = vrcholy[akt][akt2] + 1;
  213.                   heapInsert(MP(akt+2, akt2-1), vrcholy[akt][akt2] + 1);
  214.                }
  215.             if (akt - 1 > 0 && akt2 +2 <= b)
  216.                if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 + 2] == -1) {
  217.                   vrcholy[akt - 1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  218.                   heapInsert(MP(akt-1, akt2+2), vrcholy[akt][akt2] + 1);
  219.                }
  220.             if (akt - 2 > 0 && akt2 +1 <= b)
  221.                if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 +1] == -1) {
  222.                   vrcholy[akt - 2][akt2 +1] = vrcholy[akt][akt2] + 1;
  223.                   heapInsert(MP(akt-2, akt2+1), vrcholy[akt][akt2] + 1);
  224.                }
  225.             if (akt + 1 <= a && akt2 + 2 <= b)
  226.                if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 + 2] == -1) {
  227.                   vrcholy[akt + 1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  228.                   heapInsert(MP(akt+1, akt2+2), vrcholy[akt][akt2] + 1);
  229.                }
  230.             if (akt + 2 <= a && akt2 + 1 <= b)
  231.                if (vrcholy[akt + 2][akt2 + 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 + 1] == -1) {
  232.                   vrcholy[akt + 2][akt2 + 1] = vrcholy[akt][akt2] + 1;
  233.                   heapInsert(MP(akt+2, akt2+1), vrcholy[akt][akt2] + 1);
  234.                }
  235.             } else {
  236.                ok = 0;
  237.             }
  238.       }
  239.       if (vrcholy[e][f] != 999999999)
  240.          printf("%d\n", vrcholy[e][f]);
  241.       else
  242.          printf("impossible\n");
  243.    }
  244.  
  245.  
  246.    return 0;
  247. }
  248.  

Diff to submission s983

sablona.cc

--- c4.s983.cteam079.grasshop.cpp.0.sablona.cc
+++ c4.s998.cteam079.grasshop.cpp.0.sablona.cc
@@ -125,5 +125,5 @@
       for (i = 1; i <= a; i++) {
          for (ii = 1; ii <= b; ii++) {
-            vrcholy[i][ii] = 9999999;
+            vrcholy[i][ii] = 999999999;
             uz[i][ii] = -1;
          }
@@ -189,5 +189,5 @@
             akt2 = pom.second;
             //printf("%d %d\n", akt, akt2);
-            if (akt != -1) {
+            if (akt != -1 && !(akt == c && akt2 == d)) {
             uz[akt][akt2] = 1;
             /*if (akt == 5 && akt2 == 3)
@@ -237,5 +237,5 @@
             }
       }
-      if (vrcholy[e][f] != 9999999)
+      if (vrcholy[e][f] != 999999999)
          printf("%d\n", vrcholy[e][f]);
       else