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

printЗадачи

1547. Погрузка

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

Завхоз 2-го дома Старсобеса хочет вывезти со склада несколько ящиков с продуктами.
14368.jpg
Склад имеет форму прямоугольника размером `N\ times\ M`, каждая клетка либо занята одним ящиком, либо свободна. Дверь склада находится на левой стороне левой верхней клетки. Альхен использует погрузчик, чтобы поднять ящик и погрузить его в грузовик. В начальный момент времени погрузчик находится за пределами склада. Погрузчик имеет размер `1\ times\ 1`, но спереди погрузчика находятся вилы, имеющие длину 1. Вилы погрузчика могут заезжать под ящик (например, чтобы поднять его), но не должны протыкать стены склада.
Погрузчик может ехать по прямой передним и задним ходом. При необходимости можно въехать на склад задним ходом. Погрузчик может поворачивать на свободной площадке `2\ times\ 2`, в том числе задним ходом, как показано на рисунке.
14367.png
Напишите программу, определяющую, сколько ящиков со склада сможет вывезти со склада завхоз, не прибегая к помощи своих родственников для передвижения ящиков на складе.
Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,M\ ≤\ 100`). Далее следует `N` строк, содержащих по `M` символов – расположение ящиков на складе. Символ '#' означает клетку, занятую ящиком, а символ '.' – свободную клетку.
Вывести одно целое число – максимальное количество ящиков, которое сможет вывезти завхоз.

Пример ввода

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

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

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