API tools faq
paste
Advertisement
Guest User

pb apa

a guest
Jan 17th, 2020
86
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.55 KB | None | 0 0
raw download clone embed print report
  1. /*2.1 Fie o matrice MxN, unde fiecare element reprezinta o altitudine(practic, un plan 3D, cu altitudini discretizate).Se doreste sa se afle cantitatea de apa care va stoca acest plan in urma unei ploi.
  2. Pentru
  3. 2, 2, 2
  4. 2, 1, 2
  5. 2, 2, 2
  6. Se va returna 1
  7.  
  8. Pentru
  9. 3 6
  10. 1 4 3 1 3 2
  11. 3 2 1 3 2 4
  12. 2 3 3 2 3 1
  13. Se va return 4
  14.  
  15. 5 6
  16. 3 5 3 3 3 3
  17. 5 3 5 3 1 1
  18. 5 1 1 1 1 3
  19. 5 1 1 3 3 2
  20. 4 3 4 5 2 3
  21. se va returna 0
  22. */
  23.  
  24. #include <iostream>
  25. #include <fstream>
  26. #include <algorithm>
  27. #define NMAX 6
  28. #define MAX 1000
  29. using namespace std;
  30. struct Coord
  31. {
  32.     int i, j;
  33. };
  34.  
  35. struct Pct
  36. {
  37.     int val;
  38.     int i, j;
  39. };
  40.  
  41. int V[NMAX][NMAX];
  42.  
  43. Coord vMisc[4] = { {-1,0},{0,1},{1,0},{0,-1} };
  44. Coord vPozitie[NMAX*NMAX];
  45. int vVizitat[NMAX][NMAX];
  46.  
  47. void citire(int&, int&);
  48. void afisare(int, int);
  49.  
  50.  
  51. int logica(int, int);
  52.  
  53. //cautare scurgeri din margine si umplerea lor
  54. int DFSmargine(int, int, bool&);
  55. void cautareDinMargineDFS(int, int, int, int, int&, const int&, int&, int&);
  56. void umplereDinMargine(int, int);
  57.  
  58. //umplere goluri centrale si numarare
  59. void NumaraGoluri(int, int, int&, bool&);
  60.  
  61.  
  62.  
  63. //vf
  64. bool interior(int, int, int, int);
  65. bool viz(int, int, int);
  66.  
  67.  
  68. int main()
  69. {
  70.     int n, m;
  71.     int suma = 0;
  72.     citire(n, m);
  73.     afisare(n, m);
  74.  
  75.     suma = logica(n, m);
  76.     cout << "suma: " << suma;
  77.  
  78.     return 0;
  79. }
  80.  
  81.  
  82.  
  83. int logica(int n, int m)
  84. {
  85.     int s = 0;
  86.     //nu mai sunt de numarat goluri
  87.     bool suntGoluri = 1;
  88.     while (suntGoluri)
  89.     {
  90.         suntGoluri = 0;
  91.         DFSmargine(n, m, suntGoluri);
  92.         NumaraGoluri(n, m, s, suntGoluri);
  93.     }
  94.  
  95.     return s;
  96.  
  97. }
  98.  
  99.  
  100. int DFSmargine(int n, int m, bool& suntGoluri)
  101. {
  102.     //umplu marginile cu cel mai mic element mai mare decat cel de la care plec
  103.     //loop pe toata marginea
  104.  
  105.     int i, j;
  106.     int flag;
  107.     int count;
  108.     int min;
  109.     //pct-ul de pe margine de unde intru
  110.     Pct intrareM;
  111.  
  112.     //cate elem am gasit plecand dintr-o margine egale cu elem meu
  113.     for (int j = 0; j < m; j++)
  114.     {
  115.         ///marginea superioara
  116.         i = 0;
  117.         //nr de poz in vect de pozitii
  118.         count = 0;
  119.         //flag daca am intalnit un element mai mic de cat cel din margine
  120.         flag = 1;
  121.         //cautareDinMargineDFS cu minimul gasit
  122.         // minimul
  123.         min = MAX;
  124.         //refac vec de viz
  125.         memset(vVizitat, 0, m*n * sizeof(vVizitat[0][0]));
  126.  
  127.         cautareDinMargineDFS(i, j, n, m, min, V[i][j], count, flag);
  128.         if (flag)
  129.         {
  130.             umplereDinMargine(count, min);
  131.             if (min == MAX)
  132.                 return 1;
  133.             suntGoluri = 1;
  134.             afisare(n, m);
  135.         }
  136.         ///marginea inferioara
  137.         i = n - 1;
  138.         //nr de poz in vect de pozitii
  139.         count = 0;
  140.         //flag daca am intalnit un element mai mic de cat cel din margine
  141.         flag = 1;
  142.         //cautareDinMargineDFS cu minimul gasit
  143.         // minimul
  144.         min = MAX;
  145.         //refac vec de viz
  146.         memset(vVizitat, 0, m*n * sizeof(vVizitat[0][0]));
  147.         cautareDinMargineDFS(i, j, n, m, min, V[i][j], count, flag);
  148.         if (flag)
  149.         {
  150.             umplereDinMargine(count, min);
  151.             if (min == MAX)
  152.                 return 1;
  153.             suntGoluri = 1;
  154.             afisare(n, m);
  155.         }
  156.  
  157.     }
  158.     for (int i = 1; i < n - 1; i++)
  159.     {
  160.  
  161.         ///laterala stanga
  162.         j = 0;
  163.         //nr de poz in vect de pozitii
  164.         count = 0;
  165.         //flag daca am intalnit un element mai mic de cat cel din margine
  166.         flag = 1;
  167.         //cautareDinMargineDFS cu minimul gasit
  168.         // minimul
  169.         min = MAX;
  170.         //refac vec de viz
  171.         memset(vVizitat, 0, m*n * sizeof(vVizitat[0][0]));
  172.         cautareDinMargineDFS(i, j, n, m, min, V[i][j], count, flag);
  173.         if (flag)
  174.         {
  175.             umplereDinMargine(count, min);
  176.             if (min == MAX)
  177.                 return 1;
  178.             suntGoluri = 1;
  179.             afisare(n, m);
  180.         }
  181.  
  182.         ///laterala dreapta
  183.         j = m - 1;
  184.         //nr de poz in vect de pozitii
  185.         count = 0;
  186.         //flag daca am intalnit un element mai mic de cat cel din margine
  187.         flag = 1;
  188.         //cautareDinMargineDFS cu minimul gasit
  189.         // minimul
  190.         min = MAX;
  191.         //refac vec de viz
  192.         memset(vVizitat, 0, m*n * sizeof(vVizitat[0][0]));
  193.         cautareDinMargineDFS(i, j, n, m, min, V[i][j], count, flag);
  194.         if (flag)
  195.         {
  196.             umplereDinMargine(count, min);
  197.             if (min == MAX)
  198.                 break;
  199.             suntGoluri = 1;
  200.             afisare(n, m);
  201.         }
  202.     }
  203.  
  204.     return 1;
  205. }
  206.  
  207. void cautareDinMargineDFS(int i, int j, int n, int m, int &min, const int& intrareVal, int& count, int& flag)
  208. {
  209.  
  210.     if (flag == 0)
  211.         return;
  212.  
  213.     if (interior(i, j, n, m) && !viz(i, j, count))
  214.         vVizitat[i][j] = 1;
  215.     else
  216.         return;
  217.     //daca gasesc un minim mai mic decat elem initial ma intorc
  218.     if (V[i][j] < intrareVal)
  219.     {
  220.         count = 0;
  221.         flag = 0;
  222.         return;
  223.     }
  224.     //daca e un elem mai mare decat cel de intrare
  225.     //si mai mic decat min updatez minimul
  226.     if (V[i][j] > intrareVal && V[i][j] < min)
  227.         min = V[i][j];
  228.  
  229.     //daca este un element egal cu cel initial merg mai departe
  230.     if (V[i][j] == intrareVal)
  231.     {
  232.         //il bag in vect de poz pt o umplere ulterioara
  233.         vPozitie[count] = { i,j };
  234.         //maresc count
  235.         count++;
  236.         //caut si in celelalte directii
  237.         for (int dir = 0; dir < 4; dir++)
  238.         {
  239.             if (interior(i + vMisc[dir].i, j + vMisc[dir].j, n, m))
  240.             {
  241.                 if (flag == 0)
  242.                     return;
  243.                 cautareDinMargineDFS(i + vMisc[dir].i, j + vMisc[dir].j, n, m, min, intrareVal, count, flag);
  244.             }
  245.         }
  246.     }
  247. }
  248.  
  249. void NumaraGoluri(int n, int m, int& s, bool& suntGoluri)
  250. {
  251.     //aflu minim
  252.     int minim = MAX;
  253.     int maxim = -1;
  254.     int i, j;
  255.     for (j = 0; j < m; j++)
  256.     {
  257.         i = 0;
  258.         if (V[i][j] < minim)
  259.             minim = V[i][j];
  260.         if (V[i][j] > maxim)
  261.             maxim = V[i][j];
  262.         i = n - 1;
  263.         if (V[i][j] < minim)
  264.             minim = V[i][j];
  265.         if (V[i][j] > maxim)
  266.             maxim = V[i][j];
  267.     }
  268.     for (int i = 1; i < n - 1; i++)
  269.     {
  270.         j = 0;
  271.         if (V[i][j] < minim)
  272.             minim = V[i][j];
  273.         if (V[i][j] > maxim)
  274.             maxim = V[i][j];
  275.         j = m - 1;
  276.         if (V[i][j] < minim)
  277.             minim = V[i][j];
  278.         if (V[i][j] > maxim)
  279.             maxim = V[i][j];
  280.     }
  281.  
  282.     if (maxim - minim == 0)
  283.         suntGoluri = 0;
  284.  
  285.     for (int i = 0; i < n; i++)
  286.         for (int j = 0; j < m; j++)
  287.         {
  288.             if (V[i][j] < minim)
  289.             {
  290.                 //adaug golul la suma
  291.                 s += minim - V[i][j];
  292.                 //umplu golul
  293.                 V[i][j] = minim;
  294.             }
  295.         }
  296. }
  297.  
  298. void umplereDinMargine(int count, int min)
  299. {
  300.     for (int k = 0; k < count; k++)
  301.     {
  302.         V[vPozitie[k].i][vPozitie[k].j] = min;
  303.  
  304.     }
  305. }
  306.  
  307. //check interior
  308. bool interior(int i, int j, int n, int m)
  309. {
  310.     return (i >= 0 && i < n &&j >= 0 && j < m);
  311.  
  312. }
  313.  
  314. //check anterior vizitat
  315. bool viz(int i, int j, int count)
  316. {
  317.     for (int k = 0; k < count; k++)
  318.     {
  319.         if (vVizitat[i][j] == 1)
  320.             return true;
  321.     }
  322.     return false;
  323. }
  324.  
  325. void citire(int&n, int&m)
  326. {
  327.     ifstream fin("SD.in");
  328.     fin >> n >> m;
  329.     for (int i = 0; i < n; i++)
  330.         for (int j = 0; j < m; j++)
  331.             fin >> V[i][j];
  332.     fin.close();
  333. }
  334.  
  335.  
  336. void afisare(int n, int m)
  337. {
  338.     for (int i = 0; i < n; i++)
  339.     {
  340.         for (int j = 0; j < m; j++)
  341.             cout << V[i][j] << "  ";
  342.         cout << endl;
  343.     }
  344.     cout << endl;
  345. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!