API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 12th, 2018
77
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 14.22 KB | None | 0 0
raw download clone embed print report
  1. // zadanie3.c -- Denis Piovarči, 20.11.2018 12:33
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6.  
  7. #define BIGNMB 300000
  8.  
  9. int drak_pos = 0;
  10. int drak_z = 0;
  11. int princess_count = 0;
  12. int princess_pos[5] = { -1, -1, -1, -1, -1 };
  13. int generator = 0;
  14. int generator_pos = 0;
  15. //int teleport_count = 0;
  16. //int teleport = 0;
  17. int c;
  18.  
  19. //struktura zaznam suseda
  20. struct zaznam_suseda {
  21. int destinacia;
  22. int cas;
  23. int pozicia;
  24. struct zaznam_suseda *dalsi_sused;
  25. };
  26.  
  27. //struktura obsahujuca smernik na hlavicku zaznamu suseda
  28. struct susedia {
  29. struct zaznam_suseda *hlavicka;
  30. };
  31.  
  32. //struktura reprezentujuca graf
  33. struct graf {
  34.  
  35. int pocet_vrcholov;
  36. struct susedia *pole_susedov;
  37. };
  38.  
  39. //struktura pre zaznam haldy
  40. struct zaznam_haldy {
  41. int vrchol;
  42. int vzdialenost;
  43. };
  44.  
  45. //struktura pre haldu
  46. struct halda {
  47. int aktualna_velkost;
  48. int max_kapacita;
  49. int *pozicia;
  50. struct zaznam_haldy **pole;
  51. };
  52.  
  53. //struktura pre teleporty
  54. struct teleporty {
  55. int vrchol;
  56. int cislo_teleportu;
  57. };
  58.  
  59. //pole zaznamov pre teleporty
  60. struct teleporty *pole_t;
  61.  
  62. //funckia, ktora vytvara graf
  63. struct graf *vytvor_graf(int vrcholy) {
  64.  
  65. struct graf *graf = (struct graf*)malloc(sizeof(struct graf));
  66. graf->pocet_vrcholov = vrcholy;
  67.  
  68. graf->pole_susedov = (struct susedia*)malloc(vrcholy * sizeof(struct susedia));
  69.  
  70. for (int i = 0; i < vrcholy; i++)
  71. graf->pole_susedov[i].hlavicka = NULL;
  72.  
  73. return graf;
  74. }
  75.  
  76. //funkcia, ktora vytvara novy zaznam suseda
  77. struct zaznam_suseda *novy_zaznam_suseda(int destinacia, int cas, int pozicia) {
  78.  
  79. struct zaznam_suseda* novy_zaznam_suseda = (struct zaznam_suseda*)malloc(sizeof(struct zaznam_suseda));
  80. novy_zaznam_suseda->destinacia = destinacia;
  81. novy_zaznam_suseda->cas = cas;
  82. novy_zaznam_suseda->pozicia = pozicia;
  83. novy_zaznam_suseda->dalsi_sused = NULL;
  84.  
  85. return novy_zaznam_suseda;
  86. }
  87.  
  88. //kazdy vrchol grafu ma svojich susedov, cez ktorych moze ist
  89. //tato funkcia prida ku kazdemu vrcholu susedov do pola susedov
  90. void pridaj_hranu(struct graf *graf, int pozicia, int destinacia, int cas) {
  91.  
  92. struct zaznam_suseda *novy_zaznam = novy_zaznam_suseda(destinacia, cas, pozicia);
  93. novy_zaznam->dalsi_sused = graf->pole_susedov[pozicia].hlavicka;
  94. graf->pole_susedov[pozicia].hlavicka = novy_zaznam;
  95. }
  96.  
  97. //funckia sluzi na vytvaranie noveho zaznamu do haldy
  98. struct zaznam_haldy *novy_zaznam_haldy(int vrchol, int vzdialenost) {
  99.  
  100. struct zaznam_haldy *novy_zaznam = (struct zaznam_haldy*)malloc(sizeof(struct zaznam_haldy));
  101. novy_zaznam->vrchol = vrchol;
  102. novy_zaznam->vzdialenost = vzdialenost;
  103. return novy_zaznam;
  104. }
  105.  
  106. //sluzi na vytvorenie MIN haldy
  107. struct halda *vytvor_haldu(int kapacita) {
  108.  
  109. struct halda *MIN_halda = NULL;
  110. MIN_halda = (struct halda*)malloc(sizeof(struct halda));
  111. MIN_halda->pozicia = (int*)malloc(kapacita * sizeof(int));
  112. MIN_halda->aktualna_velkost = 0;
  113. MIN_halda->max_kapacita = kapacita;
  114. MIN_halda->pole = (struct zaznam_haldy**)malloc(kapacita * sizeof(struct zaznam_haldy*));
  115. return MIN_halda;
  116. }
  117.  
  118. //funckia sluzi na upravu haldy tj, ak je treba nieco vymenit a pod. aby boli dodrzane vsetky pravidla
  119. void oprav_haldu(struct halda *MIN_halda, int id) {
  120.  
  121. int minimum, lavy, pravy;
  122. struct zaznam_haldy *min_zaznam, *id_zaznam, *pom;
  123. minimum = id;
  124. lavy = 2 * id + 1;
  125. pravy = 2 * id + 2;
  126.  
  127. if (lavy < MIN_halda->aktualna_velkost && MIN_halda->pole[lavy]->vzdialenost < MIN_halda->pole[minimum]->vzdialenost)
  128. minimum = lavy;
  129.  
  130. if (pravy < MIN_halda->aktualna_velkost && MIN_halda->pole[pravy]->vzdialenost < MIN_halda->pole[minimum]->vzdialenost)
  131. minimum = pravy;
  132.  
  133. if (minimum != id) {
  134.  
  135. min_zaznam = MIN_halda->pole[minimum];
  136. id_zaznam = MIN_halda->pole[id];
  137.  
  138. MIN_halda->pozicia[min_zaznam->vrchol] = id;
  139. MIN_halda->pozicia[id_zaznam->vrchol] = minimum;
  140.  
  141. pom = MIN_halda->pole[minimum];
  142. MIN_halda->pole[minimum] = MIN_halda->pole[id];
  143. MIN_halda->pole[id] = pom;
  144. oprav_haldu(MIN_halda, minimum);
  145. }
  146. }
  147.  
  148. //vracia haldu, ked je uplne prazdna
  149. int je_prazdna(struct halda *MIN_halda) {
  150.  
  151. return MIN_halda->aktualna_velkost == 0;
  152. }
  153.  
  154. //funkcia sluziaca na odstranenie minimalneho prvku z haldy
  155. struct zaznam_haldy *odstran_min(struct halda *MIN_halda) {
  156.  
  157. struct zaznam_haldy *koren, *posledny_zaznam;
  158.  
  159. if (je_prazdna(MIN_halda))
  160. return NULL;
  161.  
  162. koren = MIN_halda->pole[0];
  163. posledny_zaznam = MIN_halda->pole[MIN_halda->aktualna_velkost - 1];
  164. MIN_halda->pole[0] = posledny_zaznam;
  165.  
  166. MIN_halda->pozicia[koren->vrchol] = MIN_halda->aktualna_velkost - 1;
  167. MIN_halda->pozicia[posledny_zaznam->vrchol] = 0;
  168.  
  169. --MIN_halda->aktualna_velkost;
  170. oprav_haldu(MIN_halda, 0);
  171.  
  172. return koren;
  173. }
  174.  
  175. //decrease key
  176. void zniz(struct halda *MIN_halda, int vrchol, int vzdialenost) {
  177.  
  178. struct zaznam_haldy *pom;
  179. int i = MIN_halda->pozicia[vrchol];
  180. MIN_halda->pole[i]->vzdialenost = vzdialenost;
  181.  
  182. while (i && MIN_halda->pole[i]->vzdialenost < MIN_halda->pole[(i - 1) / 2]->vzdialenost) {
  183.  
  184. MIN_halda->pozicia[MIN_halda->pole[i]->vrchol] = (i - 1) / 2;
  185. MIN_halda->pozicia[MIN_halda->pole[(i - 1) / 2]->vrchol] = i;
  186.  
  187. pom = MIN_halda->pole[i];
  188. MIN_halda->pole[i] = MIN_halda->pole[(i - 1) / 2];
  189. MIN_halda->pole[(i - 1) / 2] = pom;
  190.  
  191. i = (i - 1) / 2;
  192. }
  193. }
  194.  
  195. //funckia zistujuca ci sa dany vrchol uz nachadza v halde
  196. int je_v_halde(struct halda *MIN_heap, int vrchol) {
  197.  
  198. if (MIN_heap->pozicia[vrchol] < MIN_heap->aktualna_velkost)
  199. return 1;
  200. return 0;
  201. }
  202.  
  203. //dijkstra hlada najkratsiu a najefektivnejsiu cestu z jedneho vrchola do druheho
  204. int *dijkstra(struct graf *graf, int vychadzajuci_bod, int *cesta, int m) {
  205.  
  206. int pocet_vrcholov = graf->pocet_vrcholov;
  207. int v, u, *parent;
  208. int *vzdialenost;
  209.  
  210. struct zaznam_haldy *zaznam_v_halde;
  211. struct zaznam_suseda *pNode;
  212.  
  213. vzdialenost = (int*)malloc(pocet_vrcholov * sizeof(int));
  214. parent = (int*)malloc(pocet_vrcholov * sizeof(int));
  215.  
  216. struct halda *MIN_halda = vytvor_haldu(pocet_vrcholov);
  217.  
  218. for (v = 0; v < pocet_vrcholov; ++v) {
  219.  
  220. parent[0] = -1;
  221. vzdialenost[v] = BIGNMB;
  222. MIN_halda->pole[v] = novy_zaznam_haldy(v, vzdialenost[v]);
  223. MIN_halda->pozicia[v] = v;
  224. }
  225.  
  226. MIN_halda->pole[vychadzajuci_bod] = novy_zaznam_haldy(vychadzajuci_bod, vzdialenost[vychadzajuci_bod]);
  227. MIN_halda->pozicia[vychadzajuci_bod] = vychadzajuci_bod;
  228. vzdialenost[vychadzajuci_bod] = 0;
  229. zniz(MIN_halda, vychadzajuci_bod, vzdialenost[vychadzajuci_bod]);
  230.  
  231. MIN_halda->aktualna_velkost = pocet_vrcholov;
  232.  
  233. while (!je_prazdna(MIN_halda)) {
  234.  
  235. zaznam_v_halde = odstran_min(MIN_halda);
  236. u = zaznam_v_halde->vrchol;
  237.  
  238. pNode = graf->pole_susedov[u].hlavicka;
  239. while (pNode != NULL) {
  240.  
  241. v = pNode->destinacia;
  242. if (je_v_halde(MIN_halda, v) && vzdialenost[u] != BIGNMB && pNode->cas + vzdialenost[u] < vzdialenost[v]) {
  243.  
  244. vzdialenost[v] = vzdialenost[u] + pNode->cas;
  245. parent[v] = u;
  246. zniz(MIN_halda, v, vzdialenost[v]);
  247. }
  248. if (pNode->pozicia == drak_pos && drak_z == 0) {
  249. drak_z = 1;
  250. return parent;
  251. }
  252.  
  253. if (pNode->pozicia == generator_pos)
  254. generator = 1;
  255.  
  256. /*
  257. int s;
  258. for (int i = 0; i < c; i++) {
  259. if (pNode->pozicia == pole_t[i].vrchol) {
  260. for (int j = 0; j < c; j++) {
  261. if (pole_t[i].cislo_teleportu == pole_t[j].cislo_teleportu) {
  262. s = pole_t->vrchol;
  263. pNode->pozicia = s;
  264. return parent;
  265. }
  266. }
  267. }
  268. }
  269. */
  270.  
  271. /*
  272. if ((pNode->pos == teleport_pos[0] || pNode->pos == teleport_pos[1] || pNode->pos == teleport_pos[2]) && drak_z == 1 && generator == 1 && teleport == 0)
  273. {
  274. teleport = 1;
  275. teleport_pos[0] = -1;
  276. *cesta = princess_pos[0];
  277. return parent;
  278. }
  279. */
  280.  
  281. if (pNode->pozicia == princess_pos[0] && drak_z == 1)
  282. {
  283. *cesta = princess_pos[0];
  284. princess_pos[0] = -1;
  285. return parent;
  286. }
  287.  
  288. if (pNode->pozicia == princess_pos[1] && drak_z == 1)
  289. {
  290. *cesta = princess_pos[1];
  291. princess_pos[1] = -1;
  292. return parent;
  293. }
  294.  
  295. if (pNode->pozicia == princess_pos[2] && drak_z == 1)
  296. {
  297. *cesta = princess_pos[2];
  298. princess_pos[2] = -1;
  299. return parent;
  300. }
  301.  
  302. if (pNode->pozicia == princess_pos[3] && drak_z == 1)
  303. {
  304. *cesta = princess_pos[3];
  305. princess_pos[3] = -1;
  306. return parent;
  307. }
  308.  
  309. if (pNode->pozicia == princess_pos[4] && drak_z == 1)
  310. {
  311. *cesta = princess_pos[4];
  312. princess_pos[4] = -1;
  313. return parent;
  314. }
  315.  
  316. pNode = pNode->dalsi_sused;
  317. }
  318. }
  319. return 0;
  320. }
  321. int time(char **mapa, int x, int y) {
  322. switch (mapa[x][y]) {
  323. case 'C':
  324. return 1;
  325. case 'H':
  326. return 2;
  327.  
  328. case 'N':
  329. return -1;
  330.  
  331. case 'D':
  332. return 1;
  333.  
  334. case 'P':
  335. return 1;
  336.  
  337. case 'G':
  338. return 1;
  339.  
  340. }
  341. if (mapa[x][y] >= '0' && mapa[x][y] <= '9')
  342. return 1;
  343.  
  344. return 0;
  345. }
  346.  
  347. int getWeight(char letter)
  348. {
  349. switch (letter)
  350. {
  351. case 'C':
  352. return 1;
  353. case 'H':
  354. return 2;
  355. case 'P':
  356. return 1;
  357. case 'N':
  358. return -1;
  359. case 'D':
  360. return 1;
  361. case 'G':
  362. return 1;
  363. }
  364.  
  365. if (letter >= '0' && letter <= '9')
  366. return 1;
  367.  
  368. return 0;
  369. }
  370.  
  371. int *zachran_princezne(char **mapa, int n, int m, int t, int *dlzka_cesty)
  372. {
  373. int i, j, poc = 0, *dist, *path, cesta, l, k, *tmp, totalCount = 0, o, pred;
  374. int V = n * m;
  375. struct graf* graf = vytvor_graf(V);
  376. pole_t = (struct teleporty*)malloc(sizeof(struct teleporty));
  377. pole_t[0].cislo_teleportu = -1;
  378. pole_t[0].vrchol = -1;
  379.  
  380. path = (int*)malloc(sizeof(int)*n*m);
  381. tmp = (int*)malloc(sizeof(int)*n*m);
  382.  
  383. for (i = 0; i < n; i++)
  384. {
  385. for (j = 0; j < m; j++)
  386. {
  387.  
  388. if (mapa[i][j] == 'D')
  389. drak_pos = poc;
  390.  
  391. if (mapa[i][j] == 'P')
  392. {
  393. princess_pos[princess_count] = poc;
  394. princess_count++;
  395. }
  396.  
  397. if (mapa[i][j] == 'G')
  398. generator_pos = poc;
  399.  
  400.  
  401. if (mapa[i][j] >= '0' && mapa[i][j] <= '9')
  402. {
  403.  
  404. for (c = 0; pole_t->vrchol != -1 && pole_t->cislo_teleportu != -1; c++);
  405. pole_t = (struct teleporty *)realloc(pole_t, c + 1);
  406. pole_t[c].vrchol = poc;
  407. pole_t[c].cislo_teleportu = mapa[i][j];
  408. }
  409.  
  410. if (j == 0 && i == 0)
  411. {
  412. pridaj_hranu(graf, poc, poc + 1, getWeight(mapa[i][j]));
  413. pridaj_hranu(graf, poc, poc + m, getWeight(mapa[i][j]));
  414. poc++;
  415. }
  416. else if (j != 0 && i == 0 && j != m - 1)
  417. {
  418. pridaj_hranu(graf, poc, poc + 1, getWeight(mapa[i][j]));
  419. pridaj_hranu(graf, poc, poc - 1, getWeight(mapa[i][j]));
  420. pridaj_hranu(graf, poc, poc + m, getWeight(mapa[i][j]));
  421. poc++;
  422. }
  423. else if (j == m - 1 && i == 0)
  424. {
  425. pridaj_hranu(graf, poc, poc - 1, getWeight(mapa[i][j]));
  426. pridaj_hranu(graf, poc, poc + m, getWeight(mapa[i][j]));
  427. poc++;
  428. }
  429. else if (j == 0 && i == n - 1)
  430. {
  431. pridaj_hranu(graf, poc, poc + 1, getWeight(mapa[i][j]));
  432. pridaj_hranu(graf, poc, poc - m, getWeight(mapa[i][j]));
  433. poc++;
  434. }
  435. else if (j != 0 && i == n - 1 && j != m - 1)
  436. {
  437. pridaj_hranu(graf, poc, poc + 1, getWeight(mapa[i][j]));
  438. pridaj_hranu(graf, poc, poc - 1, getWeight(mapa[i][j]));
  439. pridaj_hranu(graf, poc, poc - m, getWeight(mapa[i][j]));
  440. poc++;
  441. }
  442. else if (j == m - 1 && i == n - 1)
  443. {
  444. pridaj_hranu(graf, poc, poc - 1, getWeight(mapa[i][j]));
  445. pridaj_hranu(graf, poc, poc - m, getWeight(mapa[i][j]));
  446. poc++;
  447. }
  448. else if (j == 0 && i != 0 && i != n - 1)
  449. {
  450. pridaj_hranu(graf, poc, poc + 1, getWeight(mapa[i][j]));
  451. pridaj_hranu(graf, poc, poc - m, getWeight(mapa[i][j]));
  452. pridaj_hranu(graf, poc, poc + m, getWeight(mapa[i][j]));
  453. poc++;
  454. }
  455. else if (j == m - 1 && i != 0 && i != n - 1)
  456. {
  457. pridaj_hranu(graf, poc, poc - m, getWeight(mapa[i][j]));
  458. pridaj_hranu(graf, poc, poc - 1, getWeight(mapa[i][j]));
  459. pridaj_hranu(graf, poc, poc - m, getWeight(mapa[i][j]));
  460. poc++;
  461. }
  462. else if (j != 0 && i != 0 && i != n - 1 && j != m - 1)
  463. {
  464. pridaj_hranu(graf, poc, poc - m, getWeight(mapa[i][j]));
  465. pridaj_hranu(graf, poc, poc - 1, getWeight(mapa[i][j]));
  466. pridaj_hranu(graf, poc, poc + m, getWeight(mapa[i][j]));
  467. pridaj_hranu(graf, poc, poc + 1, getWeight(mapa[i][j]));
  468. poc++;
  469. }
  470. }
  471. }
  472.  
  473. dist = dijkstra(graf, 0, &cesta, m);
  474. path[0] = 0;
  475. path[1] = 0;
  476. k = drak_pos;
  477. i = 1;
  478. while (1)
  479. {
  480. tmp[i] = k;
  481. i++;
  482. k = dist[k];
  483. totalCount++;
  484. if (k == 0)
  485. break;
  486. }
  487.  
  488. l = totalCount;
  489. for (i = 1; i <= totalCount; i++) {
  490. path[i * 2] = tmp[l] % m;
  491. path[i * 2 + 1] = tmp[l] / m;
  492. l--;
  493. }
  494.  
  495. for (j = 0; j < princess_count; j++)
  496. {
  497. if (j == 0)
  498. {
  499. dist = dijkstra(graf, drak_pos, &cesta, m);
  500. k = cesta;
  501. pred = drak_pos;
  502. }
  503. else
  504. {
  505. dist = dijkstra(graf, pred, &cesta, m);
  506. k = cesta;
  507. }
  508. if (cesta != -1) {
  509. i = 0;
  510. while (1)
  511. {
  512. tmp[i] = k;
  513. i++;
  514. k = dist[k];
  515. totalCount++;
  516. if (j == 0) {
  517. if (k == drak_pos)
  518. break;
  519. }
  520. else
  521. {
  522. if (k == pred)
  523. break;
  524. }
  525. }
  526.  
  527. l = i - 1;
  528. for (o = totalCount - i + 1; o <= totalCount; o++) {
  529. path[o * 2] = tmp[l] % m;
  530. path[o * 2 + 1] = tmp[l] / m;
  531. l--;
  532. }
  533. pred = cesta;
  534. }
  535. else
  536. {
  537. k = 8;
  538. i = 0;
  539. while (1)
  540. {
  541. tmp[i] = k;
  542. i++;
  543. k = dist[k];
  544. totalCount++;
  545. if (j == 0) {
  546. if (k == drak_pos)
  547. break;
  548. }
  549. else
  550. {
  551. if (k == pred)
  552. break;
  553. }
  554. }
  555.  
  556. l = i - 1;
  557. for (o = totalCount - i + 1; o <= totalCount; o++) {
  558. path[o * 2] = tmp[l] % m;
  559. path[o * 2 + 1] = tmp[l] / m;
  560. l--;
  561. }
  562. }
  563. }
  564.  
  565. /*
  566. if (teleport == 1) {
  567. dist = dijkstra(graph, 35, &cesta, m);
  568. k = cesta;
  569. i = 0;
  570. while (1)
  571. {
  572. tmp[i] = k;
  573. i++;
  574. k = dist[k];
  575. totalCount++;
  576. if (k == 35)
  577. break;
  578. }
  579. tmp[i] = 35;
  580. i++;
  581. totalCount++;
  582. l = i - 1;
  583. for (i = totalCount - i + 1; i <= totalCount; i++) {
  584. path[i * 2] = tmp[l] % m;
  585. path[i * 2 + 1] = tmp[l] / m;
  586. l--;
  587. }
  588.  
  589. }
  590. */
  591. *dlzka_cesty = totalCount + 1;
  592.  
  593. return path;
  594. }
  595.  
  596.  
  597. int main() {
  598.  
  599. int dlzka_cesty = 0;
  600. int n = 5, m = 5, t = 0;
  601.  
  602. char **mapa = (char**)malloc(n * sizeof(char*));
  603. for (int i = 0; i < m; i++) {
  604. mapa[i] = (char*)malloc(m * sizeof(char));
  605. }
  606.  
  607. mapa[0] = "CHHDC";
  608. mapa[1] = "HCCHH";
  609. mapa[2] = "CHPPC";
  610. mapa[3] = "PHHHC";
  611. mapa[4] = "CHHHC";
  612.  
  613.  
  614. for (int i = 0; i < n; i++) {
  615. for (int j = 0; j < m; j++) {
  616. printf("%c", mapa[i][j]);
  617. }
  618. printf("\n");
  619. }
  620.  
  621. zachran_princezne(mapa, n, m, t, &dlzka_cesty);
  622.  
  623. getchar();
  624. return 0;
  625. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!