Esplorazione dello spazio (Editoriale)

Utilizzando la ricerca in profondità (DFS) contiamo il numero di asteroidi. Esso coincide con il numero di componenti connesse formate dai simboli '$\ast$'.

Esempio

Il campo in input contiene $7$ asteroidi.

Implementazione dell'algoritmo

Dichiariamo un array bidimensionale di caratteri (array di stringhe), in cui verrà memorizzato il campo con gli asteroidi.

string m[1001];

La funzione dfs esegue la ricerca in profondità sulla griglia, a partire dalla cella $(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);
}

Parte principale del programma. Leggiamo i dati in input.

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

Nella variabile $c$ contiamo il numero di asteroidi.

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

Stampiamo la risposta.

cout << c << endl;