2590. Исследование космоса

Коровы Фермера Джона наконец стартовали с Земли и теперь летают в своем Мукрафте. Коровы хотят достичь своих любимых родственников на спутнике Юпитера Ио, но для этого они должны сначала перейти через опасный пояс астероидов.

Бесси пилотирует судно через этот предательский n * n сектор пространства. Астероиды в этом секторе представляются квадратами 1 * 1 и представляют собой каменные глыбы, соединенные по краям (два квадрата имеющие только один общий угол считаются двумя различными астероидами). Пожалуйста, помогите Бесси пробраться через это поле путем подсчета количества различных астероидов во всем секторе.

Рассмотрим пространство 10 * 10 внизу слева. Символ ‘*’ указывает на астероид, ‘.’ на пустое пространство. Диаграмма справа указывает на одну из возможных нумераций астероидов.

В указанном секторе присутствуют 7 астероидов.

Вход. Первая строка содержит одно число n (1 ≤ n ≤ 1000). Начиная со второй, (i + 1)-ая строка содержит i-ую строку поля с астероидами: n символов.

Выход. Вывести количество астероидов в поле.

Пример входа	Пример выхода
10 ...**..... .*........ ......*... ...*..*... ..*****... ...*...... ....***... .*..***... .....*...* ..*.......	7

РЕШЕНИЕ

поиск в глубину

Анализ алгоритма

При помощи поиска в глубину подсчитаем количество астероидов. Оно равно количеству связных компонент, задаваемых символами ‘*’.

Пример

Входное поле содержит 7 астероидов.

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

Объявим двумерный символьный массив (массив строк), в котором будем содержать поле с астероидами.

string m[1001];

Поиск в глубину на сетке из точки (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 = 0;

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

if (m[i][j] == '*')

{

dfs(i,j);

c++;

}

Выводим ответ.

cout << c << endl;