Source code for submission s983

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] = 9999999;
  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) {
  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] != 9999999)
  240.          printf("%d\n", vrcholy[e][f]);
  241.       else
  242.          printf("impossible\n");
  243.    }
  244.  
  245.  
  246.    return 0;
  247. }
  248.  

Diff to submission s761

hop.cc

--- 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;
 }