[UVa] 572 - Oil Deposits

Problem

Link: UVa 572 - Oil Deposits

Hint

DFS

Solution

C++

#include <iostream>

static const int DIRECTIONS[][2] = {{-1, -1}, {0, -1}, {1, -1},
                                    {-1, 0}, /*{0, 0},*/ {1, 0},
                                    {-1, 1}, {0, 1}, {1, 1}};
static bool map[101][101];
static int m, n;

void dfs(int i, int j);

int main()
{
  int i, j;
  int count;
  char row[101];

  std::ios::sync_with_stdio(false);

  while (std::cin >> m >> n && (m || n))
  {
    // input
    for (i = 0; i < m; ++i)
    {
      std::cin >> row;
      // don't judge this, I just want to do this
      for (j = 0; j < n; ++j)
        map[i][j] = row[j] == '@';
    }

    // count
    count = 0;
    for (i = 0; i < m; ++i)
      for (j = 0; j < n; ++j)
        if (map[i][j])
        {
          ++count;
          dfs(i, j);
        }

    std::cout << count << std::endl;
  }

  return 0;
}

void dfs(int i, int j)
{
  int temp_i, temp_j;
  map[i][j] = false;
  for (const auto* p : DIRECTIONS)
  {
    temp_i = i + p[0], temp_j = j + p[1];
    // check boundary
    if (temp_i >= 0 && temp_i < m &&
        temp_j >= 0 && temp_j < n && map[temp_i][temp_j])
      dfs(temp_i, temp_j);
  }
}
Show Comments