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

Условие

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

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

• Ромб имеет какую-то целую высоту h ≥ 0.
• Ромб имеет центр, описываемый двумя координатами 1 ≤ x_c ≤ c, 1 ≤ y_c ≤ r. (x_c, y_c) — позиция ячейки на изображении.
• Все ячейки, имеющие координаты x, y, такие что |x − x_c| + |y − y_c| < h принадлежат ромбу и обязаны иметь черный цвет.

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

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

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

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

5 5
@@#@@
@###@
#####
@###@
@@#@@

3

3 5
@#@#@
#####
@#@#@

2

3 3
@@@
@@@
@@@

0

Разбор

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

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

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