Lamp

题目描述

有一个由 $H$ 行横向行和 $W$ 列纵向列组成的网格，某些格子上有障碍物。 Snuke 将选择一个没有障碍物的格子并在上面放一盏灯。 放置在该格子的灯会向四个基本方向发出直射光束：上、下、左、右。 在每个方向上，光束会一直传播直到遇到有障碍物的格子或到达网格边界。它会点亮途经的所有格子，包括放置灯的格子，但不包括被障碍物占据的格子。 Snuke 想要使被灯光照到的格子数最大化。 给出 $H$ 个字符串 $S_i$（$1 \leq i \leq H$），每个长度为 $W$。如果 $S_i$ 的第 $j$ 个字符（$1 \leq j \leq W$）是 #，则位于从上数第 $i$ 行、从左数第 $j$ 列的格子上有障碍物；如果该字符是 $.$，则该格子上没有障碍物。 求放置灯后最多能被照亮的格子数。

输入格式

标准输入的格式如下： $H$ $W$ $S_1$ : $S_H$

输出格式

输出放置灯后最多被照亮的格子数。

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

8

8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#

13

提示

$1 \leq H \leq 2,000$ $1 \leq W \leq 2,000$ $S_i$ 是长度为 $W$ 的由 # 和 $.$ 组成的字符串。 对于某个 $S_i$（$1 \leq i \leq H$），至少存在一个字符为 $.$。如果 Snuke 将灯放在从上数第 2 行、从左数第 2 列的格子上，它会照亮如下格子：第二行从左数的第 1 到第 5 个格子，以及第二列从上数的第 1 到第 4 个格子，总共有 8 个格子。

标签: AtCoder|abc129D

来源

AtCoder|abc129D