Algoritmul Lui Lee && Drum Optim

Apr 10th, 2019
100
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include "pch.h"
2. #include <iostream>
3. #include <fstream>
4. #include <queue>
5.
6. using namespace std;
7. #define DIMEN 10
8. #define POSIT 4
9.
10. ifstream in("date.in");
11. ofstream out("date.out");
12.
13. int n, m, matrice[DIMEN][DIMEN], matriceLee[DIMEN][DIMEN];
14. int startx, starty, stopx, stopy;
15. int di[POSIT] = { 0, 0, -1, 1 };
16. int dj[POSIT] = { -1, 1, 0, 0 };
17. queue < pair < int, int > > Coada;
18. struct {
19.     int x, y;
20. }stiva[DIMEN * DIMEN];
21. int k = 0;
22.
23. void Citire();
24. void Afisare();
25. bool e_ok(int i, int j);
26. void agl_Lee();
27. void Drum_Optim();
28.
29. int main() {
30.     Citire();
31.     agl_Lee();
32.     for (int i = 0; i < n; i++) {
33.         for (int j = 0; j < m; j++)
34.             cout << matriceLee[i][j] << " ";
35.         cout << endl;
36.     }
37.     Drum_Optim();
38.     return 0;
39. }
40.
41. void Citire() {
42.     in >> n >> m;
43.     for (int i = 0; i < n; i++)
44.         for (int j = 0; j < m; j++)
45.             in >> matrice[i][j];
46.     in >> startx >> starty;
47.     in >> stopx >> stopy;
48.     in.close();
49. }
50.
51. void Afisare() {
52.     for (int i = 0; i < n; i++) {
53.         for (int j = 0; j < m; j++) {
54.             cout << matrice[i][j] << " ";
55.             out << matrice[i][j] << " ";
56.         }
57.         cout << endl;
58.         out << '\n';
59.     }
60.     out.close();
61. }
62.
63. bool e_ok(int i, int j) {
64.     if (matrice[i][j] == -1)    return false;
65.     if (i < 0 || j < 0 || i >= n || j >= m) return false;
66.     return true;
67. }
68.
69. void agl_Lee() {
70.     int i, j, i_urm, j_urm;
71.     matriceLee[startx][starty] = 1;
77.         for (int d = 0; d < POSIT; d++) {
78.             i_urm = i + di[d];
79.             j_urm = j + dj[d];
80.             if (e_ok(i_urm, j_urm) && matriceLee[i_urm][j_urm] == 0) {
81.                 matriceLee[i_urm][j_urm] = matriceLee[i][j] + 1;
83.             }
84.         }
85.     }
86. }
87.
88. void Drum_Optim() {
89.     int i = stopx, j = stopy;
90.     stiva[k].x = i;
91.     stiva[k].y = j;
92.     k++;
93.     while (matriceLee[i][j] > 1) {
94.         for (int d = 0; d < POSIT; d++) {
95.             int i_urm = i + di[d];
96.             int j_urm = j + dj[d];
97.             if (matriceLee[i_urm][j_urm] == matriceLee[i][j] - 1) {
98.                 stiva[k].x = i;
99.                 stiva[k].y = j;
100.                 k++;
101.                 i = i_urm;
102.                 j = j_urm;
103.                 break;
104.             }
105.         }
106.     }
107.     k--;
108.     while (k >= 0) {
109.         out << stiva[k].x << " " << stiva[k].y << '\n';
110.         k--;
111.     }
112. }
RAW Paste Data