ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1033. Лабиринт

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Администрация лабиринта решила начать новый сезон с новыми обоями. Для этого им необходима программа для вычисления площади поверхности стен внутри лабиринта. Эта работа как раз для вас!
Лабиринт представлен матрицей N × N. Некоторые ячейки матрицы содержат символ точки («.»), обозначающий пустую клетку. Другие ячейки содержат символ диеза («#»), обозначающий квадрат, заполненный монолитным блоком каменной стены. Все квадраты имеют одинаковый размер 3 × 3 метра.
Стены построены вокруг лабиринта (за исключением верхнего левого и нижнего правого углов, которые используются как входы) и на ячейках, обозначенных диезом. Других стен нет. В левом верхнем и правом нижнем углу ячеек входной матрицы всегда будет стоять точка.
Problem illustration
Ваша задача – вычислить площадь видимой части стен внутри лабиринта. Иными словами, площадь поверхности стен, которые видны посетителю лабиринта. Обратите внимание, что между любыми двумя соседними блоками стены нет отверстий, через которые можно было бы смотреть или перемещаться. Блоки считаются соседними, если они соприкасаются друг с другом в любом углу. В качестве примера приведен рисунок: видимые стены внутри лабиринта нарисованы жирными линиями. Высота всех стен – 3 метра.

Исходные данные

Первая строка содержит целое число N (3 ≤ N ≤ 33; видите, 3 – это магическая цифра!). Следующие N строк содержат по N символов. Каждая строка описывает одну строку матрицы лабиринта. В каждой строке используются только символы «.» и «#».

Результат

Выведите точное значение необходимой площади обоев.

Пример

исходные данныерезультат
5
.....
...##
..#..
..###
.....
198

Автор задачи: Владимир Пинаев
Источник задачи: III командный студенческий чемпионат Урала по программированию. 1999 г.