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

printЗадачи

1045. Шоссе через город

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

Город 4е имеет форму квадрата размером `N\ times\ N` кварталов. Каждый квартал либо застроен зданием, либо является пустым. Необходимо построить широкое шоссе из левого верхнего угла города в правый нижний угол. Шоссе должно проходить через кварталы города, являющие соседними по горизонтали или вертикали. Шоссе не должно выходить за пределы города и проходить более чем через `2*N+1` кварталов. Часть зданий при строительстве придется снести.
Напишите программу, которая по плану города определит минимальное количество зданий, которое потребуется снести при строительстве шоссе.
Во входном файле несколько тестовых случаев. Каждый тест начинается со строки, содержащей одно целое число `N` (`2\ ≤\ N\ ≤\ 500`) – размер города. Далее следует `N` строк, содержащих по `N` символов – план города. Символ '#' означает квартал со зданием, символ '.' – пустырь. Набор тестов заканчивается строкой, содержащей число 0.
Для каждого тестового случая вывести строку, содержащую одно целое число – минимальное количество сносимых зданий.

Пример ввода

4
####
#...
.#..
..#.
5
..#..
#.#..
..#..
.##..
.....
0

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

2
0
loading