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