Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <queue>
- #include <utility>
- #include <iostream>
- using namespace std;
- const int maxn = 101;
- const int inf = 1 << 30;
- const int dx[] = { 0, 1, 0, -1 };
- const int dy[] = { 1, 0, -1, 0 };
- void citire(bool A[maxn][maxn], int &N)
- {
- ifstream in("ex-b.in");
- in >> N;
- for (int i = 1; i <= N; ++i)
- for (int j = 1; j <= N; ++j)
- in >> A[i][j];
- in.close();
- }
- bool valid(int N, int x, int y)
- {
- return x >= 1 && y >= 1 &&
- x <= N && y <= N;
- }
- void spatii(int x)
- {
- for (int j = 0; j < x; ++j)
- {
- cout << " ";
- }
- }
- void Lee(bool A[maxn][maxn], int N, int x,
- int y, int D[maxn][maxn], bool &changed, int level)
- {
- changed = false;
- for (int i = 0; i < 4; ++i)
- {
- int newx = x + dx[i];
- int newy = y + dy[i];
- if (valid(N, newx, newy))
- {
- if (!A[newx][newy] &&
- D[newx][newy] > D[x][y] + 1)
- {
- int val_veche = D[newx][newy];
- D[newx][newy] = D[x][y] + 1;
- changed = true;
- spatii(level);
- cout << "> (" << newx << ", " << newy <<
- "): din " << val_veche << " in " << D[newx][newy] << "."
- << endl;
- for (int i = 1; i <= N; ++i)
- {
- spatii(level);
- for (int j = 1; j <= N; ++j)
- {
- cout << D[i][j] << " ";
- }
- cout << endl;
- }
- cout << endl;
- spatii(level);
- cout << "> Urmeaza parcurgerea vecinilor lui (" << newx << ',' <<
- newy << "):" << endl;
- bool subchange = false;
- level += 4;
- Lee(A, N, newx, newy, D, subchange, level);
- level -= 4;
- if (!subchange)
- {
- spatii(level);
- cout << "> Nu au fost vecini de schimbat." << endl;
- }
- else
- {
- spatii(level);
- cout << "> Vecinii lui (" << newx << ',' <<
- newy << ") au fost parcursi." << endl;
- }
- }
- else
- {
- spatii(level);
- cout << "> Valoare neschimbata in (" << newx << ", " << newy <<
- ")." << endl;
- }
- }
- }
- }
- void Lee_optim(bool A[maxn][maxn], int N,
- int x, int y,
- int D[maxn][maxn], int &count)
- {
- queue<pair<int, int>> Q;
- Q.push(make_pair(x, y));
- while (!Q.empty())
- {
- pair<int, int> poz = Q.front();
- Q.pop();
- ++count;
- for (int i = 0; i < 4; ++i)
- {
- int newx = poz.first + dx[i];
- int newy = poz.second + dy[i];
- if (valid(N, newx, newy))
- {
- if (!A[newx][newy] &&
- D[newx][newy] > D[poz.first][poz.second] + 1)
- {
- D[newx][newy] = D[poz.first][poz.second] + 1;
- Q.push(make_pair(newx, newy));
- }
- }
- }
- }
- }
- void init(int D[maxn][maxn],
- int N, int x, int y)
- {
- for (int i = 1; i <= N; ++i)
- {
- for (int j = 1; j <= N; ++j)
- {
- D[i][j] = inf;
- }
- }
- D[x][y] = 0;
- }
- void testare_algoritm_recursiv(bool A[maxn][maxn], int N,
- int start_x, int start_y, int D[maxn][maxn])
- {
- cout << "> Urmeaza parcurgerea vecinilor lui (0,0) " <<
- "- punctul de pornire:" << endl;
- bool changed;
- int level = 4;
- Lee(A, N, start_x, start_y, D, changed, level);
- cout << "> Vecinii lui (0,0) au fost parcursi." <<
- " Algoritmul s-a incheiat." << endl;
- }
- void testare_algoritm_optim(bool A[maxn][maxn], int N,
- int start_x, int start_y, int D[maxn][maxn])
- {
- int count = 0;
- Lee_optim(A, N, start_x, start_y, D, count);
- cout << "Pasi cu algoritmul optim nerecursiv: " << count << endl;
- }
- int main()
- {
- int N;
- bool A[maxn][maxn];
- int D[maxn][maxn];
- citire(A, N);
- int start_x = 1; // x - linia, y - coloana
- int start_y = 1;
- init(D, N, start_x, start_y);
- testare_algoritm_recursiv(A, N, start_x, start_y, D);
- // sau:
- //testare_algoritm_optim(A, N, start_x, start_y, D);
- const int end_x = 3;
- const int end_y = 2;
- ofstream out("ex-b.out");
- out << D[end_x][end_y] << endl;
- out.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement