Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <cmath>
- #include <cstring>
- #include <iostream>
- #include <queue>
- #include <stack>
- #include <vector>
- #define DEBUG 1
- const int MAXD = 100;
- const int MAXN = MAXD * MAXD;
- using namespace std;
- int heights[MAXD][MAXD];
- bool adjGraph[MAXN][MAXN];
- int w, h;
- int n;
- int dx[] = { 0, 1, 0, -1 };
- int dy[] = { 1, 0, -1, 0 };
- int toOne(int x, int y)
- {
- return y * w + x;
- }
- int oneToX(int o)
- {
- return o % w;
- }
- int oneToY(int o)
- {
- return o / w;
- }
- void generateAdj()
- {
- for (int y1 = 0; y1 < h; ++y1)
- {
- for (int x1 = 0; x1 < w; ++x1)
- {
- for (int i = 0; i < 4; ++i)
- {
- int x2 = x1 + dx[i];
- int y2 = y1 + dy[i];
- if (x2 < 0 || y2 < 0 || x2 >= w || y2 >= h)
- continue;
- adjGraph[toOne(x1, y1)][toOne(x2, y2)] = heights[y1][x1] >= heights[y2][x2];
- }
- }
- }
- }
- vector< int > dfs(int u, bool visited[])
- {
- visited[u] = true;
- vector< int > reachable = { u };
- for (int v = 0; v < n; v++)
- {
- if (adjGraph[u][v] && !visited[v])
- {
- vector< int > sub_reachable = dfs(v, visited);
- reachable.insert(reachable.end(), sub_reachable.begin(), sub_reachable.end());
- }
- }
- return reachable;
- }
- vector< int > get_reachable_vertices(int target)
- {
- bool visited[MAXN] = { false };
- vector< int > reachable = dfs(target, visited);
- queue< int > q;
- for (int u : reachable)
- {
- visited[u] = true;
- q.push(u);
- }
- while (!q.empty())
- {
- int u = q.front();
- q.pop();
- for (int v = 0; v < n; v++)
- {
- if (adjGraph[v][u] && !visited[v])
- {
- visited[v] = true;
- q.push(v);
- }
- }
- }
- vector< int > result;
- for (int u = 0; u < n; u++)
- {
- if (visited[u])
- {
- result.push_back(u);
- }
- }
- return result;
- }
- bool isElementInVector(std::vector< int >& vec, int elem)
- {
- for (int i = 0; i < vec.size(); i++)
- {
- if (vec[i] == elem)
- {
- return true;
- }
- }
- return false;
- }
- int main()
- {
- cin >> h >> w;
- n = w * h;
- if (n == 1)
- {
- cout << 1;
- exit(0);
- }
- for (int i = 0; i < h; ++i)
- {
- for (int j = 0; j < w; ++j)
- {
- cin >> heights[i][j];
- }
- }
- #ifdef DEBUG
- cout << "w:" << w << ", h:" << h << "\n";
- for (int y = 0; y < h; ++y)
- {
- for (int x = 0; x < w; ++x)
- {
- int o = toOne(x, y);
- if (oneToX(o) != x || oneToY(o) != y)
- {
- cout << "ABOBA" << x << ", " << y;
- }
- }
- }
- for (int y = 0; y < h; ++y)
- {
- for (int x = 0; x < w; ++x)
- {
- cout << heights[y][x] << " ";
- }
- cout << "\n";
- }
- #endif
- generateAdj();
- #ifdef DEBUG
- for (int y1 = 0; y1 < h; ++y1)
- {
- for (int x1 = 0; x1 < w; ++x1)
- {
- for (int y2 = 0; y2 < h; ++y2)
- {
- for (int x2 = 0; x2 < w; ++x2)
- {
- if (adjGraph[toOne(x1, y1)][toOne(x2, y2)])
- {
- cout << x1 << "," << y1 << " -> " << x2 << "," << y2 << " "
- << "\n";
- }
- }
- }
- }
- }
- #endif
- vector< int > reachable;
- int count = 0;
- for (int i = 0; i < n; ++i)
- {
- if (!isElementInVector(reachable, i))
- {
- count++;
- vector< int > reachable2 = get_reachable_vertices(i);
- // Output the result
- #ifdef DEBUG
- cout << "aaaa(" << oneToX(i) << ", " << oneToY(i) << "), ";
- cout << "Vertices that can reach all other vertices: ";
- for (int j : reachable2)
- {
- if (!isElementInVector(reachable, j))
- {
- cout << "(" << oneToX(j) << ", " << oneToY(j) << "), ";
- }
- }
- cout << endl;
- #endif
- reachable.insert(reachable.end(), reachable2.begin(), reachable2.end());
- }
- }
- cout << count;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement