API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 7th, 2017
61
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 31.21 KB | None | 0 0
raw download clone embed print report
  1.  
  2. #include<stdio.h>
  3. #include<math.h>
  4. #include<stdlib.h>
  5.  
  6. #define POCET_PRINCEZIEN  3
  7. #define POCET_TELEPORTOV  10
  8. #define DLZKA_CESTY       200
  9.  typedef struct pozicia{
  10.   int x;
  11.   int y;
  12.  }POZICIA;
  13.  
  14.  typedef struct postupnost{
  15.   POZICIA **pozicie;
  16.     int cena;
  17.     int limit;
  18.     int pocet;
  19.  }POSTUPNOST;
  20.  
  21.  typedef struct krok{
  22.   POZICIA *p; //aktualna pozicia
  23.   POZICIA *z; //predchadzajuci krok
  24.   int index;
  25.   int cena;
  26.   int hotovo;
  27.  }KROK;
  28.  
  29.  typedef struct okraj{
  30.   KROK **kroky;
  31.   int pocet;
  32.   int limit;
  33.  }OKRAJ;
  34.  
  35.  
  36. int najdivPost(POSTUPNOST *postupnost, POZICIA *poz) {
  37.     int i;
  38.     if(poz == NULL) return -1;
  39.     for( i = 0; i < postupnost->pocet; i++) {
  40.         if((poz->x == postupnost->pozicie[i]->x) && (poz->y == postupnost->pozicie[i]->y)) return i;
  41.     }
  42.     return -1;
  43. }
  44.  
  45. void swapKROKy(OKRAJ *okraj, int pos1, int pos2) {
  46.     KROK *k = okraj->kroky[pos1];
  47.     okraj->kroky[pos1] = okraj->kroky[pos2];
  48.     okraj->kroky[pos2] = k;
  49.     okraj->kroky[pos1]->index = pos1;
  50.     okraj->kroky[pos2]->index = pos2;
  51. }
  52.  
  53.  
  54. void addPOSTUPNOST(POSTUPNOST *postupnost, POSTUPNOST *postupnost2) {
  55.     int i;
  56.     if(postupnost2 == NULL) return;
  57.     if(postupnost2->pocet == 0) return;
  58.     if(postupnost->pocet == 0) {
  59.         for( i = 0; i < postupnost2->pocet; i++) {
  60.             int a;
  61.             if(postupnost->pocet == postupnost->limit) {
  62.                 POZICIA **pozicie = calloc((postupnost->limit+DLZKA_CESTY),sizeof(POZICIA*));
  63.                     for( a = 0; a < postupnost->pocet; a++) {
  64.                         pozicie[a] = postupnost->pozicie[a];
  65.                     }
  66.                     free(postupnost->pozicie);
  67.                     postupnost->pozicie = pozicie;
  68.                     postupnost->limit = postupnost->limit + DLZKA_CESTY;
  69.             }
  70.             postupnost->pozicie[postupnost->pocet] = postupnost2->pozicie[i];
  71.             postupnost->pocet++;
  72.  
  73.         }
  74.         postupnost->cena = postupnost2->cena;
  75.     } else if((postupnost->pozicie[postupnost->pocet - 1]->x== postupnost2->pozicie[0]->x) && (postupnost->pozicie[postupnost->pocet - 1]->y== postupnost2->pozicie[0]->y)) {
  76.         for( i = 1; i < postupnost2->pocet; i++) {
  77.             int a;
  78.             if(postupnost->pocet == postupnost->limit) {
  79.                 POZICIA **pozicie = calloc((postupnost->limit+DLZKA_CESTY),sizeof(POZICIA*));
  80.                 for( a = 0; a < postupnost->pocet; a++) {
  81.                     pozicie[a] = postupnost->pozicie[a];
  82.                 }
  83.                 free(postupnost->pozicie);
  84.                 postupnost->pozicie = pozicie;
  85.                 postupnost->limit = postupnost->limit + DLZKA_CESTY;
  86.             }
  87.             postupnost->pozicie[postupnost->pocet] = postupnost2->pozicie[i];
  88.             postupnost->pocet++;
  89.  
  90.         }
  91.         postupnost->cena = postupnost->cena + postupnost2->cena;
  92.     } else {
  93.         for( i = postupnost2->pocet - 2; i >= 0; i--) {
  94.             int a;
  95.             if(postupnost->pocet == postupnost->limit) {
  96.                 POZICIA **pozicie = calloc((postupnost->limit+DLZKA_CESTY),sizeof(POZICIA*));
  97.                 for( a = 0; a < postupnost->pocet; a++) {
  98.                     pozicie[a] = postupnost->pozicie[a];
  99.                 }
  100.                 free(postupnost->pozicie);
  101.                 postupnost->pozicie = pozicie;
  102.                 postupnost->limit = postupnost->limit + DLZKA_CESTY;
  103.             }
  104.             postupnost->pozicie[postupnost->pocet] = postupnost2->pozicie[i];
  105.             postupnost->pocet++;
  106.         }
  107.         postupnost->cena = postupnost->cena + postupnost2->cena;
  108.     }
  109. }
  110.  
  111.  
  112. void reHeapUp(OKRAJ *okraj, int index, int findMin) {
  113.     while(index > 0) {
  114.         int parentIndex = (index + 1) / 2 - 1;
  115.         KROK *current = okraj->kroky[index];
  116.         KROK *parent = okraj->kroky[parentIndex];
  117.         if(findMin == 1) {
  118.             if(parent->cena > current->cena) {
  119.                 swapKROKy(okraj, index, parentIndex);
  120.                 index = parentIndex;
  121.             } else {
  122.                 return;
  123.             }
  124.         } else {
  125.             if(parent->cena < current->cena) {
  126.                 swapKROKy(okraj, index, parentIndex);
  127.                 index = parentIndex;
  128.             } else {
  129.                 return;
  130.             }
  131.         }
  132.     }
  133. }
  134.  
  135. void reHeapDown(OKRAJ *okraj, int index, int maxIndex, int findMin) {
  136.     while(index <= maxIndex) {
  137.         int child1Index = (index+1) * 2 - 1 ;
  138.         int child2Index = child1Index + 1;
  139.         KROK *current = okraj->kroky[index];
  140.         KROK *child1 = NULL;
  141.         KROK *child2 = NULL;
  142.         if(child1Index <= maxIndex) child1 = okraj->kroky[child1Index];
  143.         if(child2Index <= maxIndex) child2 = okraj->kroky[child2Index];
  144.  
  145.         if(findMin == 1) {
  146.             if(child1 != NULL) {
  147.                 if(child2 != NULL) {
  148.                     if(child1->cena > child2->cena) {
  149.                         if(child2->cena < current->cena) {
  150.                             swapKROKy(okraj, index, child2Index);
  151.                             index = child2Index;
  152.                         } else {
  153.                             return;
  154.                         }
  155.                     } else {
  156.                         if(child1->cena < current->cena) {
  157.                             swapKROKy(okraj, index, child1Index);
  158.                             index = child1Index;
  159.                         } else {
  160.                             return;
  161.                         }
  162.                     }
  163.                 } else {
  164.                     if(child1->cena < current->cena) {
  165.                         swapKROKy(okraj, index, child1Index);
  166.                         index = child1Index;
  167.                     } else {
  168.                         return;
  169.                     }
  170.  
  171.                 }
  172.             } else {
  173.                 return;
  174.             }
  175.         } else {
  176.             if(child1 != NULL) {
  177.                 if(child2 != NULL) {
  178.                     if(child1->cena < child2->cena) {
  179.                         if(child2->cena > current->cena) {
  180.                             swapKROKy(okraj, index, child2Index);
  181.                             index = child2Index;
  182.                         } else {
  183.                             return;
  184.                         }
  185.                     } else {
  186.                         if(child1->cena > current->cena) {
  187.                             swapKROKy(okraj, index, child1Index);
  188.                             index = child1Index;
  189.                         } else {
  190.                             return;
  191.                         }
  192.                     }
  193.                 } else {
  194.                     if(child1->cena > current->cena) {
  195.                         swapKROKy(okraj, index, child1Index);
  196.                         index = child1Index;
  197.                     } else {
  198.                         return;
  199.                     }
  200.  
  201.                 }
  202.             } else {
  203.                 return;
  204.             }
  205.         }
  206.     }
  207. }
  208.  
  209. void inicializujPozicie(char **mapa, int n, int m, POZICIA *start, POZICIA *d, POZICIA *vypinac, POSTUPNOST *p, POSTUPNOST **teleporty) {
  210.     int i,j;
  211.  
  212.  
  213.  
  214.     for( i = 0; i < n; i++) {
  215.  
  216.         for( j = 0; j < m; j++) {
  217.  
  218.             char c = mapa[i][j];
  219.             //printf("%c",c);
  220.             if(c == 'D') {
  221.                 d->x = i;
  222.                 d->y = j;
  223.             } else if(c == 'G') {
  224.                 vypinac->x = i;
  225.                 vypinac->y = j;
  226.             } else if(c == 'P') {
  227.                 POZICIA *tmpPoz =malloc(sizeof(POZICIA));
  228.                 tmpPoz->x = i;
  229.                 tmpPoz->y = j;
  230.                 int a;
  231.                 if(p->pocet == p->limit) {
  232.                     POZICIA **pozicie = calloc((p->limit+DLZKA_CESTY),sizeof(POZICIA*));
  233.                     for( a = 0; a < p->pocet; a++) {
  234.                         pozicie[a] = p->pozicie[a];
  235.                     }
  236.                     free(p->pozicie);
  237.                     p->pozicie = pozicie;
  238.                     p->limit = p->limit + DLZKA_CESTY;
  239.                 }
  240.                 p->pozicie[p->pocet] = tmpPoz;
  241.                 p->pocet++;
  242.  
  243.             } else if(('0' <= c) && (c <= '9')) {
  244.                 POZICIA *tmpPoz =malloc(sizeof(POZICIA));
  245.                 tmpPoz->x = i;
  246.                 tmpPoz->y = j;
  247.                 int a;
  248.                 if(teleporty[c - '0']->pocet == teleporty[c - '0']->limit) {
  249.                     POZICIA **pozicie = calloc((teleporty[c - '0']->limit+DLZKA_CESTY),sizeof(POZICIA*));
  250.                     for( a = 0; a < teleporty[c - '0']->pocet; a++) {
  251.                         pozicie[a] = teleporty[c - '0']->pozicie[a];
  252.                     }
  253.                     free(teleporty[c - '0']->pozicie);
  254.                     teleporty[c - '0']->pozicie = pozicie;
  255.                     teleporty[c - '0']->limit = teleporty[c - '0']->limit + DLZKA_CESTY;
  256.                 }
  257.                 teleporty[c - '0']->pozicie[teleporty[c - '0']->pocet] = tmpPoz;
  258.                 teleporty[c - '0']->pocet++;
  259.  
  260.             }
  261.         }
  262.     }
  263. }
  264.  
  265.  
  266.  
  267.  
  268.   void hladajMozneKROKy(char **mapa, int n, int m
  269.                                     , KROK ***kroky, POSTUPNOST **teleporty
  270.                                     , POZICIA *pozFrom, POSTUPNOST *moznePozicie
  271.                                     , int fungujuTeleporty
  272.                                     ) {
  273.         moznePozicie->pocet = 0;
  274.         int k,i,j;
  275.         char cFrom = mapa[pozFrom->x][pozFrom->y];
  276.         if((fungujuTeleporty == 1) && ('0' <= cFrom) && (cFrom <= '9')) {
  277.             POSTUPNOST *teleport = teleporty[cFrom - '0'];
  278.             for( k = 0; k < teleport->pocet; k++) {
  279.                 int pos = najdivPost(moznePozicie, teleport->pozicie[k]);
  280.                 if(pos < 0) {
  281.                     int a;
  282.                     if(moznePozicie->pocet == moznePozicie->limit) {
  283.                         POZICIA **pozicie = calloc((moznePozicie->limit+DLZKA_CESTY),sizeof(POZICIA*));
  284.                         for( a = 0; a < moznePozicie->pocet; a++) {
  285.                             pozicie[a] = moznePozicie->pozicie[a];
  286.                         }
  287.                         free(moznePozicie->pozicie);
  288.                         moznePozicie->pozicie = pozicie;
  289.                         moznePozicie->limit = moznePozicie->limit + DLZKA_CESTY;
  290.                     }
  291.                     moznePozicie->pozicie[moznePozicie->pocet] = teleport->pozicie[k];
  292.                     moznePozicie->pocet++;
  293.  
  294.                 }
  295.             }
  296.  
  297.         }
  298.         for( i = -1; i < 2; i++) {
  299.             for( j = -1; j < 2; j++) {
  300.                 if((i != 0) && (j != 0)) continue;
  301.                 if((i == 0) && (j == 0)) continue;
  302.                 int x = pozFrom->x + i;
  303.                 int y = pozFrom->y + j;
  304.                 if((x < 0) || (y < 0)) continue;
  305.                 if((x >= n) || (y >= m)) continue;
  306.                 char c = mapa[x][y];
  307.                 if(c == 'N') continue;
  308.                 int pos = najdivPost(moznePozicie, kroky[x][y]->p);
  309.                 if(pos < 0) {
  310.  
  311.  
  312.                 }
  313.                     int a;
  314.                     if(moznePozicie->pocet == moznePozicie->limit) {
  315.                         POZICIA **pozicie = calloc((moznePozicie->limit+DLZKA_CESTY),sizeof(POZICIA*));
  316.                         for( a = 0; a < moznePozicie->pocet; a++) {
  317.                             pozicie[a] = moznePozicie->pozicie[a];
  318.                         }
  319.                         free(moznePozicie->pozicie);
  320.                         moznePozicie->pozicie = pozicie;
  321.                         moznePozicie->limit = moznePozicie->limit + DLZKA_CESTY;
  322.                     }
  323.                     moznePozicie->pozicie[moznePozicie->pocet] = kroky[x][y]->p;
  324.                     moznePozicie->pocet++;
  325.             }
  326.         }
  327.     }
  328.  
  329. void hladajCestu(char **mapa, int n, int m
  330.                  , KROK ***kroky, POSTUPNOST **teleporty, OKRAJ *okraj
  331.                  , POZICIA *pozFrom, POSTUPNOST *pozTo
  332.                  , int fungujuTeleporty
  333.                 ) {
  334.     int i,j;
  335.     for(i  = 0; i < n; i++) {
  336.         for(j  = 0; j < m; j++) {
  337.             kroky[i][j]->cena = 0;
  338.             kroky[i][j]->z = NULL;
  339.             kroky[i][j]->index = -1;
  340.             kroky[i][j]->hotovo = 0;
  341.         }
  342.     }
  343.  
  344.     okraj->pocet = 0;
  345.  
  346.     int b;
  347.     if(okraj->pocet == okraj->limit) {
  348.         KROK **kroky = calloc((okraj->limit+DLZKA_CESTY),sizeof(KROK*));
  349.         for(b = 0; b < okraj->pocet; b++) {
  350.             kroky[b] = okraj->kroky[b];
  351.         }
  352.         free(okraj->kroky);
  353.         okraj->kroky = kroky;
  354.         okraj->limit = okraj->limit + DLZKA_CESTY;
  355.     }
  356.     okraj->kroky[okraj->pocet] = kroky[pozFrom->x][pozFrom->y];
  357.     okraj->pocet++;
  358.  
  359.     POSTUPNOST *moznePozicie = malloc(sizeof(POSTUPNOST));
  360.     moznePozicie->pozicie = calloc(POCET_TELEPORTOV,sizeof(POZICIA*));
  361.     moznePozicie->pocet = 0;
  362.     moznePozicie->limit = POCET_TELEPORTOV;
  363.     moznePozicie->cena =0;
  364.  
  365.     while((okraj->pocet > 0) && (pozTo->pocet > 0)) {
  366.  
  367.         KROK *actual = okraj->kroky[0];
  368.  
  369.         actual->hotovo = 1;
  370.         okraj->pocet--;
  371.         if(okraj->pocet > 0) {
  372.             okraj->kroky[0] = okraj->kroky[okraj->pocet];
  373.             okraj->kroky[0]->index = 0;
  374.             reHeapDown(okraj, 0, okraj->pocet - 1, 1);
  375.         }
  376.  
  377.         int pos = najdivPost(pozTo, actual->p);
  378.         if(pos > -1) {
  379.             for( i = pos; i < pozTo->pocet-1; i++) {
  380.                 pozTo->pozicie[i] = pozTo->pozicie[i+1];
  381.             }
  382.             pozTo->pocet--;
  383.         }
  384.  
  385.         hladajMozneKROKy(mapa, n, m, kroky, teleporty, actual->p, moznePozicie, fungujuTeleporty);
  386.         for( i = 0; i < moznePozicie->pocet; i++) {
  387.             POZICIA *nextPos = moznePozicie->pozicie[i];
  388.  
  389.  
  390.             KROK *nextKROK = kroky[nextPos->x][nextPos->y];
  391.             if(nextKROK->hotovo == 1) continue;
  392.                 int cenaKROKu = 1;
  393.                 char c = mapa[nextPos->x][nextPos->y];
  394.                 if(c == 'H') cenaKROKu++;
  395.                 if(('0' <= c) && (c <= '9') && (fungujuTeleporty == 1)) {
  396.                     if(mapa[actual->p->x][actual->p->y] == c) cenaKROKu--;
  397.                 }
  398.             if(nextKROK->index > -1) {
  399.                 if(nextKROK->cena > (actual->cena + cenaKROKu)) {
  400.                     nextKROK->cena = actual->cena + cenaKROKu;
  401.                     nextKROK->z = actual->p;
  402.                     reHeapUp(okraj, nextKROK->index, 1);
  403.                 }
  404.             } else {
  405.                 int b;
  406.     if(okraj->pocet == okraj->limit) {
  407.         KROK **kroky = calloc((okraj->limit+DLZKA_CESTY),sizeof(KROK*));
  408.         for(b = 0; b < okraj->pocet; b++) {
  409.             kroky[i] = okraj->kroky[b];
  410.         }
  411.         free(okraj->kroky);
  412.         okraj->kroky = kroky;
  413.         okraj->limit = okraj->limit + DLZKA_CESTY;
  414.     }
  415.     okraj->kroky[okraj->pocet] = nextKROK;
  416.     okraj->pocet++;
  417.  
  418.                     nextKROK->index = okraj->pocet-1;
  419.                 nextKROK->z = actual->p;
  420.                 nextKROK->cena = actual->cena + cenaKROKu;
  421.                 reHeapUp(okraj, okraj->pocet-1, 1);
  422.             }
  423.         }
  424.     }
  425. }
  426.  
  427. void citajCestuZKROKov(KROK ***kroky, POSTUPNOST *cesta, POZICIA *kam) {
  428.     KROK *krok = kroky[kam->x][kam->y];
  429.     if(krok->z != NULL) citajCestuZKROKov(kroky, cesta, krok->z);
  430.     int a;
  431.     if(cesta->pocet == cesta->limit) {
  432.         POZICIA **pozicie = calloc((cesta->limit+DLZKA_CESTY),sizeof(POZICIA*));
  433.         for( a = 0; a < cesta->pocet; a++) {
  434.             pozicie[a] = cesta->pozicie[a];
  435.         }
  436.         free(cesta->pozicie);
  437.         cesta->pozicie = pozicie;
  438.         cesta->limit = cesta->limit + DLZKA_CESTY;
  439.     }
  440.     cesta->pozicie[cesta->pocet] = krok->p;
  441.     cesta->pocet++;
  442.  
  443.     cesta->cena = krok->cena;
  444. }
  445. int i,j;
  446. POSTUPNOST ***mapaPOSTUPNOSTi(int size) {
  447.     POSTUPNOST ***mapa = malloc(size*sizeof(POSTUPNOST**));
  448.     for( i = 0; i < size; i++) {
  449.         mapa[i] = malloc(size*sizeof(POSTUPNOST*));
  450.         for( j = 0; j < size; j++) {
  451.             mapa[i][j] = NULL;
  452.         }
  453.     }
  454.     return mapa;
  455. }
  456.  
  457. int calculateCena(POSTUPNOST **array, int size) {
  458.     int suma = 0,i;
  459.     for( i = 0; i < size; i++) {
  460.         if(array[i] == NULL) continue;
  461.         suma = suma + array[i]->cena;
  462.     }
  463.     return suma;
  464. }
  465.  
  466. int combine(POSTUPNOST ***noTele, POSTUPNOST ***tele, int size
  467.             , int index, int fromIndex
  468.             , POSTUPNOST *p, POSTUPNOST *najdene
  469.             , POSTUPNOST **current, POSTUPNOST **minimal, int min
  470.             , int useTele, int useNoTele
  471.            ) {
  472.     int i;
  473.     if((index >= size) || (najdene->pocet >= (size-2))) {
  474.         if(najdene->pocet >= (size-2)) {
  475.             int cena = 0,i;
  476.     for( i = 0; i < size; i++) {
  477.         if(current[i] == NULL) continue;
  478.         cena += current[i]->cena;
  479.     }
  480.             if(cena < min) {
  481.                 for( i = 0; i < size; i++) {
  482.                     minimal[i] = current[i];
  483.                 }
  484.                 return cena;
  485.             } else {
  486.                 return min;
  487.             }
  488.         } else {
  489.             return min;
  490.         }
  491.     }
  492.  
  493.     if(useNoTele == 1) {
  494.         for( i = 1; i < size; i++) {
  495.             POSTUPNOST *pos = noTele[fromIndex][i];
  496.             if(pos == NULL) continue;
  497.             if(pos->pocet == 0) continue;
  498.             current[index] = pos;
  499.             if(i > 1) {
  500.                 int princezna = najdivPost(najdene, p->pozicie[i-2]);
  501.                 if(princezna > -1) continue;
  502.                 int a;
  503.                     if(najdene->pocet == najdene->limit) {
  504.                         POZICIA **pozicie = calloc((najdene->limit+DLZKA_CESTY),sizeof(POZICIA*));
  505.                         for( a = 0; a < najdene->pocet; a++) {
  506.                             pozicie[a] = najdene->pozicie[a];
  507.                         }
  508.                         free(najdene->pozicie);
  509.                         najdene->pozicie = pozicie;
  510.                         najdene->limit = najdene->limit + DLZKA_CESTY;
  511.                     }
  512.                     najdene->pozicie[najdene->pocet] = p->pozicie[i-2];
  513.                     najdene->pocet++;
  514.  
  515.             }
  516.             int newUseNoTele = 1;
  517.             if(i == 1) newUseNoTele = 0;
  518.             min = combine(noTele, tele, size
  519.                           , index+1, i
  520.                           , p, najdene
  521.                           , current, minimal, min
  522.                           , useTele, newUseNoTele);
  523.             if(i > 1) najdene->pocet--;
  524.             current[index] = NULL;
  525.         }
  526.     }
  527.  
  528.     if(useTele == 1) {
  529.         for( i = 2; i < size; i++) {
  530.             POSTUPNOST *pos = tele[fromIndex][i];
  531.             if(pos == NULL) continue;
  532.             if(pos->pocet == 0) continue;
  533.             current[index] = pos;
  534.             int princezna = najdivPost(najdene, p->pozicie[i-2]);
  535.             if(princezna > -1) continue;
  536.             int a;
  537.                     if(najdene->pocet == najdene->limit) {
  538.                         POZICIA **pozicie = calloc((najdene->limit+DLZKA_CESTY),sizeof(POZICIA*));
  539.                         for( a = 0; a < najdene->pocet; a++) {
  540.                             pozicie[a] = najdene->pozicie[a];
  541.                         }
  542.                         free(najdene->pozicie);
  543.                         najdene->pozicie = pozicie;
  544.                         najdene->limit = najdene->limit + DLZKA_CESTY;
  545.                     }
  546.                     najdene->pozicie[najdene->pocet] = p->pozicie[i-2];
  547.                     najdene->pocet++;
  548.  
  549.             min = combine(noTele, tele, size
  550.                           , index+1, i
  551.                           , p, najdene
  552.                           , current, minimal, min
  553.                           , useTele, useNoTele);
  554.             current[index] = NULL;
  555.             najdene->pocet--;
  556.         }
  557.     }
  558.  
  559.     return min;
  560. }
  561.  
  562. void printMapa(char **mapa, int n, int m,POSTUPNOST *postupnost) {
  563.     printf(" ---------------------------------------\n");
  564.     POZICIA *poz = malloc(sizeof(POZICIA));
  565.     poz->x=0;
  566.     poz->y=0;
  567.     int i,j,k;
  568.     for( i = 0; i < n; i++) {
  569.         for( j = 0; j < m; j++) {
  570.             char c = mapa[i][j];
  571.             poz->x = i;
  572.             poz->y = j;
  573.  
  574.             printf("%c",c);
  575.         }
  576.         printf("\n");
  577.     }
  578.     printf(" ---------------------------------------");
  579. }
  580.  
  581. int* zachran_princezne(char **mapa, int n, int m, int t, int *dlzka_cesty) {
  582.  
  583.     int i,j;
  584.     printMapa(mapa,n,m,NULL);
  585.     POZICIA *start = malloc(sizeof(POZICIA));
  586.                 start->x = 0;
  587.                 start->y = 0;
  588.     POZICIA *d = malloc(sizeof(POZICIA));
  589.                 d->x = -1;
  590.                 d->y = -1;
  591.     POZICIA *vypinac = malloc(sizeof(POZICIA));
  592.                 vypinac->x = -1;
  593.                 vypinac->y = -1;
  594.     POSTUPNOST *p = malloc(sizeof(POSTUPNOST));
  595.     p->pozicie = calloc(POCET_PRINCEZIEN,sizeof(POZICIA*));
  596.     p->pocet = 0;
  597.     p->limit = POCET_PRINCEZIEN;
  598.     p->cena =0;
  599.  
  600.     POSTUPNOST **teleporty =calloc(POCET_TELEPORTOV,sizeof(POSTUPNOST*));
  601.     for( i = 0; i < POCET_TELEPORTOV; i++) {teleporty[i] = malloc(sizeof(POSTUPNOST));
  602.     teleporty[i]->pozicie = calloc(POCET_TELEPORTOV,sizeof(POZICIA*));
  603.     teleporty[i]->pocet = 0;
  604.     teleporty[i]->limit = POCET_TELEPORTOV;
  605.     teleporty[i]->cena =0;
  606.     }
  607.     POSTUPNOST *vyslednaCesta = malloc(sizeof(POSTUPNOST));
  608.     vyslednaCesta->pozicie = calloc(DLZKA_CESTY,sizeof(POZICIA*));
  609.     vyslednaCesta->pocet = 0;
  610.     vyslednaCesta->limit = DLZKA_CESTY;
  611.     vyslednaCesta->cena =0;
  612.  
  613.     inicializujPozicie(mapa, n, m, start, d, vypinac, p, teleporty);
  614.  
  615.     OKRAJ *okraj = malloc(sizeof(OKRAJ));
  616.     okraj->kroky = calloc(DLZKA_CESTY,sizeof(KROK*));
  617.     okraj->pocet = 0;
  618.     okraj->limit = DLZKA_CESTY;
  619.     POSTUPNOST *ciele = malloc(sizeof(POSTUPNOST));
  620.     ciele->pozicie = calloc(4,sizeof(POZICIA*));
  621.     ciele->pocet = 0;
  622.     ciele->limit = 4;
  623.     ciele->cena =0;
  624.  
  625.     KROK ***kroky = malloc(n*sizeof(KROK**));
  626.     for( i = 0; i < n; i++) {
  627.         kroky[i] = malloc(m*sizeof(KROK*));
  628.         for( j = 0; j < m; j++) {
  629.             kroky[i][j] = malloc(sizeof(KROK));
  630.             kroky[i][j]->p = malloc(sizeof(POZICIA));
  631.                 kroky[i][j]->p->x = i;
  632.                 kroky[i][j]->p->y = j;
  633.             kroky[i][j]->z = NULL;
  634.             kroky[i][j]->cena = 0;
  635.             kroky[i][j]->index = -1;
  636.         }
  637.     }
  638.     // S -> D, V
  639.     POSTUPNOST *cesta_S_D = malloc(sizeof(POSTUPNOST));
  640.     cesta_S_D->pozicie = calloc(0,sizeof(POZICIA*));
  641.     cesta_S_D->pocet = 0;
  642.     cesta_S_D->limit = 0;
  643.     cesta_S_D->cena =0;
  644.     POSTUPNOST *cesta_S_V = malloc(sizeof(POSTUPNOST));
  645.     cesta_S_V->pozicie = calloc(0,sizeof(POZICIA*));
  646.     cesta_S_V->pocet = 0;
  647.     cesta_S_V->limit = 0;
  648.     cesta_S_V->cena =0;
  649.  
  650.     POSTUPNOST *cesta_V_D_tele = malloc(sizeof(POSTUPNOST));
  651.     cesta_V_D_tele->pozicie = calloc(0,sizeof(POZICIA*));
  652.     cesta_V_D_tele->pocet = 0;
  653.     cesta_V_D_tele->limit = 0;
  654.     cesta_V_D_tele->cena =0;
  655.  
  656.     POSTUPNOST *tmpPos = malloc(sizeof(POSTUPNOST));
  657.     tmpPos->pozicie = calloc(DLZKA_CESTY,sizeof(POZICIA*));
  658.     tmpPos->pocet = 0;
  659.     tmpPos->limit = DLZKA_CESTY;
  660.     tmpPos->cena =0;
  661.  
  662.     POSTUPNOST ***mapaTele = mapaPOSTUPNOSTi(p->pocet + 2);
  663.     POSTUPNOST ***mapaNoTele = mapaPOSTUPNOSTi(p->pocet + 2);
  664.  
  665.  
  666.     int ignoreTele = 0;
  667.     if((vypinac->x == -1) || (vypinac->y == -1)) ignoreTele = 1;
  668.  
  669.     // S -> D, V
  670.     ciele->pocet = 0;
  671.     int a;
  672.                     if(ciele->pocet == ciele->limit) {
  673.                         POZICIA **pozicie = calloc((ciele->limit+DLZKA_CESTY),sizeof(POZICIA*));
  674.                         for( a = 0; a < ciele->pocet; a++) {
  675.                             pozicie[a] = ciele->pozicie[a];
  676.                         }
  677.                         free(ciele->pozicie);
  678.                         ciele->pozicie = pozicie;
  679.                         ciele->limit = ciele->limit + DLZKA_CESTY;
  680.                     }
  681.                     ciele->pozicie[ciele->pocet] = d;
  682.                     ciele->pocet++;
  683.     if((vypinac->x != -1) || (vypinac->y != -1)) {
  684.     int a;
  685.                     if(ciele->pocet == ciele->limit) {
  686.                         POZICIA **pozicie = calloc((ciele->limit+DLZKA_CESTY),sizeof(POZICIA*));
  687.                         for( a = 0; a < ciele->pocet; a++) {
  688.                             pozicie[a] = ciele->pozicie[a];
  689.                         }
  690.                         free(ciele->pozicie);
  691.                         ciele->pozicie = pozicie;
  692.                         ciele->limit = ciele->limit + DLZKA_CESTY;
  693.                     }
  694.                     ciele->pozicie[ciele->pocet] = vypinac;
  695.                     ciele->pocet++;
  696.  
  697.     }
  698.  
  699.     hladajCestu(mapa, n, m, kroky, teleporty, okraj, start, ciele, 0);
  700.     citajCestuZKROKov(kroky, cesta_S_D, d);
  701.     if((vypinac->x != -1) || (vypinac->y != -1)) citajCestuZKROKov(kroky, cesta_S_V, vypinac);
  702.  
  703.     // V -tele> D, P1, P2, PPOCET_PRINCEZIEN
  704.  
  705.     if(ignoreTele == 0) {
  706.         ciele->pocet = 0;
  707.         addPOSTUPNOST(ciele, p);
  708.         if((d->x != -1) || (d->y != -1)) {
  709.         int a;
  710.                     if(ciele->pocet == ciele->limit) {
  711.                         POZICIA **pozicie = calloc((ciele->limit+DLZKA_CESTY),sizeof(POZICIA*));
  712.                         for( a = 0; a < ciele->pocet; a++) {
  713.                             pozicie[a] = ciele->pozicie[a];
  714.                         }
  715.                         free(ciele->pozicie);
  716.                         ciele->pozicie = pozicie;
  717.                         ciele->limit = ciele->limit + DLZKA_CESTY;
  718.                     }
  719.                     ciele->pozicie[ciele->pocet] = d;
  720.                     ciele->pocet++;
  721.  
  722.         }
  723.         hladajCestu(mapa, n, m, kroky, teleporty, okraj, vypinac, ciele, 1);
  724.         citajCestuZKROKov(kroky, cesta_V_D_tele, d);
  725.         for( i = 1; i <= p->pocet; i++) {
  726.             tmpPos->pocet = 0;
  727.             citajCestuZKROKov(kroky, tmpPos, p->pozicie[i-1]);
  728.             if(tmpPos->pocet > 0) {
  729.                 mapaTele[1][i+1] = tmpPos;
  730.                 tmpPos = malloc(sizeof(POSTUPNOST));
  731.                 tmpPos->pozicie = calloc(DLZKA_CESTY,sizeof(POZICIA*));
  732.                 tmpPos->pocet = 0;
  733.                 tmpPos->limit = DLZKA_CESTY;
  734.                 tmpPos->cena =0;
  735.             }
  736.         }
  737.     }
  738.  
  739.  
  740.     int ignoreNoTele = 0;
  741.     if((ignoreTele == 0) && ((cesta_S_D->cena + 1) > (cesta_S_V->cena + cesta_V_D_tele->cena + 1))) {
  742.         addPOSTUPNOST(vyslednaCesta, cesta_S_V);
  743.         addPOSTUPNOST(vyslednaCesta, cesta_V_D_tele);
  744.         ignoreNoTele = 1;
  745.     } else {
  746.         addPOSTUPNOST(vyslednaCesta, cesta_S_D);
  747.     }
  748.  
  749.  
  750.     if(ignoreNoTele == 0) {
  751.         for( i = 0; i < p->pocet+2 ; i++) {
  752.             ciele->pocet = 0;
  753.             addPOSTUPNOST(ciele, p);
  754.             if((vypinac->x != -1) || (vypinac->y != -1)) {
  755.             int a;
  756.                     if(ciele->pocet == ciele->limit) {
  757.                         POZICIA **pozicie = calloc((ciele->limit+DLZKA_CESTY),sizeof(POZICIA*));
  758.                         for( a = 0; a < ciele->pocet; a++) {
  759.                             pozicie[a] = ciele->pozicie[a];
  760.                         }
  761.                         free(ciele->pozicie);
  762.                         ciele->pozicie = pozicie;
  763.                         ciele->limit = ciele->limit + DLZKA_CESTY;
  764.                     }
  765.                     ciele->pozicie[ciele->pocet] = vypinac;
  766.                     ciele->pocet++;
  767.  
  768.             }
  769.             POZICIA *fromPoz = d;
  770.             if(i == 1) continue;
  771.             if(i > 1) fromPoz = p->pozicie[i-2];
  772.             hladajCestu(mapa, n, m, kroky, teleporty, okraj, fromPoz, ciele, 0);
  773.             for( j = 0; j < p->pocet + 2; j++) {
  774.                 if(i == j) continue;
  775.                 POZICIA *toPoz = d;
  776.                 if(j == 0) continue;
  777.                 if((j == 1) && ((vypinac->x == -1) || (vypinac->y == -1))) continue;
  778.                 if(j == 1) toPoz = vypinac;
  779.                 if(j > 1) toPoz = p->pozicie[j-2];
  780.                 tmpPos->pocet = 0;
  781.                 citajCestuZKROKov(kroky, tmpPos, toPoz);
  782.                 if(tmpPos->pocet > 0) {
  783.                     mapaNoTele[i][j] = tmpPos;
  784.                     tmpPos = malloc(sizeof(POSTUPNOST));
  785.                     tmpPos->pozicie = calloc(DLZKA_CESTY,sizeof(POZICIA*));
  786.                     tmpPos->pocet = 0;
  787.                     tmpPos->limit = DLZKA_CESTY;
  788.                     tmpPos->cena =0;
  789.                 }
  790.             }
  791.         }
  792.     }
  793.  
  794.     if(ignoreTele == 0) {
  795.         for( i = 0; i < p->pocet+2 ; i++) {
  796.             ciele->pocet = 0;
  797.             if(i == 1) continue;
  798.             addPOSTUPNOST(ciele, p);
  799.             POZICIA *fromPoz = d;
  800.             if(i > 1) fromPoz = p->pozicie[i-2];
  801.             hladajCestu(mapa, n, m, kroky, teleporty, okraj, fromPoz, ciele, 1);
  802.             for( j = 0; j < p->pocet + 2; j++) {
  803.                 if(i == j) continue;
  804.                 if(j < 2) continue;
  805.                 POZICIA *toPoz = p->pozicie[j-2];
  806.                 tmpPos->pocet = 0;
  807.                 citajCestuZKROKov(kroky, tmpPos, toPoz);
  808.                 if(tmpPos->pocet > 0) {
  809.                     mapaTele[i][j] = tmpPos;
  810.                     tmpPos = malloc(sizeof(POSTUPNOST));
  811.                     tmpPos->pozicie = calloc(DLZKA_CESTY,sizeof(POZICIA*));
  812.                     tmpPos->pocet = 0;
  813.                     tmpPos->limit = DLZKA_CESTY;
  814.                     tmpPos->cena =0;
  815.                 }
  816.             }
  817.         }
  818.     }
  819.  
  820.     POSTUPNOST **tmpCesta = malloc((p->pocet+2)*sizeof(POSTUPNOST*));
  821.     POSTUPNOST **minCesta = malloc((p->pocet+2)*sizeof(POSTUPNOST*));
  822.     for( i = 0; i < p->pocet + 2; i++) {
  823.         tmpCesta[i] = NULL;
  824.         minCesta[i] = NULL;
  825.     }
  826.  
  827.     int useTele = 1;
  828.     int useNoTele = 1;
  829.  
  830.     if(ignoreNoTele == 1) useNoTele = 0;
  831.     if(ignoreTele == 1) useTele = 0;
  832.  
  833.     POSTUPNOST *najdenePrincezne = malloc(sizeof(POSTUPNOST));
  834.     najdenePrincezne->pozicie = calloc(POCET_PRINCEZIEN,sizeof(POZICIA*));
  835.     najdenePrincezne->pocet = 0;
  836.     najdenePrincezne->limit = POCET_PRINCEZIEN;
  837.     najdenePrincezne->cena =0;
  838.     combine(mapaNoTele, mapaTele, p->pocet + 2
  839.             , 0, 0
  840.             , p, najdenePrincezne
  841.             , tmpCesta, minCesta, DLZKA_CESTY
  842.             , useTele, useNoTele);
  843.  
  844.     for( i = 0; i < p->pocet + 2; i++) {
  845.         POSTUPNOST *p = minCesta[i];
  846.         if(p == NULL) continue;
  847.        addPOSTUPNOST(vyslednaCesta, p);
  848.     }
  849.  
  850.     *dlzka_cesty = vyslednaCesta->pocet;
  851.     int *array = calloc(vyslednaCesta->pocet*2,sizeof(int));
  852.     int num = 0;
  853.     for( i = 0; i < vyslednaCesta->pocet; i++) {
  854.         array[num++] = vyslednaCesta->pozicie[i]->y;
  855.         array[num++] = vyslednaCesta->pozicie[i]->x;
  856.     }
  857.     return array;
  858. }
  859.  
  860. int main() {
  861.     int length;
  862.     int i=0;
  863.     int *res;
  864.     int map_w = 5;
  865.     int map_h = 5;
  866.     char map[5][5] = {
  867.             {'P', 'C', 'N', 'C', 'N'},
  868.             {'C', 'C', '0', 'C', 'P'},
  869.             {'C', '0', 'G', 'H', 'N'},
  870.             {'N', '0', 'N', 'H', 'N'},
  871.             {'N', 'P', 'N', 'N', 'D'}
  872.     };
  873.     char * map_d_r[5] = { map[0], map[1], map[2], map[POCET_PRINCEZIEN], map[4]};
  874.     char ** map_d = map_d_r;
  875. //    char * map_d_r[4] = { map[0], map[1], map[2], map[POCET_PRINCEZIEN]};
  876.  
  877.     res = zachran_princezne(map_d, map_h, map_w, POCET_TELEPORTOV, &length);
  878.     printf("dlzka cesty %d\n", length);
  879.     for(i=0; i < 2*length; i++) {
  880.         printf("x %d, y %d\n",res[i],res[i+1]);
  881.         i++;
  882.     }
  883.     return 0;
  884. }
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!