Задача B. Компьютерное зрение

Автор:M. Kuzin   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Ваша команда сейчас занимается разработкой нового робота. Вам поручена ответственная задача — научить робота находить на картинке ромбы.

Камера робота позволяет записывать черно-белые прямоугольные изображения шириной c и высотой r ячеек. Черная ячейка на изображении кодируется символом '#', а белая символом '@'. Ромбом называется связная область изображения, целиком состоящая из черных ячеек и удовлетворяющая следующим критериям:

Например, вот корректные изображения ромбов имеющих высоту 2 (обратите внимание, что к ромбу могут прилегать и другие черные ячейки):

@@#@@ @###@ #####

@###@ ##### #####

@@#@@ @@#@@ #####

А вот примеры некорректных ромбов:

@@#@@ @###@ @@@@@

@#@#@ @@### @@@@@

@@#@@ @@#@@ @@@@@

Конечно, на одной картинке одновременно может находиться множество ромбов. Сейчас вам требуется найти максимальный из них по высоте.

Формат входных данных

В первой строке находятся два натуральных числа 1 ≤ r, c ≤ 1000 — высота и ширина изображения.

В следующих r строках находятся по c символов '@' или '#', означающих цвет ячеек изображения. '@' - белый цвет, '#' — черный цвет.

Формат выходных данных

Выведите одно целое число — максимальную высоту ромба на изображении. Если на изображении отсутствуют ромбы, то выведите 0.

Ограничения

1 ≤ r, c ≤ 10 — 40 баллов

1 ≤ r, c ≤ 100 — 20 баллов

1 ≤ r, c ≤ 1000 — 40 баллов

Примеры тестов

Стандартный вход Стандартный выход
1
5 5
@@#@@
@###@
#####
@###@
@@#@@
3
2
3 5
@#@#@
#####
@#@#@
2
3
3 3
@@@
@@@
@@@
0

Разбор

Для каждой позиции в массиве нужно посчитать сколько черных клеток находятся справа и слева от нее. Для этого достаточно пройти по каждой строке и поддерживать последнюю найденную белую клетку. В каждую ячейку нужно записать разность ее индекса и индекса последней белой клетки.

Теперь для каждой ячейки можно с помощью динамического программирования посчитать dp[i][j] — максимальную высоту треугольника (половину ромба) снизу и сверху. Для каждой клетки dp[i][j] = min(left[i][j], right[i][j], dp[i1][j]), так как любой треугольник состоит из нижней полосы и меньшего треугольника. Аналогично можно посчитать нижние треугольники.

Теперь минимум из высоты верхнего и нижнего треугольника для каждой клетки является высотой максимального ромба с центром в этой клетке. Асимптотика O(n2).


0.109s 0.013s 13