#WeekContest1001T6. 粮仓选址
粮仓选址
粮仓选址
题目描述
噜噜准备在一块 的荒地上修建 简易粮仓。
为了方便施工,每座粮仓必须正好占据一个 的水平矩形(高 行、宽 列)。若矩形 个格子全部为空地 .
,就可以建粮仓;只要其中有任何岩石 #
,该矩形就无法使用。
噜噜可以 至多炸掉一格岩石(把某个 #
变成 .
)。
请问在最佳炸点方案下,最多有多少个位置可以建造合法粮仓?
粮仓之间可以互相重叠或相邻;题目只要求统计满足条件的 矩形总数,而不需要实际放置或去重。
输入格式
第一行两个整数,。 接下来行列的字符,表示地图矩阵;
- 每行
rowᵢ
为长 的字符串,只含.
与#
。
输出格式
一个整数,表示可建粮仓的最大数量。
样例一
输入
4 6
..#...
.#....
......
...#..
输出
7
说明
若炸掉第 行第 列(坐标 ())的岩石,可使原本包含 唯一 岩石的若干 矩形变为全空地;此时总共有 个合法矩形。
数据范围与难度说明
- ,保证读取总输入不超过 字符。
相关
在下列比赛中: