Space Exploration (Editorial)

Using depth first search, we count the number of asteroids. This number matches the count of connected components formed by the '$\ast$' characters.

Example

The input field contains $7$ asteroids.

Algorithm implementation

Declare a two-dimensional character array (an array of strings) to store the field with asteroids.

string m[1001];

The dfs function performs a depth-first search on the grid, starting from the cell $(i,j)$.

void dfs(int i, int j)
{
  if ((i < 0) || (i >= n) || (j < 0) || (j >= n)) return;

  if (m[i][j] == '.') return;
  m[i][j] = '.';

  dfs(i-1,j); dfs(i+1,j);
  dfs(i,j-1); dfs(i,j+1);
}

The main part of the program. Read the input data.

cin >> n;
for (i = 0; i < n; i++)
  cin >> m[i];

In the variable $c$ we count the number of asteroids.

c = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
  if (m[i][j] == '*') 
  {
    dfs(i,j);
    c++;
  }

Print the answer.

cout << c << endl;