06/04/2025 20:12:56

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1547. Погрузка

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

Завхоз 2-го дома Старсобеса хочет вывезти со склада несколько ящиков с продуктами.

Склад имеет форму прямоугольника размером

$N\ times\ M$ , каждая клетка либо занята одним ящиком, либо свободна. Дверь склада находится на левой стороне левой верхней клетки. Альхен использует погрузчик, чтобы поднять ящик и погрузить его в грузовик. В начальный момент времени погрузчик находится за пределами склада. Погрузчик имеет размер

$1\ times\ 1$ , но спереди погрузчика находятся вилы, имеющие длину 1. Вилы погрузчика могут заезжать под ящик (например, чтобы поднять его), но не должны протыкать стены склада.

Погрузчик может ехать по прямой передним и задним ходом. При необходимости можно въехать на склад задним ходом. Погрузчик может поворачивать на свободной площадке

$2\ times\ 2$ , в том числе задним ходом, как показано на рисунке.

Напишите программу, определяющую, сколько ящиков со склада сможет вывезти со склада завхоз, не прибегая к помощи своих родственников для передвижения ящиков на складе.

Первая строка ввода содержит два целых числа

$N$ и

$M$ (

$1\ ≤\ N,M\ ≤\ 100$ ). Далее следует

$N$ строк, содержащих по

$M$ символов – расположение ящиков на складе. Символ '#' означает клетку, занятую ящиком, а символ '.' – свободную клетку.

Вывести одно целое число – максимальное количество ящиков, которое сможет вывезти завхоз.

Пример ввода

3 4
..##
##..
..##

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

Пояснение: оставшиеся ящики на складе будут расположены так:

....
##..
..#.