Advertisement
Guest User

Untitled

a guest
Sep 6th, 2021
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dx[] = {1, 0, -1, 0};
  5. int dy[] = {0, 1, 0, -1};
  6.  
  7. int n, m;
  8. int vis[1005][1005], a[1005][1005];
  9.  
  10. bool isValid(int x, int y) {
  11.     if(x < 0 || y < 0 || x >= n || y >= m || a[x][y] || vis[x][y])
  12.         return false;
  13.     return true;
  14. }
  15.  
  16. void dfs(int x, int y) {
  17.     if(isValid(x, y)) {
  18.         vis[x][y] = 1;
  19.         for(int i = 0; i < 4; i++) {
  20.             dfs(x + dx[i], y + dy[i]);
  21.         }
  22.     }
  23.     return;    
  24. }
  25.  
  26. int main() {  
  27.     ios::sync_with_stdio(0); cin.tie(0);
  28.     memset(vis, 0, sizeof(vis));
  29.     cin >> n >> m;
  30.     for(int i = 0; i < n; i++) {
  31.         string s;
  32.         cin >> s;
  33.         for(int j = 0; j < s.length(); j++)
  34.             a[i][j] = (s[j] == '#');
  35.     }
  36.     int ans = 0;
  37.     for(int i = 0; i < n; i++) {
  38.         for(int j = 0; j < m; j++) {
  39.             if(a[i][j] == 0 && !vis[i][j]) {
  40.                 dfs(i, j);
  41.                 ans++;
  42.             }
  43.         }
  44.     }
  45.     cout << ans << endl;
  46.     return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement