MiinaMagdy

572 - Oil Deposits

Mar 13th, 2023
756
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define all(x) x.begin(), x.end()
  7. #define sz(x) int(x.size())
  8. #define endl '\n'
  9.  
  10. int n, m;
  11.  
  12. void solve() {
  13.     int ans = 0;
  14.     vector<vector<char>> grid(n, vector<char>(m));
  15.     for (int i = 0; i < n; i++) {
  16.         for (int j = 0; j < m; j++) {
  17.             cin >> grid[i][j];
  18.         }
  19.     }
  20.     vector<vector<bool>> vis(n, vector<bool>(m));
  21.     auto valid = [&](int i, int j) {
  22.         return 0 <= i && i < n && 0 <= j && j < m && !vis[i][j] && grid[i][j] == '@';
  23.     };
  24.     function<void(int , int )> dfs = [&](int i, int j) {
  25.         for (int di = -1; di < 2; di++) {
  26.             for (int dj = -1; dj < 2; dj++) {
  27.                 if (!di && !dj) continue;
  28.                 int ni = di + i, nj = dj + j;
  29.                 if (valid(ni, nj)) {
  30.                     vis[ni][nj] = true;
  31.                     dfs(ni, nj);
  32.                 }
  33.             }
  34.         }
  35.     };
  36.     for (int i = 0; i < n; i++) {
  37.         for (int j = 0; j < m; j++) {
  38.             if (grid[i][j] == '@' && !vis[i][j]) {
  39.                 vis[i][j] = true;
  40.                 ans++;
  41.                 dfs(i, j);
  42.             }
  43.         }
  44.     }
  45.     cout << ans << endl;
  46. }
  47.  
  48. int main() {
  49.     cin.tie(0), cin.sync_with_stdio(0);
  50.     while (cin >> n >> m, n && m)
  51.         solve();
  52. }
  53.  
Tags: C++ UVA
Advertisement
Add Comment
Please, Sign In to add comment