Advertisement
cosenza987

Untitled

Jul 4th, 2021
1,424
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int arr[1010][1010];
  6. pair<int, int> pp;
  7. set<pair<int, int>> spots;
  8.  
  9. void remover(int i, int j) {
  10.     pp = make_pair(i, j);
  11.     spots.erase(pp);
  12.     arr[i][j] = 0;
  13.     if(arr[i - 1][j] == 1 and i - 1 >= 0) {
  14.         remover(i - 1, j);
  15.     }
  16.     if(arr[i + 1][j] == 1) {
  17.         remover(i + 1, j);
  18.     }
  19.     if(arr[i][j + 1] == 1) {
  20.         remover(i, j + 1);
  21.     }
  22.     if(arr[i][j - 1] == 1 and j - 1 >= 0) {
  23.         remover(i, j - 1);
  24.     }
  25.     return;
  26. }
  27.  
  28. int main() {
  29.     ios_base::sync_with_stdio(false);
  30.     cin.tie(0);
  31.     int n, m;
  32.     cin >> n >> m;
  33.     for(int i = 0; i < n; i++) {
  34.         for(int j = 0; j < m; j++) {
  35.             cin >> arr[i][j];
  36.             if(arr[i][j] == 1) {
  37.                 pp = make_pair(i, j);
  38.                 spots.insert(pp);
  39.             }
  40.         }
  41.     }
  42.     long long ans = 0;
  43.     //cout << spots.size() << "\n";
  44.     while(spots.size() != 0) {
  45.         auto itr = spots.begin();
  46.         pp = *itr;
  47.         remover(pp.first, pp.second);
  48.         //cout << pp.first << " " << pp.second << "\n";
  49.         ans++;
  50.     }
  51.     cout << ans << "\n";
  52.     return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement