Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <fstream>
- using namespace std;
- vector<int> DX = {0, 1, 0, -1};
- vector<int> DY = {1, 0, -1, 0};
- vector<vector<bool>> g;
- vector<vector<bool>> used;
- int n, m;
- bool f(int x, int y)
- {
- return x >= 0 && y >= 0 && x < n && y < m;
- }
- void dfs(int x, int y)
- {
- if (used[x][y])
- return;
- used[x][y] = true;
- for (int k = 0; k < 4; ++k)
- {
- int x1 = x + DX[k];
- int y1 = y + DY[k];
- if (f(x1, y1) && g[x1][y1])
- dfs(x1, y1);
- }
- }
- int main()
- {
- ifstream cin("drains.in");
- ofstream cout("drains.out");
- cin >> n >> m;
- g.assign(n, vector<bool>(m, true));
- used.assign(n, vector<bool>(m));
- vector<vector<int>> h(n, vector<int>(m));
- for (auto& x : h)
- for (auto& y : x)
- cin >> y;
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < m; ++j)
- {
- for (int k = 0; k < 4; ++k)
- {
- int i1 = i + DX[k];
- int j1 = j + DY[k];
- if (f(i1, j1) && h[i1][j1] < h[i][j])
- g[i][j] = false;
- }
- }
- int cnt = 0;
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < m; ++j)
- if (g[i][j] && !used[i][j])
- dfs(i, j), ++cnt;
- cout << cnt << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement