achulkov2

Untitled

Apr 12th, 2018
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.10 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. vector<vector<int>> field;
  7. vector<vector<bool>> used;
  8. int n, m;
  9.  
  10. bool ok(int x, int y) {
  11. return (0 <= x && x < n && 0 <= y && y < m);
  12. }
  13.  
  14. vector<pair<int, int>> steps{{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
  15.  
  16. bool dfs(int x, int y) {
  17. used[x][y] = true;
  18. bool res = true;
  19. for (const auto& step :steps) {
  20. int nx = x + step.first, ny = y + step.second;
  21. if (ok(nx, ny)) {
  22. if (field[nx][ny] < field[x][y]) {
  23. res = false;
  24. } else if (!used[nx][ny] && field[nx][ny] == field[x][y]) {
  25. res = (dfs(nx, ny) && res);
  26. }
  27. }
  28. }
  29. return res;
  30. }
  31.  
  32. int main() {
  33. cin >> n >> m;
  34. field.assign(n, vector<int>(m));
  35. for (auto& row : field) {
  36. for (auto& elem : row) cin >> elem;
  37. }
  38. used.assign(n, vector<bool>(m, false));
  39. int cnt = 0;
  40. for (int i = 0; i < n; ++i) {
  41. for (int j = 0; j < m; ++j) {
  42. if (!used[i][j] && dfs(i, j)) ++cnt;
  43. }
  44. }
  45. cout << cnt << "\n";
  46. return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment