Дослідження космосу (Розбір)

За допомогою пошуку в глибину підрахуємо кількість астероїдів. Вона збігається з числом зв'язних компонент, утворених символами '$\ast$'.

Приклад

Вхідне поле містить $7$ астероїдів.

Реалізація алгоритму

Оголосимо двовимірний символьний масив (масив рядків), у якому зберігатиметься поле з астероїдами.

string m[1001];

Функція dfs виконує пошук у глибину на сітці, починаючи з клітинки $(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);
}

Основна частина програми. Зчитуємо вхідні дані.

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

У змінній $c$ підраховуємо кількість астероїдів.

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

Виводимо відповідь.

cout << c << endl;