A7657. [ABC129D] Lamp
编程题
普及/提高-
知识点
题目描述
给定一个高为 $H$ 行、宽为 $W$ 列的网格。在这个网格中，部分格子存在障碍物。
すぬけ君想要在没有障碍物的格子中选择一个，并在该格子上安装一盏灯。从安装灯的格子出发，光线会沿着上下左右四个方向直线照射。对于每个方向，光线会一直照射到遇到第一个有障碍物的格子，或者到达网格边界的前一个格子为止。安装灯的格子本身也会被照亮，但有障碍物的格子不会被照亮。
すぬけ君希望通过安装灯，使被照亮的格子数最大。
给定 $H$ 个长度为 $W$ 的字符串 $S_i$（$1 \leq i \leq H$）。当 $S_i$ 的第 $j$ 个字符（$1 \leq j \leq 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$
> $H$ $W$
> $S_1$
> $S_2$
> $\vdots$
> $S_H$
输出格式
输出被照亮的格子数的最大值。
输入输出样例
输入 #1
4 6 #..#.. .....# ....#. #.#...
输出 #1
8
输入 #2
8 8 ..#...#. ....#... ##...... ..###..# ...#..#. ##....#. #...#... ###.#..#
输出 #2
13
说明/提示
## 限制条件
- $1 \leq H \leq 2,000$
- $1 \leq W \leq 2,000$
- $S_i$ 仅由
- 至少存在一个
## 样例解释 1
如果すぬけ君在从上到下第 $2$ 行、从左到右第 $2$ 列的格子安装灯，则从上到下第 $2$ 行、从左到右第 $1$ 到 $5$ 列的格子，以及从左到右第 $2$ 列、从上到下第 $1$ 到 $4$ 行的格子都会被照亮，总共 $8$ 个格子。
- $1 \leq H \leq 2,000$
- $1 \leq W \leq 2,000$
- $S_i$ 仅由
# 和 . 组成，长度为 $W$- 至少存在一个
.## 样例解释 1
如果すぬけ君在从上到下第 $2$ 行、从左到右第 $2$ 列的格子安装灯，则从上到下第 $2$ 行、从左到右第 $1$ 到 $5$ 列的格子，以及从左到右第 $2$ 列、从上到下第 $1$ 到 $4$ 行的格子都会被照亮，总共 $8$ 个格子。