UVA 572 - Oil Deposits Solution

 

Problem Link:    572 - Oil Deposits

Solution in C++:

/// La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

/// Abul Hasnat  Tonmoy

/// Department of CSE,23rd batch

/// Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include <bits/stdc++.h>

using namespace std;

const int N = 101;

vector<string> vs;

string s;

int m, n, cnt = 0;

bool visited[N][N];

int di[] = {0, -1, -1, -1, 0, 1, 1, 1, 0};

int dj[] = {-1, -1, 0, 1, 1, 1, 0, -1, -1};

void dfs(int a, int b) {

  visited[a][b] = 1;

  for (int i = 0; i < 8; i++) {

    int x = di[i] + a;

    int y = dj[i] + b;

    if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y]) {

      visited[x][y] = 1;

      if (vs[x][y] == '@') dfs(x, y);

    }

  }

}

int main() {

  ios_base::sync_with_stdio(0);

  cin.tie(0);

  while (1) {

    vs.clear();

    cin >> m >> n;

    if (m == 0) break;

    for (int i = 0; i < m; i++) {

      cin >> s;

      vs.push_back(s);

    }

    memset(visited, 0, sizeof visited);

    cnt = 0;

    for (int i = 0; i < m; i++) {

      for (int j = 0; j < n; j++) {

        if (!visited[i][j]) {

          visited[i][j] == 1;

          if (vs[i][j] == '@') {

            cnt++;

            dfs(i, j);

          }

        }

      }

    }

    cout << cnt << endl;

  }

}