API tools faq
paste
Advertisement
Guest User

asp2

a guest
Dec 12th, 2019
114
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.26 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <stdlib.h>
  3. using namespace std;
  4.  
  5. class koordinate {
  6.     int x, y;
  7. public:
  8.     koordinate(int x=0, int y=0)
  9.     {
  10.         this->x = x;
  11.         this->y = y;
  12.     }
  13.     void setX(int x)
  14.     {
  15.         this->x = x;
  16.     }
  17.     void setY(int y)
  18.     {
  19.         this->y = y;
  20.     }
  21.     int getX()
  22.     {
  23.         return x;
  24.     }
  25.     int getY()
  26.     {
  27.         return y;
  28.     }
  29. };
  30.  
  31. class graf {
  32. private:
  33.     int b[50][50];
  34.     int ukupcv;
  35.     bool cvpostoji[50];
  36.     int visina, sirina;
  37.     koordinate kord[50];
  38.     koordinate potcv[500];
  39.     int brpotcv;
  40. public:
  41.     graf(int sir, int vis)
  42.     {
  43.         if (sir > 80 || vis > 50) { cout << "Greska! Prekoracene maksimalne dimenzije 80x50!\n"; return; }
  44.         visina = vis;
  45.         sirina = sir;
  46.         ukupcv = 0;
  47.         brpotcv = 0;
  48.         for (int i = 0; i < 50; i++) { cvpostoji[i] = false; kord[i].setX(-1); kord[i].setY(-1); }
  49.     }
  50.     void inicgraf(int sir, int vis)
  51.     {
  52.         if (sir > 80 || vis > 50) { cout << "Greska! Prekoracene maksimalne dimenzije 80x50!\n"; return; }
  53.         visina = vis;
  54.         sirina = sir;
  55.         ukupcv = 0;
  56.         brpotcv = 0;
  57.         for (int i = 0; i < 50; i++) { cvpostoji[i] = false; kord[i].setX(-1); kord[i].setY(-1); }
  58.  
  59.     }
  60.     void ispisgrafa()
  61.     {
  62.  
  63.         cout << "\n";
  64.         for (int i = 0; i < ukupcv; i++)
  65.         {
  66.             if (cvpostoji[i])
  67.             {
  68.                 cout << "Cvor: " << i + 1 << " ";
  69.                 for (int j = 0; j < ukupcv; j++)
  70.                 {
  71.                     if (!cvpostoji[j]) { continue; }
  72.                     cout << "|" << b[i][j];
  73.                 }
  74.                 cout << "| Koordinate: X="<<kord[i].getX()<<" Y="<< kord[i].getY()<<"\n";
  75.             }
  76.         }
  77.     }
  78.  
  79.     bool postojicvornakord(int a, int b)
  80.     {
  81.         bool postoji = false;
  82.         for (int i = 0; i < 50; i++)
  83.         {
  84.             if (kord[i].getX() == a && kord[i].getY() == b)
  85.             {
  86.                 postoji = true;
  87.                 break;
  88.             }
  89.         }
  90.         return postoji;
  91.     }
  92.  
  93.    
  94.     void ispislavirinta()
  95.     {
  96.  
  97.         cout << "\n";
  98.         for (int i = 0; i < visina; i++)
  99.         {
  100.                 cout << "|";
  101.                 for (int j = 0; j < sirina; j++)
  102.                 {
  103.                     if (brojcvoranakord(j, i) == 0) { cout << "U "; continue; }
  104.                     if (brojcvoranakord(j, i) == 1) { cout << "I "; continue; }
  105.                     if (postojipotcvornakord(j, i))
  106.                     {
  107.                         cout << "  ";
  108.                     }
  109.                     else
  110.                         cout << "X ";
  111.                 }
  112.                 cout << "|\n";
  113.         }
  114.  
  115.     }
  116.  
  117.  
  118.     void dodajpocetak(int x, int y)
  119.     {
  120.         if (brpotcv==2)
  121.         {
  122.             cout << "Greska! Vec ste uneli pocetni i krajnji cvor!";
  123.             return;
  124.         }
  125.         if (!(x == 0 || y == 0 || x == sirina-1 || y == visina-1))
  126.         {
  127.             cout << "\nGreska! Pocetak mora da bude uz ivicu lavirinta!\n";
  128.             return;
  129.         }
  130.  
  131.         potcv[brpotcv].setY(y);
  132.         potcv[brpotcv++].setX(x);
  133.     }
  134.  
  135.     bool postojipotcvornakord(int a, int b)
  136.     {
  137.         bool postoji = false;
  138.         if (a > sirina || b > visina || a == -1 || b == -1) { return postoji; }
  139.         for (int i = 0; i < brpotcv; i++)
  140.         {
  141.             if (potcv[i].getX() == a && potcv[i].getY() == b)
  142.             {
  143.                 postoji = true;
  144.                 break;
  145.             }
  146.         }
  147.         return postoji;
  148.     }
  149.     void dodajpotcv(int a, int b)
  150.     {
  151.         if (postojipotcvornakord(a, b)) { cout << "\nPostoji prolaz na tim koordinatama!\n"; return; }
  152.         if (a + 1 > sirina || b + 1 > visina) { cout << "\nGreska! Van opsega!\n"; return; }
  153.         potcv[brpotcv].setY(b);
  154.         potcv[brpotcv++].setX(a);
  155.     }
  156.  
  157.     int brojcvoranakord(int a, int b)
  158.     {
  159.         int ind = -1;
  160.         for (int i = 0; i < 50; i++)
  161.         {
  162.             if (kord[i].getX() == a && kord[i].getY() == b)
  163.             {
  164.                 ind = i;
  165.                 break;
  166.             }
  167.         }
  168.         return ind;
  169.     }
  170.  
  171.     void dodajcvor(int x, int y)
  172.     {
  173.         for (int i = 0; i < ukupcv; i++)
  174.         {
  175.             if (!cvpostoji[i])
  176.             {
  177.                 for (int j = 0; j <= ukupcv; j++)
  178.                 {
  179.                     b[i][j] = 0;
  180.                     b[j][i] = 0;
  181.                     cvpostoji[i] = true;
  182.                     kord[i].setX(x);
  183.                     kord[i].setY(y);
  184.                 }
  185.                 return;
  186.             }
  187.         }
  188.         for (int i = 0; i <= ukupcv; i++)
  189.         {
  190.             b[ukupcv][i] = 0;
  191.             b[i][ukupcv] = 0;
  192.         }
  193.         cvpostoji[ukupcv] = true;
  194.         kord[ukupcv].setX(x);
  195.         kord[ukupcv].setY(y);
  196.         //cout << "\nNovi cvor dodat na novo mesto: " << ukupcv + 1 << " !";
  197.         ukupcv++;
  198.     }
  199.  
  200.     void potcvjecvor(int b) //ispitivanje da li je potencijalni cvor, odnosno jedan pomeraj u lavirintu raskrsnica, odnosno cvor grafa
  201.     {
  202.         bool gore = false;
  203.         bool dole = false;
  204.         bool levo = false;
  205.         bool desno = false;
  206.         if (postojipotcvornakord(potcv[b].getX() - 1, potcv[b].getY())) levo = true;
  207.         if (postojipotcvornakord(potcv[b].getX() + 1, potcv[b].getY())) desno = true;
  208.         if (postojipotcvornakord(potcv[b].getX(), potcv[b].getY() - 1)) gore = true;
  209.         if (postojipotcvornakord(potcv[b].getX(), potcv[b].getY() + 1)) dole = true;
  210.         if (!(((dole && gore) && (!levo && !desno)) || (levo && desno) && (!gore && !dole)))
  211.         {
  212.             dodajcvor(potcv[b].getX(), potcv[b].getY());
  213.         }
  214.     }
  215.  
  216.     void potcvucvor()
  217.     {
  218.         for (int i = 0; i < brpotcv; i++)
  219.         {
  220.             potcvjecvor(i);
  221.         }
  222.     }
  223.  
  224.  
  225.  
  226.     void dodajgranu(int prvi, int drugi)
  227.     {
  228.         if ((prvi < ukupcv) && (drugi < ukupcv) && (cvpostoji[prvi]) && (cvpostoji[drugi]))
  229.         {
  230.             b[prvi][drugi] = 1;
  231.             b[drugi][prvi] = 1;
  232.         }
  233.         else
  234.         {
  235.             cout << "Greska! Neki od cvorova ne postoji u grafu!   "<<prvi<<"  "<<drugi;
  236.         }
  237.     }
  238.  
  239.  
  240.     void spoji(int a, int b, int c, int d)
  241.     {
  242.         int poz1 = brojcvoranakord(a, b);
  243.         int poz2 = brojcvoranakord(c, d);
  244.         dodajgranu(poz1, poz2);
  245.     }
  246.  
  247.     void brisigraf()
  248.     {
  249.         for (int i = 0; i < 50; i++) cvpostoji[i] = false;
  250.         ukupcv = 0;
  251.         cout << "\nUpesno izbrisan graf!\n";
  252.     }
  253.  
  254.     void povezigraf()
  255.     {
  256.         for (int i = 0; i < ukupcv; i++)
  257.         {
  258.             int s = kord[i].getX();
  259.             int v = kord[i].getY();
  260.             //horizontala
  261.             s++;
  262.             while (s < sirina)
  263.             {
  264.                 if (!postojipotcvornakord(s, v))
  265.                     break;
  266.                 if (postojicvornakord(s, v))
  267.                 {
  268.                     dodajgranu(brojcvoranakord(s, v), i);
  269.                     break;
  270.                 }
  271.                 s++;
  272.             }
  273.  
  274.         }
  275.  
  276.         for (int i = 0; i < ukupcv; i++)
  277.         {
  278.             int s = kord[i].getX();
  279.             int v = kord[i].getY();
  280.             //vertikala
  281.             v++;
  282.             while (v < visina)
  283.             {
  284.                 if (!postojipotcvornakord(s, v))
  285.                     break;
  286.                 if (postojicvornakord(s, v))
  287.                 {
  288.                     dodajgranu(brojcvoranakord(s, v), i);
  289.                     break;
  290.                 }
  291.                 v++;
  292.             }
  293.  
  294.         }
  295.  
  296.     }
  297.    
  298.     void dijkstra()
  299.     {
  300.         int *najkr=new int[ukupcv];
  301.         int* prethodnik = new int[ukupcv];
  302.         bool *posecen=new bool[ukupcv];
  303.         for (int i = 1; i < ukupcv; i++) { posecen[i] = false; }
  304.         for (int i = 1; i < ukupcv; i++) { prethodnik[i] = b[0][i]; }
  305.         for (int i = 1; i < ukupcv; i++) { if (b[0][i] == 1) najkr[i] = 1; else najkr[i] = 500; }
  306.         int indmin = 1;
  307.         while (1)
  308.         {
  309.            
  310.             indmin = 1;
  311.             for (int i = 1; i < ukupcv; i++)
  312.             {
  313.                 if ((najkr[i] < najkr[indmin]) && !posecen[i]) { indmin = i; break;}
  314.             }
  315.             //cout << "\nIndmin je:" << indmin;
  316.             posecen[indmin] = true;
  317.             if (indmin == 1) break;
  318.             for (int i = 1; i < ukupcv; i++)
  319.             {
  320.                 if ((b[indmin][i] == 1)&& !posecen[i])
  321.                 {
  322.                     najkr[i] = najkr[indmin] + 1;
  323.                     prethodnik[i] = indmin+1;
  324.                 }
  325.             }  
  326.         }
  327.  
  328.         cout << "\nDIJKSTRA REZULTAT:";
  329.         cout << "\nVektor najkracih rast: \n";
  330.         for (int i = 1; i < ukupcv; i++) { cout << " " << najkr[i]; }
  331.         cout << "\nVektor posecenih: \n";
  332.         for (int i = 1; i < ukupcv; i++) { cout << " " << posecen[i]; }
  333.         cout << "\nVektor prethodnih: \n";
  334.         for (int i = 1; i < ukupcv; i++) { cout << " " << prethodnik[i]; }
  335.         cout << "\n";
  336.  
  337.         int putanja[50];
  338.         int brputanja = 0;
  339.         int pozicija=1;
  340.         bool imaputanja = true;
  341.  
  342.         while (pozicija != 0)
  343.         {
  344.             if (prethodnik[pozicija] == 0) { imaputanja = false; break; }
  345.             putanja[brputanja++] = prethodnik[pozicija] - 1;
  346.             pozicija = prethodnik[pozicija] - 1;
  347.         }
  348.         if (imaputanja)
  349.         {
  350.             cout << "\nPostoji putanja!\nPutanja kroz lavirint: ";
  351.             for (int i = brputanja - 1; i >= 0; i--)
  352.             {
  353.                 cout << "(" << kord[putanja[i]].getX() << ", " << kord[putanja[i]].getY() << ") -> ";
  354.             }
  355.             cout << "(" << kord[1].getX() << ", " << kord[1].getY() << ") \n\n\n";
  356.         }
  357.         else
  358.         {
  359.             cout << "\nNe postoji putanja!\n";
  360.         }
  361.  
  362.         delete[] najkr;
  363.         delete[] posecen;
  364.         delete[] prethodnik;
  365.     }
  366.  
  367.  
  368. };
  369.  
  370.  
  371.  
  372. int main()
  373. {
  374.     //primer 1
  375.     /*graf g(6, 6);
  376.     g.dodajpocetak(1, 5);
  377.     g.dodajpocetak(5, 2);
  378.     g.dodajpotcv(1, 4);
  379.     g.dodajpotcv(2, 4);
  380.     g.dodajpotcv(3, 4);
  381.     g.dodajpotcv(4, 4);
  382.     g.dodajpotcv(3, 3);
  383.     g.dodajpotcv(3, 2);
  384.     g.dodajpotcv(3, 1);
  385.     g.dodajpotcv(4, 2);
  386.     g.dodajpotcv(2, 1);
  387.     g.dodajpotcv(1, 1);
  388.     g.dodajpotcv(1, 2);*/
  389.  
  390.     //primer 2
  391.  
  392.     /*graf g(10, 10);
  393.     g.dodajpocetak(0, 7);
  394.     g.dodajpocetak(8, 9);
  395.     g.dodajpotcv(1, 7);
  396.     g.dodajpotcv(1, 6);
  397.     g.dodajpotcv(1, 5);
  398.     g.dodajpotcv(1, 4);
  399.     g.dodajpotcv(1, 3);
  400.     g.dodajpotcv(1, 2);
  401.     g.dodajpotcv(2, 2);
  402.     g.dodajpotcv(3, 2);
  403.     g.dodajpotcv(4, 2);
  404.     g.dodajpotcv(5, 2);
  405.     g.dodajpotcv(6, 2);
  406.     g.dodajpotcv(7, 2);
  407.     g.dodajpotcv(8, 2);
  408.     g.dodajpotcv(3, 1);
  409.     g.dodajpotcv(7, 1);
  410.     g.dodajpotcv(7, 0);
  411.     g.dodajpotcv(8, 0);
  412.     g.dodajpotcv(4, 3);
  413.     g.dodajpotcv(4, 4);
  414.     g.dodajpotcv(4, 5);
  415.     g.dodajpotcv(4, 6);
  416.     g.dodajpotcv(4, 7);
  417.     g.dodajpotcv(4, 8);
  418.     g.dodajpotcv(3, 8);
  419.     g.dodajpotcv(5, 6);
  420.     g.dodajpotcv(6, 6);
  421.     g.dodajpotcv(6, 5);
  422.     g.dodajpotcv(6, 4);
  423.     g.dodajpotcv(6, 7);
  424.     g.dodajpotcv(6, 8);
  425.     g.dodajpotcv(6, 9);
  426.     g.dodajpotcv(7, 9);
  427.     g.dodajpotcv(7, 4);
  428.     g.dodajpotcv(7, 7);
  429.     g.dodajpotcv(8, 4);
  430.     g.dodajpotcv(8, 5);
  431.     g.dodajpotcv(8, 6);
  432.     g.dodajpotcv(8, 7);
  433.  
  434.    
  435.     g.potcvucvor();
  436.     g.povezigraf();
  437.     g.ispisgrafa();
  438.     g.ispislavirinta();
  439.     g.dijkstra();*/
  440.  
  441.     char izb;
  442.     int a, b;
  443.     graf g(80, 50);
  444.     cout << "Izaberi operaciju: \n1) Novi lavirint: unos dimenzija\n2) Unos ulaza i izlaza iz lavirinta\n3) Dodavanje putanja\n4) Pronalazenje puta \n5) TEST PRIMER \n";
  445.     cin >> izb;
  446.     while (izb < '6')
  447.     {
  448.         switch (izb)
  449.         {
  450.         default:
  451.             break;
  452.         case '1':
  453.  
  454.             cout << "\nStvaranje lavirinta - unesi dimenzije: ";
  455.             cin >> a>>b;
  456.             g.inicgraf(a, b);
  457.             cout << "\nIzaberi novu opciju:";
  458.             cin >> izb;
  459.             break;
  460.         case '2':
  461.             cout << "\nStvaranje lavirinta - unesi dimenzije ulaza: ";
  462.             cin >> a >> b;
  463.             g.dodajpocetak(a, b);
  464.             cout << "\nStvaranje lavirinta - unesi dimenzije izlaza: ";
  465.             cin >> a >> b;
  466.             g.dodajpocetak(a, b);
  467.             cout << "\nIzaberi novu opciju:";
  468.             cin >> izb;
  469.             break;
  470.         case '3':
  471.             cout << "\nDodavanje putanje - upisi dimenzije prolaza: ";
  472.             cin >> a>>b;
  473.             g.dodajpotcv(a, b);
  474.             cout << "\nIzaberi novu opciju:";
  475.             cin >> izb;
  476.             break;
  477.         case '4':
  478.             g.potcvucvor();
  479.             g.povezigraf();
  480.             g.ispisgrafa();
  481.             g.ispislavirinta();
  482.             g.dijkstra();
  483.             cout << "\nIzaberi novu opciju:";
  484.             cin >> izb;
  485.             break;
  486.         case '5':
  487.            
  488.             g.inicgraf(10, 10);
  489.             g.dodajpocetak(0, 7);
  490.             g.dodajpocetak(8, 9);
  491.             g.dodajpotcv(1, 7);
  492.             g.dodajpotcv(1, 6);
  493.             g.dodajpotcv(1, 5);
  494.             g.dodajpotcv(1, 4);
  495.             g.dodajpotcv(1, 3);
  496.             g.dodajpotcv(1, 2);
  497.             g.dodajpotcv(2, 2);
  498.             g.dodajpotcv(3, 2);
  499.             g.dodajpotcv(4, 2);
  500.             g.dodajpotcv(5, 2);
  501.             g.dodajpotcv(6, 2);
  502.             g.dodajpotcv(7, 2);
  503.             g.dodajpotcv(8, 2);
  504.             g.dodajpotcv(3, 1);
  505.             g.dodajpotcv(7, 1);
  506.             g.dodajpotcv(7, 0);
  507.             g.dodajpotcv(8, 0);
  508.             g.dodajpotcv(4, 3);
  509.             g.dodajpotcv(4, 4);
  510.             g.dodajpotcv(4, 5);
  511.             g.dodajpotcv(4, 6);
  512.             g.dodajpotcv(4, 7);
  513.             g.dodajpotcv(4, 8);
  514.             g.dodajpotcv(3, 8);
  515.             g.dodajpotcv(5, 6);
  516.             g.dodajpotcv(6, 6);
  517.             g.dodajpotcv(6, 5);
  518.             g.dodajpotcv(6, 4);
  519.             g.dodajpotcv(6, 7);
  520.             g.dodajpotcv(6, 8);
  521.             g.dodajpotcv(6, 9);
  522.             g.dodajpotcv(7, 9);
  523.             g.dodajpotcv(7, 4);
  524.             g.dodajpotcv(7, 7);
  525.             g.dodajpotcv(8, 4);
  526.             g.dodajpotcv(8, 5);
  527.             g.dodajpotcv(8, 6);
  528.             g.dodajpotcv(8, 7);
  529.  
  530.             g.potcvucvor();
  531.             g.povezigraf();
  532.             g.ispisgrafa();
  533.             g.ispislavirinta();
  534.             g.dijkstra();
  535.  
  536.             cout << "\nIzaberi novu opciju:";
  537.             cin >> izb;
  538.             break;
  539.         }
  540.     }
  541. }
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!