silviubogan

Teste pentru ex. b de la problema labirintului

Jan 8th, 2019
16
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <queue>
  3. #include <utility>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 101;
  9. const int inf = 1 << 30;
  10. const int dx[] = { 0, 1, 0, -1 };
  11. const int dy[] = { 1, 0, -1, 0 };
  12.  
  13. void citire(bool A[maxn][maxn], int &N)
  14. {
  15.     ifstream in("ex-b.in");
  16.     in >> N;
  17.     for (int i = 1; i <= N; ++i)
  18.         for (int j = 1; j <= N; ++j)
  19.             in >> A[i][j];
  20.  
  21.     in.close();
  22. }
  23.  
  24. bool valid(int N, int x, int y)
  25. {
  26.     return x >= 1 && y >= 1 &&
  27.         x <= N && y <= N;
  28. }
  29.  
  30. void spatii(int x)
  31. {
  32.     for (int j = 0; j < x; ++j)
  33.     {
  34.         cout << " ";
  35.     }
  36. }
  37.  
  38. void Lee(bool A[maxn][maxn], int N, int x,
  39.     int y, int D[maxn][maxn], bool &changed, int level)
  40. {
  41.     changed = false;
  42.     for (int i = 0; i < 4; ++i)
  43.     {
  44.         int newx = x + dx[i];
  45.         int newy = y + dy[i];
  46.  
  47.         if (valid(N, newx, newy))
  48.         {
  49.             if (!A[newx][newy] &&
  50.                 D[newx][newy] > D[x][y] + 1)
  51.             {
  52.                 int val_veche = D[newx][newy];
  53.                 D[newx][newy] = D[x][y] + 1;
  54.                
  55.                 changed = true;
  56.  
  57.                 spatii(level);
  58.                 cout << "> (" << newx << ", " << newy <<
  59.                     "): din " << val_veche << " in " << D[newx][newy] << "."
  60.                     << endl;
  61.  
  62.                 for (int i = 1; i <= N; ++i)
  63.                 {
  64.                     spatii(level);
  65.                     for (int j = 1; j <= N; ++j)
  66.                     {
  67.                         cout << D[i][j] << " ";
  68.                     }
  69.                     cout << endl;
  70.                 }
  71.                 cout << endl;
  72.  
  73.                 spatii(level);
  74.                 cout << "> Urmeaza parcurgerea vecinilor lui (" << newx << ',' <<
  75.                     newy << "):" << endl;
  76.  
  77.                 bool subchange = false;
  78.  
  79.                 level += 4;
  80.                 Lee(A, N, newx, newy, D, subchange, level);
  81.                 level -= 4;
  82.  
  83.                 if (!subchange)
  84.                 {
  85.                     spatii(level);
  86.                     cout << "> Nu au fost vecini de schimbat." << endl;
  87.                 }
  88.                 else
  89.                 {
  90.                     spatii(level);
  91.                     cout << "> Vecinii lui (" << newx << ',' <<
  92.                         newy << ") au fost parcursi." << endl;
  93.                 }
  94.             }
  95.             else
  96.             {
  97.                 spatii(level);
  98.                 cout << "> Valoare neschimbata in (" << newx << ", " << newy <<
  99.                     ")." << endl;
  100.             }
  101.         }
  102.     }
  103. }
  104.  
  105. void Lee_optim(bool A[maxn][maxn], int N,
  106.     int x, int y,
  107.     int D[maxn][maxn], int &count)
  108. {
  109.     queue<pair<int, int>> Q;
  110.     Q.push(make_pair(x, y));
  111.  
  112.     while (!Q.empty())
  113.     {
  114.         pair<int, int> poz = Q.front();
  115.         Q.pop();
  116.         ++count;
  117.  
  118.         for (int i = 0; i < 4; ++i)
  119.         {
  120.             int newx = poz.first + dx[i];
  121.             int newy = poz.second + dy[i];
  122.  
  123.             if (valid(N, newx, newy))
  124.             {
  125.                 if (!A[newx][newy] &&
  126.                     D[newx][newy] > D[poz.first][poz.second] + 1)
  127.                 {
  128.                     D[newx][newy] = D[poz.first][poz.second] + 1;
  129.                     Q.push(make_pair(newx, newy));
  130.                 }
  131.             }
  132.         }
  133.     }
  134. }
  135.  
  136. void init(int D[maxn][maxn],
  137.     int N, int x, int y)
  138. {
  139.     for (int i = 1; i <= N; ++i)
  140.     {
  141.         for (int j = 1; j <= N; ++j)
  142.         {
  143.             D[i][j] = inf;
  144.         }
  145.     }
  146.     D[x][y] = 0;
  147. }
  148.  
  149. void testare_algoritm_recursiv(bool A[maxn][maxn], int N,
  150.     int start_x, int start_y, int D[maxn][maxn])
  151. {
  152.     cout << "> Urmeaza parcurgerea vecinilor lui (0,0) " <<
  153.     "- punctul de pornire:" << endl;
  154.  
  155.     bool changed;
  156.     int level = 4;
  157.     Lee(A, N, start_x, start_y, D, changed, level);
  158.  
  159.     cout << "> Vecinii lui (0,0) au fost parcursi." <<
  160.         " Algoritmul s-a incheiat." << endl;
  161. }
  162.  
  163. void testare_algoritm_optim(bool A[maxn][maxn], int N,
  164.     int start_x, int start_y, int D[maxn][maxn])
  165. {
  166.     int count = 0;
  167.     Lee_optim(A, N, start_x, start_y, D, count);
  168.     cout << "Pasi cu algoritmul optim nerecursiv: " << count << endl;
  169. }
  170.  
  171. int main()
  172. {
  173.     int N;
  174.     bool A[maxn][maxn];
  175.     int D[maxn][maxn];
  176.  
  177.     citire(A, N);
  178.  
  179.     int start_x = 1; // x - linia, y - coloana
  180.     int start_y = 1;
  181.  
  182.     init(D, N, start_x, start_y);
  183.  
  184.     testare_algoritm_recursiv(A, N, start_x, start_y, D);
  185.     // sau:
  186.     //testare_algoritm_optim(A, N, start_x, start_y, D);
  187.  
  188.     const int end_x = 3;
  189.     const int end_y = 2;
  190.  
  191.     ofstream out("ex-b.out");
  192.     out << D[end_x][end_y] << endl;
  193.     out.close();
  194.  
  195.     return 0;
  196. }
RAW Paste Data