|
Таинственные прямоугольники
(Время: 10 сек. Память: 128 Мб Сложность: 82%)
В таблице размерностью N×M, состоящей из ячеек черного и белого цвета, требуется найти количество различных прямоугольных рамок, состоящих из ячеек черного цвета. Рамка прямоугольника размерности h×w состоит ровно из 2×(h+w-2) ячеек. В этой задаче нас будут интересовать только прямоугольники, для которых h ≥ 3 и w ≥ 3.
Например, таблица, изображенная на рисунке справа, содержит девять таких прямоугольников: один прямоугольник 3×3, два прямоугольника 3×4, два прямоугольника 4×3, один прямоугольник 3×5, один прямоугольник 5×3 и два прямоугольника 4×4.
Входные данные
В первой строке входного файла INPUT.TXT записано два натуральных числа N и M (3 ≤ N, M ≤ 2000) – размеры таблицы. Далее в N строках записано по M символов – содержание таблицы. Символом «#» обозначается клетка черного цвета, а символом «.» – белая клетка.
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT | Пояснения |
|---|
| 1 | 3 3
###
###
### | 1 | Один прямоугольник размером 3×3 и черная ячейка в центре |
| 2 | 3 3
###
#.#
### | 1 | Один прямоугольник размером 3×3, но уже без черной ячейки |
| 3 | 6 6
######
#.##.#
######
######
#.##.#
###### | 25 | По 4 прямоугольника размерами 3×3 и 4×4, по 4 прямоугольника размерами 3×4 и 4×3, по 2 прямоугольника размерами 3×6 и 6×3, 4×6 и 6×4, и 1 прямоугольник размером 6×6 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
