Advertisement
Derga

Untitled

Aug 24th, 2023
829
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.48 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <queue>
  6. #include <stack>
  7. #include <vector>
  8.  
  9. #define DEBUG 1
  10.  
  11. const int MAXD = 100;
  12. const int MAXN = MAXD * MAXD;
  13. using namespace std;
  14. int heights[MAXD][MAXD];
  15. bool adjGraph[MAXN][MAXN];
  16. int w, h;
  17. int n;
  18.  
  19. int dx[] = { 0, 1, 0, -1 };
  20. int dy[] = { 1, 0, -1, 0 };
  21.  
  22. int toOne(int x, int y)
  23. {
  24.     return y * w + x;
  25. }
  26.  
  27. int oneToX(int o)
  28. {
  29.     return o % w;
  30. }
  31. int oneToY(int o)
  32. {
  33.     return o / w;
  34. }
  35.  
  36. void generateAdj()
  37. {
  38.     for (int y1 = 0; y1 < h; ++y1)
  39.     {
  40.         for (int x1 = 0; x1 < w; ++x1)
  41.         {
  42.             for (int i = 0; i < 4; ++i)
  43.             {
  44.                 int x2 = x1 + dx[i];
  45.                 int y2 = y1 + dy[i];
  46.                 if (x2 < 0 || y2 < 0 || x2 >= w || y2 >= h)
  47.                     continue;
  48.                 adjGraph[toOne(x1, y1)][toOne(x2, y2)] = heights[y1][x1] >= heights[y2][x2];
  49.             }
  50.         }
  51.     }
  52. }
  53. vector< int > dfs(int u, bool visited[])
  54. {
  55.     visited[u] = true;
  56.     vector< int > reachable = { u };
  57.     for (int v = 0; v < n; v++)
  58.     {
  59.         if (adjGraph[u][v] && !visited[v])
  60.         {
  61.             vector< int > sub_reachable = dfs(v, visited);
  62.             reachable.insert(reachable.end(), sub_reachable.begin(), sub_reachable.end());
  63.         }
  64.     }
  65.     return reachable;
  66. }
  67.  
  68. vector< int > get_reachable_vertices(int target)
  69. {
  70.     bool visited[MAXN] = { false };
  71.     vector< int > reachable = dfs(target, visited);
  72.     queue< int > q;
  73.     for (int u : reachable)
  74.     {
  75.         visited[u] = true;
  76.         q.push(u);
  77.     }
  78.     while (!q.empty())
  79.     {
  80.         int u = q.front();
  81.         q.pop();
  82.         for (int v = 0; v < n; v++)
  83.         {
  84.             if (adjGraph[v][u] && !visited[v])
  85.             {
  86.                 visited[v] = true;
  87.                 q.push(v);
  88.             }
  89.         }
  90.     }
  91.     vector< int > result;
  92.     for (int u = 0; u < n; u++)
  93.     {
  94.         if (visited[u])
  95.         {
  96.             result.push_back(u);
  97.         }
  98.     }
  99.     return result;
  100. }
  101. bool isElementInVector(std::vector< int >& vec, int elem)
  102. {
  103.     for (int i = 0; i < vec.size(); i++)
  104.     {
  105.         if (vec[i] == elem)
  106.         {
  107.             return true;
  108.         }
  109.     }
  110.     return false;
  111. }
  112.  
  113. int main()
  114. {
  115.     cin >> h >> w;
  116.     n = w * h;
  117.     if (n == 1)
  118.     {
  119.         cout << 1;
  120.         exit(0);
  121.     }
  122.     for (int i = 0; i < h; ++i)
  123.     {
  124.         for (int j = 0; j < w; ++j)
  125.         {
  126.             cin >> heights[i][j];
  127.         }
  128.     }
  129. #ifdef DEBUG
  130.     cout << "w:" << w << ", h:" << h << "\n";
  131.     for (int y = 0; y < h; ++y)
  132.     {
  133.         for (int x = 0; x < w; ++x)
  134.         {
  135.             int o = toOne(x, y);
  136.             if (oneToX(o) != x || oneToY(o) != y)
  137.             {
  138.                 cout << "ABOBA" << x << ", " << y;
  139.             }
  140.         }
  141.     }
  142.     for (int y = 0; y < h; ++y)
  143.     {
  144.         for (int x = 0; x < w; ++x)
  145.         {
  146.             cout << heights[y][x] << " ";
  147.         }
  148.         cout << "\n";
  149.     }
  150. #endif
  151.     generateAdj();
  152.  
  153. #ifdef DEBUG
  154.     for (int y1 = 0; y1 < h; ++y1)
  155.     {
  156.         for (int x1 = 0; x1 < w; ++x1)
  157.         {
  158.             for (int y2 = 0; y2 < h; ++y2)
  159.             {
  160.                 for (int x2 = 0; x2 < w; ++x2)
  161.                 {
  162.                     if (adjGraph[toOne(x1, y1)][toOne(x2, y2)])
  163.                     {
  164.                         cout << x1 << "," << y1 << " -> " << x2 << "," << y2 << " "
  165.                              << "\n";
  166.                     }
  167.                 }
  168.             }
  169.         }
  170.     }
  171. #endif
  172.     vector< int > reachable;
  173.     int count = 0;
  174.     for (int i = 0; i < n; ++i)
  175.     {
  176.         if (!isElementInVector(reachable, i))
  177.         {
  178.             count++;
  179.             vector< int > reachable2 = get_reachable_vertices(i);
  180.             // Output the result
  181. #ifdef DEBUG
  182.             cout << "aaaa(" << oneToX(i) << ", " << oneToY(i) << "), ";
  183.             cout << "Vertices that can reach all other vertices: ";
  184.             for (int j : reachable2)
  185.             {
  186.                 if (!isElementInVector(reachable, j))
  187.                 {
  188.                     cout << "(" << oneToX(j) << ", " << oneToY(j) << "), ";
  189.                 }
  190.             }
  191.             cout << endl;
  192. #endif
  193.             reachable.insert(reachable.end(), reachable2.begin(), reachable2.end());
  194.         }
  195.     }
  196.     cout << count;
  197.     return 0;
  198. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement