printРабочее место участника

printЗадачи

55. Покраска лабиринта

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Лабиринт представляет собой квадрат, состоящий из `N\ times\ N` сегментов. Каждый из сегментов может быть либо пустым, либо заполненным монолитной каменной стеной. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесён сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри (см. рисунок). Помогите ему рассчитать количество краски, необходимой для этого.
Ограничения: `3\ ≤\ N\ ≤\ 33`, размер сегмента `3\ times\ 3` м, высота стен 3 м.
Ввод
В первой строке находится число `N`, затем идут `N` строк по `N` символов: точка обозначает пустой сегмент, решётка – сегмент со стеной.
Вывод
Вывести одно число – площадь видимой части внутренних стен лабиринта в квадратных метрах.

Пример ввода

5
.....
...##
..#..
..###
.....

Пример вывода

198
Источник: Eastern quarterfinal, NEERC, 1999
loading