Mentosan

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;
  72.     Coada.push(make_pair(startx, starty));
  73.     while (!Coada.empty()) {
  74.         i = Coada.front().first;
  75.         j = Coada.front().second;
  76.         Coada.pop();
  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;
  82.                 Coada.push(make_pair(i_urm, j_urm));
  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