Задача №111280. Поливальная машина
Город N, в отличие от города M, расположен на склоне одного холма. Чистоту улиц этого города обеспечивает единственная поливальная машина. Бензин нынче дорог, поэтому движение муниципального транспорта «в гору» признано слишком расточительным.
Карта города представляет собой прямоугольник, разбитый на H × W клеток, где H и W — высота и ширина карты в клетках соответственно. Часть клеток заняты зданиями, остальные соответствуют улицам и площадям, которые и требуется помыть.
Поливальная машина начинает свой путь в одной из клеток самого верхнего ряда, не занятой зданиями. Она может полить асфальт в текущей клетке и переместиться в любую из двух соседних клеток этого же ряда, не занятых зданиями. Объехать здания, не поднимаясь при этом в гору, невозможно. Поливальная машина также может переместиться в соседнюю по вертикали свободную клетку из нижнего ряда.
Помогите узнать экономному муниципалитету, какое максимальное количество свободных клеток поливальная машина сможет помыть, не поднимаясь при этом в гору?
Учтите, что структура города такова, что в каждом ряду свободные клетки образуют один непрерывный отрезок.
В первой строке входного файла находятся натуральные числа H и W — высота и ширина карты города (1 ≤ W ≤ 300, 1 ≤ H ≤ 300).
Каждая из следующих H строк содержит W символов ‘#’ и ‘.’, означающих, соответственно, клетки со зданиями и без.
Выведите единственное натуральное число — максимальную площадь, которую может обработать поливалка.
8 8 ###...## #...#### ##.##### ##..#### ......## ####...# #...#### #.....##
18