分数: 400 点
问题陈述
有一个网格 H 水平行和 W 垂直的柱子,并且某些方格上有障碍物。
Snuke 将选择一个未被障碍物占据的方格并在其上放置一盏灯。 放置在广场上的灯会向四个基本方向发出直光束:上、下、左、右。 在每个方向上,光束将继续行进,直到击中被障碍物占据的正方形或击中网格的边界。它将照亮途中的所有方格,包括放置灯的方格,但不会照亮被障碍物占据的方格。
Snuke 想要最大化灯照亮的方块数量。
你被给予 H 字符串 S_i (1 \leq i \leq H),每个长度 W。如果 j- 第一个字符 (1 \leq j \leq W) 的 S_i is #,广场上有障碍物 i从顶部开始的第行和 j左起第 列;如果该字符是 .,那个方块上没有障碍物。
找出灯照亮的最大可能的方块数。
约束
- 1 \leq H \leq 2,000
- 1 \leq W \leq 2,000
- S_i 是一个长度为 W 组成
#和.. .在其中一个字符串中至少出现一次 S_i (1 \leq i \leq H).
输入
输入由标准输入按以下格式给出:
H W S_1 : S_H
输出
打印灯照亮的最大可能的方块数。
示例输入 1
4 6 #..#.. .....# ....#. #.#...
示例输出 1
8
如果 Snuke 将灯放在从上数第二行、从左数第二列的方格上,它将点亮以下方格:第二行从左数第一到第五个方格,以及第二列从上数第一到第四个方格,总共八个方格。
示例输入 2
8 8 ..#...#. ....#... ##...... ..###..# ...#..#. ##....#. #...#... ###.#..#
示例输出 2
13