EduBrick

Поле как граф

6000 мс · 256 МБ · всё или ничего

Дано поле из точек и решёток: точка — проходимая клетка, решётка — стена.

Построим граф: вершины — проходимые клетки, ребро соединяет две клетки, если они соседние по стороне. Сколько в этом графе вершин и рёбер?

Формат ввода

В первой строке числа nn и mm от 11 до 500500. В следующих nn строках по mm символов — точки и решётки.

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

Два числа через пробел: количество вершин и рёбер.

Примеры

ввод
2 2
..
..
вывод
4 4

Примечание

Строить сам список смежности не нужно — вопрос только о количестве. Чтобы не посчитать каждое ребро дважды, смотрите у каждой клетки только двух соседей: справа и снизу.

Войдите, чтобы отправлять решения.