Advertisement
Tucancitto

Algoritmul lui Lee

Feb 4th, 2021 (edited)
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <iomanip>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. struct Punct
  8. {
  9.     int coordX, coordY;
  10. }start;
  11.  
  12. queue <pair<int, int>> coada;
  13.  
  14. const int di[] = { -1, 0, 1, 0 };
  15. const int dj[] = { 0, 1, 0, -1 };
  16.  
  17. void Citire(int drumuri[][20], int& nrLinii, int& nrColoane, int& nrObstacole)
  18. {
  19.     ifstream fin("alee.in");
  20.  
  21.     fin >> nrLinii >> nrColoane >> nrObstacole;
  22.  
  23.     for (int i = 0; i < nrObstacole; i++)
  24.     {
  25.         Punct obstacol = { 0 };
  26.         fin >> obstacol.coordX >> obstacol.coordY;
  27.         drumuri[obstacol.coordX][obstacol.coordY] = -1;
  28.     }
  29.  
  30.     fin >> start.coordX >> start.coordY;
  31.     drumuri[start.coordX][start.coordY] = 0;
  32. }
  33.  
  34. bool verif(Punct urmator, int nrLinii, int nrColoane)
  35. {
  36.     if (urmator.coordX < 0 || urmator.coordY < 0 || urmator.coordX >= nrLinii || urmator.coordY >= nrColoane)
  37.         return false;
  38.     return true;
  39. }
  40.  
  41. void Lee(int drumuri[][20], int nrLinii, int nrColoane)
  42. {
  43.     Punct curent = { 0 }, urmator = { 0 };
  44.     coada.push(make_pair(start.coordX, start.coordY));
  45.  
  46.     while (!coada.empty())
  47.     {
  48.         curent.coordX = coada.front().first;
  49.         curent.coordY = coada.front().second;
  50.  
  51.         for (int dir = 0; dir < 4; dir++)
  52.         {
  53.             urmator.coordX = curent.coordX + di[dir];
  54.             urmator.coordY = curent.coordY + dj[dir];
  55.             if (verif(urmator, nrLinii, nrColoane) && drumuri[urmator.coordX][urmator.coordY] == 0)
  56.             {
  57.                 drumuri[urmator.coordX][urmator.coordY] = drumuri[curent.coordX][curent.coordY] + 1;
  58.                 coada.push(make_pair(urmator.coordX, urmator.coordY));
  59.             }
  60.         }
  61.         coada.pop();
  62.     }
  63.     drumuri[start.coordX][start.coordY] = 0;
  64.     return;
  65. }
  66.  
  67. void Afisare(int drumuri[][20], int nrLinii, int nrColoane)
  68. {
  69.     for (int i = 0; i < nrLinii; i++, cout << endl)
  70.         for (int j = 0; j < nrColoane; j++)
  71.             cout << setw(4) << drumuri[i][j];
  72. }
  73.  
  74. int main()
  75. {
  76.     int drumuri[20][20] = { 0 }, nrLinii, nrColoane, nrObstacole;
  77.     Citire(drumuri, nrLinii, nrColoane, nrObstacole);
  78.     Lee(drumuri, nrLinii, nrColoane);
  79.     Afisare(drumuri, nrLinii, nrColoane);
  80.  
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement