2590. Space Exploration

Farmer John’s cows have finally launched from Earth and are now drifting through space aboard their Moocraft. They hope to reach their fellow cows on Io, one of Jupiter’s moons, but to do so they must first pass through a dangerous asteroid belt.

Bessie is piloting the ship through a sector of space of size n * n. The asteroids in this sector are composed of 1 * 1 cells connected by their sides (cells that touch only at a corner are considered part of different asteroids). Help Bessie by counting the number of distinct asteroids in the entire sector.

Consider the 10 * 10 sector shown on the left below. The characters “*” represent parts of asteroids, and each “.” denotes empty space. The right-hand illustration shows an example numbering of the asteroids.

There are 7 asteroids in this sector.

Input. The first line contains the integer n (1 ≤ n ≤ 1000). Starting from the second line, the (i + 1)-th line contains the i-th row of the asteroid field, consisting of n characters.

Output. Print the number of asteroids in the field.

Sample input	Sample output
10 ...**..... .*........ ......*... ...*..*... ..*****... ...*...... ....***... .*..***... .....*...* ..*.......	7

SOLUTION

depth first search

Algorithm analysis

Using depth first search, we count the number of asteroids. This number matches the count of connected components formed by the ‘*’ 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;