Задача M. Число комнат в лабиринте ≡

Условие

Карта лабиринта, выступающего в качестве игрового поля, представлена в виде матрицы n × m клеток. Каждая клетка маркируется одним из двух значений: свободное пространство либо непроходимый участок. Полагается, что в процессе игры персонаж может передвигаться в одном из четырех направлений: вверх, вниз, вправо и влево, всегда при этом оставаясь в свободных клетках.

В лабиринте также могут встречаться закрытые комнаты, переходы между которыми остаются для персонажа недоступными. Иначе говоря, находясь в одной из таких комнат, персонаж не сможет переместиться в любую другую стандартным для него способом.

Для некоторого заданного лабиринта требуется определить общее число закрытых комнат.

Формат входного файла

Во входном файле "input.txt" построчно хранится двумерный массив символов, представляющий собой карту лабиринта. Свободные клетки в нем обозначаются пробелами (ASCII 32), в то время как все остальные выступают в качестве непроходимых участков.

Формат выходного файла

Выходной файл "output.txt" должен содержать полученное число комнат.

Ограничения

0 < (n, m) ≤ 5000

Примеры тестов

xxxxxxxxx    xxx xx xxxxxxxxxxxx
xxxxxxxxx    xxx xx xxxxxxxxxxxx
xxxxxxxxx    xxx                
xxxxxxxxx    xxxxxxxxx   xxxxxxx
xxx          xxxxxxxxx   xxxxxxx
xxx   xxx    xxxxxxxxx          
xxx          xxxxxxxxx          
xxxxxx  xxx  xxxxxxxxx   xxxxxxx
xxxxxx  xxx  xxxxxxxxx   xxxxxxx
xxxxxx                   xxxxxxx
xxxxxxxxxxxxx            xxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

1

xxx   xxx       xxxx  0000000000
xxx   xxx   xx  xxxx  0000000000
xxx   xxx   xx                  
xxxxxxxxx   xxxxxxxx  aaa    iii
            xxxxxxxx  aaa       
xxx   xxx   xxaa    aa    000iii
              aa    aa    000iii
iiiiii   aaa  aaaaaaaa    000iii
iiiiii   aaa  aaaaaaaa    000iii
000iii                          
000000   000  00000000    000000
000000   0000000000000    000000

3