#WeekContest1001T6. 粮仓选址

粮仓选址

粮仓选址

题目描述

噜噜准备在一块 n×mn \times m 的荒地上修建 简易粮仓。 为了方便施工,每座粮仓必须正好占据一个 2×32 \times 3 的水平矩形(高 22 行、宽 33 列)。若矩形 66 个格子全部为空地 .,就可以建粮仓;只要其中有任何岩石 #,该矩形就无法使用。

噜噜可以 至多炸掉一格岩石(把某个 # 变成 .)。 请问在最佳炸点方案下,最多有多少个位置可以建造合法粮仓?

粮仓之间可以互相重叠或相邻;题目只要求统计满足条件的 2×32\times3 矩形总数,而不需要实际放置或去重。


输入格式

第一行两个整数,n,mn,m。 接下来nnmm列的字符,表示地图矩阵;

  • 1n,m10001\le n,m\le 1000
  • 每行 rowᵢ 为长 mm 的字符串,只含 .#

输出格式

一个整数,表示可建粮仓的最大数量。


样例一

输入

4 6
..#...
.#....
......
...#..

输出

7

说明

若炸掉第 44 行第 44 列(坐标 (4,44,4))的岩石,可使原本包含 唯一 岩石的若干 2×32\times3 矩形变为全空地;此时总共有 77 个合法矩形。


数据范围与难度说明

  • 1n,m10001\le n,m\le 1000,保证读取总输入不超过 10610^{6} 字符。