Островки грязи в школьном коридоре

После перемены дежурные нарисовали план коридора в клетку. Чистые клетки отмечены точкой, а клетки, где остались следы грязи, — решёткой.

Два грязных следа считаются частью одного «островка грязи», если из одного можно дойти до другого, переходя только по грязным клеткам вверх/вниз/влево/вправо.

Нужно узнать, сколько островков грязи получилось.

Формат ввода

В первой строке два целых числа m и n — размеры плана (m строк и n столбцов). Далее идут m строк по n символов: . или #.

Формат вывода

Выведите одно целое число — количество островков грязи.

Ограничения

• 1 ≤ m ≤ 80
• 1 ≤ n ≤ 80

Пример

Ввод:

4 7
..##...
..##..#
....###
#......

Вывод:

3

Ключевое наблюдение: грязные клетки образуют группы, где из любой # можно дойти до любой другой по шагам вверх/вниз/влево/вправо. Каждая такая группа — связная компонента на решётке. Если мы один раз нашли клетку #, то можем обойти все клетки её островка и пометить их как посещённые. Тогда при дальнейшем просмотре поля этот островок больше не увеличит ответ.

Почему работает BFS/DFS: это стандартный способ «заливки» области, где из клетки можно переходить в соседние клетки по правилам задачи. Мы гарантированно посетим ровно те клетки, которые принадлежат текущему островку.

План решения:

• Считай m, n и саму сетку.
• Заведи массив used[m][n] = False.
• Пройди по всем клеткам.
• Если встретил # и она ещё не used, то:
• увеличь счётчик островков на 1;
• запусти BFS (очередь) или DFS (стек) из этой клетки;
• в обходе для каждой клетки пробуй 4 направления и добавляй соседа, если он внутри поля, равен # и ещё не посещён.

Мини-сниппет для соседей: for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]: ....

Сложность: каждая клетка попадает в обход не более одного раза, поэтому время O(m*n), память O(m*n) на used (и очередь/стек).

Частая ошибка: считать диагонали соседними (нельзя) или забыть поставить used в момент добавления в очередь — тогда одну и ту же клетку можно добавить много раз.