Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1547. Погрузка
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 19/03/2011 | Южно-Уральский открытый командный чемпионат по программированию (G) |
Ограничения: время – 250ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Завхоз 2-го дома Старсобеса хочет вывезти со склада
несколько ящиков с продуктами.
Склад имеет форму прямоугольника размером `N\ times\ M`, каждая клетка либо занята одним ящиком,
либо свободна. Дверь склада находится на левой стороне левой верхней клетки.
Альхен использует погрузчик, чтобы поднять ящик и погрузить его в грузовик.
В начальный момент времени погрузчик находится за пределами склада.
Погрузчик имеет размер `1\ times\ 1`, но спереди погрузчика
находятся вилы, имеющие длину 1. Вилы погрузчика могут заезжать под ящик (например, чтобы поднять его),
но не должны протыкать стены склада.
Погрузчик может ехать по прямой передним и задним ходом.
При необходимости можно въехать на склад задним ходом.
Погрузчик может поворачивать на свободной площадке `2\ times\ 2`, в том числе задним ходом,
как показано на рисунке.
Напишите программу, определяющую, сколько ящиков со склада сможет вывезти со склада завхоз,
не прибегая к помощи своих родственников для передвижения ящиков на складе.
Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,M\ ≤\ 100`).
Далее следует `N` строк, содержащих по `M` символов – расположение ящиков на складе.
Символ '#' означает клетку, занятую ящиком, а символ '.' – свободную клетку.
Вывести одно целое число – максимальное количество ящиков, которое сможет вывезти завхоз.
Пример ввода
3 4 ..## ##.. ..##
Пример вывода
3
.... ##.. ..#.
