← 返回题目
题库练习 [ABC129D] Lamp
← 上一题 下一题 →

A7657 | [ABC129D] Lamp

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

给定一个高为 $H$ 行、宽为 $W$ 列的网格。在这个网格中，部分格子存在障碍物。

すぬけ君想要在没有障碍物的格子中选择一个，并在该格子上安装一盏灯。从安装灯的格子出发，光线会沿着上下左右四个方向直线照射。对于每个方向，光线会一直照射到遇到第一个有障碍物的格子，或者到达网格边界的前一个格子为止。安装灯的格子本身也会被照亮，但有障碍物的格子不会被照亮。

すぬけ君希望通过安装灯，使被照亮的格子数最大。

给定 $H$ 个长度为 $W$ 的字符串 $S_i$（$1 \leq i \leq H$）。当 $S_i$ 的第 $j$ 个字符（$1 \leq j \leq W$）为 # 时，表示从上到下第 $i$ 行、从左到右第 $j$ 列的格子有障碍物；为 . 时表示没有障碍物。

请你求出被照亮的格子数的最大值。

输入格式

输入通过标准输入给出，格式如下：

> $H$ $W$
> $S_1$
> $S_2$
> $\vdots$
> $S_H$

输出格式

输出被照亮的格子数的最大值。

输入输出样例

输入 #1
4 6
#..#..
.....#
....#.
#.#...
输出 #1
8
输入 #2
8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#
输出 #2
13
C++ 编辑器
输入
输出