Advertisement
Alex239

Untitled

Oct 11th, 2016
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. #include <vector>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. vector<int> DX = {0, 1, 0, -1};
  7. vector<int> DY = {1, 0, -1, 0};
  8. vector<vector<bool>> g;
  9. vector<vector<bool>> used;
  10. int n, m;
  11.  
  12. bool f(int x, int y)
  13. {
  14.     return x >= 0 && y >= 0 && x < n && y < m;
  15. }
  16.  
  17. void dfs(int x, int y)
  18. {
  19.     if (used[x][y])
  20.         return;
  21.     used[x][y] = true;
  22.     for (int k = 0; k < 4; ++k)
  23.     {
  24.         int x1 = x + DX[k];
  25.         int y1 = y + DY[k];
  26.         if (f(x1, y1) && g[x1][y1])
  27.             dfs(x1, y1);
  28.     }
  29. }
  30.  
  31. int main()
  32. {
  33.     ifstream cin("drains.in");
  34.     ofstream cout("drains.out");
  35.     cin >> n >> m;
  36.     g.assign(n, vector<bool>(m, true));
  37.     used.assign(n, vector<bool>(m));
  38.     vector<vector<int>> h(n, vector<int>(m));
  39.     for (auto& x : h)
  40.         for (auto& y : x)
  41.             cin >> y;
  42.     for (int i = 0; i < n; ++i)
  43.         for (int j = 0; j < m; ++j)
  44.         {
  45.             for (int k = 0; k < 4; ++k)
  46.             {
  47.                 int i1 = i + DX[k];
  48.                 int j1 = j + DY[k];
  49.                 if (f(i1, j1) && h[i1][j1] < h[i][j])
  50.                     g[i][j] = false;
  51.             }
  52.         }
  53.     int cnt = 0;
  54.     for (int i = 0; i < n; ++i)
  55.         for (int j = 0; j < m; ++j)
  56.             if (g[i][j] && !used[i][j])
  57.                 dfs(i, j), ++cnt;
  58.     cout << cnt << endl;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement