Ankit_132

C

Oct 21st, 2023
223
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int n, m;
  8.     cin>>n>>m;
  9.  
  10.     vector<string> s(n);
  11.     for(auto &e: s)   cin>>e;
  12.  
  13.     vector<vector<int>> vis(n, vector<int> (m, 0));
  14.     int x[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
  15.     int y[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
  16.  
  17.     function<void(int, int)> DFS = [&](int i, int j)
  18.     {
  19.         vis[i][j] = 1;
  20.  
  21.         for(int d=0; d<8; d++)
  22.         {
  23.             if(i+x[d]>=0 && i+x[d]<n && j+y[d]>=0 && j+y[d]<m && !vis[i+x[d]][j+y[d]] && s[i+x[d]][j+y[d]]=='#')
  24.                 DFS(i+x[d], j+y[d]);
  25.         }
  26.     };
  27.  
  28.     int ans = 0;
  29.  
  30.     for(int i=0; i<n; i++)
  31.     {
  32.         for(int j=0; j<m; j++)
  33.         {
  34.             if(!vis[i][j] && s[i][j]=='#')
  35.             {
  36.                 ans++;
  37.                 DFS(i, j);
  38.             }
  39.         }
  40.     }
  41.  
  42.     cout<<ans<<"\n";
  43. }
  44.  
Advertisement
Add Comment
Please, Sign In to add comment