НачалоПодразделы
Другие разделы
Дата и время
16/11/2024 23:20:52
Занятие 10
A. Удаление клеток B. Покраска лабиринта C. Ближайшее число D. Путь спелеолога E. Круглая задача F. Город-лабиринт
B. Покраска лабиринта
Поиск в глубину (DFS)Олимпиадные задачи на русском языке
| 03/07/2006 | Лето 2006 дорешивание ( 5F) |
| 12/07/2006 | Лето 2006 - 5 (F) |
| 14/11/2007 | Занятие 10 (B) |
| 10/12/2013 | Занятие 11 для начинающих (B) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Лабиринт представляет собой квадрат, состоящий из `N\ times\ N` сегментов. Каждый из сегментов может быть либо пустым, либо заполненным монолитной каменной стеной. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесён сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри (см. рисунок). Помогите ему рассчитать количество краски, необходимой для этого.
Ограничения: `3\ ≤\ N\ ≤\ 33`, размер сегмента `3\ times\ 3` м, высота стен 3 м.
Ввод
В первой строке находится число `N`, затем идут `N` строк по `N` символов: точка обозначает пустой сегмент, решётка – сегмент со стеной.
Вывод
Вывести одно число – площадь видимой части внутренних стен лабиринта в квадратных метрах.
Пример ввода
5 ..... ...## ..#.. ..### .....
Пример вывода
198
