AlexandruT

Algoritmul lui Lee

Jul 10th, 2015
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. struct coord
  8. {
  9.     int x, y;
  10. };
  11.  
  12. queue <coord> q;
  13.  
  14. int a[105][105], b[105][105], l, c;
  15.  
  16. void Citire()
  17. {
  18.     int i, j;
  19.     ifstream fin("lee.in");
  20.     fin >> l >> c;
  21.     for(i = 1; i <= l; i++)
  22.         for(j = 1; j <= c; j++)
  23.             fin >> a[i][j];
  24.     fin.close();
  25. }
  26.  
  27. void Bordare()
  28. {
  29.     int i;
  30.     /// bordez coloanele 0 si c+1
  31.     for(i = 0; i<= l + 1; i++)
  32.         a[i][0] = a[i][c + 1] = 1;
  33.     /// bordez liniile 0 si l+1
  34.     for(i = 0; i <= c + 1; i++)
  35.         a[0][i] = a[l + 1][i] = 1;
  36. }
  37.  
  38. void Lee()
  39. {
  40.     coord w, w1;
  41.     w.x = 1;
  42.     w.y = 1;
  43.     q.push(w);
  44.     b[1][1] = 1;
  45.     while(!q.empty())
  46.     {
  47.         w = q.front();
  48.         q.pop();
  49.         /// nord
  50.         w1.x = w.x - 1;
  51.         w1.y = w.y;
  52.         if(a[w1.x][w1.y] == 0 &&
  53.            (b[w1.x][w1.y] == 0 || b[w1.x][w1.y] > b[w.x][w.y] + 1))
  54.         {
  55.             b[w1.x][w1.y] = b[w.x][w.y] + 1;
  56.             q.push(w1);
  57.         }
  58.         /// sud
  59.         w1.x = w.x + 1;
  60.         w1.y = w.y;
  61.         if(a[w1.x][w1.y] == 0 &&
  62.            (b[w1.x][w1.y] == 0 || b[w1.x][w1.y] > b[w.x][w.y] + 1))
  63.         {
  64.             b[w1.x][w1.y] = b[w.x][w.y] + 1;
  65.             q.push(w1);
  66.         }
  67.         /// est
  68.         w1.x = w.x;
  69.         w1.y = w.y + 1;
  70.         if(a[w1.x][w1.y] == 0 &&
  71.            (b[w1.x][w1.y] == 0 || b[w1.x][w1.y] > b[w.x][w.y] + 1))
  72.         {
  73.             b[w1.x][w1.y] = b[w.x][w.y] + 1;
  74.             q.push(w1);
  75.         }
  76.         /// vest
  77.         w1.x = w.x;
  78.         w1.y = w.y - 1;
  79.         if(a[w1.x][w1.y] == 0 &&
  80.            (b[w1.x][w1.y] == 0 || b[w1.x][w1.y] > b[w.x][w.y] + 1))
  81.         {
  82.             b[w1.x][w1.y] = b[w.x][w.y] + 1;
  83.             q.push(w1);
  84.         }
  85.     }
  86. }
  87.  
  88. void Afisare()
  89. {
  90.     int i, j;
  91.     for(i = 1; i <= l; i++)
  92.     {
  93.         for(j = 1; j <= c; j++)
  94.             cout << b[i][j] << " ";
  95.         cout << "\n";
  96.     }
  97. }
  98. int main()
  99. {
  100.     Citire();
  101.     Bordare();
  102.     Lee();
  103.     Afisare();
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment