Олимпиадный тренинг

Задача . Камеры замка Иф


Задача

Темы:
В замке Иф стало не хватать камер для узников. В качестве камер было решено использовать пещеры в скале. Но вот незадача - некторые пещеры могут быть соединены между собой сложными ходами. А нужно, чтобы каждая камера была изолирована от других частью скалы. У коменданта замка Бертье имеется план скалы в виде прямоугольного фрагмента бумаги, разбитого на клеточки, в котором отмечены клеточки-пустоты (это будут камеры) и клеточки-скальная порода (это будут стены камер). Пустая клеточка на карте обозначена точкой, клетка-стена обозначена звездочкой. Прежде, чем использовать эти пещеры в качестве камер, комендант Бертье хочет посчитать, а сколько всего новых камер может получиться. Ваша задача - по имеющейся карте, которую Бертье любезно готов Вам предоставить, посчитать количество пещер в скале, которые станут камерами для узников. Постарайтесь сделать это быстро и правильно, иначе Вы рискуете оказаться в одной из них.

Входные данные
В первой строке  вводятся числа N и M – размеры лабиринта в скале (3 <= N, М <= 10). В следующих N строках задан план пещер скалы (‘.’ – пустота, ‘*’ – скальная порода). Гарантируется, что по периметру плана со всех сторон.стоят * и ни в одной из пещер нет выхода из скалы.

Выходные данные
Требуется вывести единственное число – количество отдельных камер, т.е. таких пещер, которые со всех сторон окружены скальной породой. Две клетки, обозначающие пустоты в скале считаются относящимися к одной и той же пещере, если они имеют общую сторону.
Примеры
Входные данныеВыходные данные
1
5 5
*****
**..*
*.*.*
*..**
*****
2

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python2
Комментарий учителя