Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1045. Шоссе через город
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 01/09/2008 | Заочный тур личного первенства (B) |
| 18/02/2013 | Занятие 17 (C) |
| 19/07/2016 | Лето 2016 - 11 (D) |
| 08/07/2019 | Лето 2019 - 4 (C) |
| 06/07/2020 | Летние сборы - 4 (D) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Город 4е имеет форму квадрата размером `N\ times\ N` кварталов.
Каждый квартал либо застроен зданием, либо является пустым.
Необходимо построить широкое шоссе из левого верхнего угла города в правый нижний угол. Шоссе должно проходить через кварталы города,
являющие соседними по горизонтали или вертикали. Шоссе не должно выходить за пределы города и проходить более чем
через `2*N+1` кварталов. Часть зданий при строительстве придется снести.
Напишите программу, которая по плану города определит минимальное количество зданий, которое потребуется снести при строительстве шоссе.
Во входном файле несколько тестовых случаев. Каждый тест начинается со строки, содержащей одно целое число `N` (`2\ ≤\ N\ ≤\ 500`) –
размер города. Далее следует `N` строк, содержащих по `N` символов – план города. Символ '#' означает квартал
со зданием, символ '.' – пустырь. Набор тестов заканчивается строкой, содержащей число 0.
Для каждого тестового случая вывести строку, содержащую одно целое число – минимальное количество сносимых зданий.
Пример ввода
4 #### #... .#.. ..#. 5 ..#.. #.#.. ..#.. .##.. ..... 0
Пример вывода
2 0
