← 返回题目列表

AtCoder · abc129_d

D. 灯

中文机器翻译题面 查看原题

分数: 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