Kosmos tədqiqatı (Həll təhlili)

Dərinliyinə axtarış (DFS) istifadə edərək asteroidlərin sayını hesablayaq. Bu say '$\ast$' simvollarından əmələ gələn əlaqəli komponentlərin sayına bərabərdir.

Nümunə

Giriş sahəsi $7$ asteroid saxlayır.

Alqoritmin realizasiyası

Asteroidlər olan sahənin saxlanılacağı ikiölçülü simvol massivi (sətirlər massivi) elan edək.

string m[1001];

dfs funksiyası $(i,j)$ xanasından başlayaraq şəbəkə üzərində dərinliyinə axtarış həyata keçirir.

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);
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

$c$ dəyişənində asteroidlərin sayını hesablayırıq.

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

Cavabı çıxarırıq.

cout << c << endl;