Source code for submission s1008

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 == e && akt2 == f)) {
  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. for (i = 0; i < heapSize; i++)
  244. heap[i].value = 999999999;
  245. }
  246.  
  247.  
  248. return 0;
  249. }
  250.  

Diff to submission s998

sablona.cc

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