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

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

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

Рассмотрим сектор 10 * 10, изображённый ниже слева. Символы ‘*’ обозначают части астероидов, а каждый символ ‘.’ соответствует пустому пространству. На правом рисунке показан пример нумерации астероидов.

В этом секторе 7 астероидов.

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

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

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

РЕШЕНИЕ

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

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

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

Пример

Входное поле содержит 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;