#ABC129D. Lamp
Lamp
题目描述
There is a grid with horizontal rows and vertical columns, and there are obstacles on some of the squares.
Snuke is going to choose one of the squares not occupied by an obstacle and place a lamp on it. The lamp placed on the square will emit straight beams of light in four cardinal directions: up, down, left, and right. In each direction, the beam will continue traveling until it hits a square occupied by an obstacle or it hits the border of the grid. It will light all the squares on the way, including the square on which the lamp is placed, but not the square occupied by an obstacle.
Snuke wants to maximize the number of squares lighted by the lamp.
You are given strings (), each of length . If the -th character () of is #
, there is an obstacle on the square at the -th row from the top and the -th column from the left; if that character is .
, there is no obstacle on that square.
Find the maximum possible number of squares lighted by the lamp.
有一个网格,横向有 行,纵向有 列,其中一些方格上有障碍物。
斯努克要选择一个没有障碍物的方格,并在上面放一盏灯。放置在方格上的灯会向四个基本方向发出直线光束:向上、向下、向左和向右。在每个方向上,光束都会继续前进,直到击中一个被障碍物占据的方格或击中网格的边界。它将照亮途中的所有方格,包括灯所在的方格,但不会照亮被障碍物占据的方格。
Snuke 希望灯点亮的方格数达到最大。
我们给出了长度为 的 字符串 ( )。如果 的第 个字符( )是 "#",那么在从上往下的第 行和从左往上的第 列的方格上有障碍物;如果该字符是".",那么该方格上没有障碍物。
求被灯照亮的方格的最大可能数目。
输入格式
输入内容按以下格式标准输入:
输出格式
打印灯点亮的最大方格数。
样例 #1
样例输入 #1
4 6
#..#..
.....#
....#.
#.#...
样例输出 #1
8
样例 #2
样例输入 #2
8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#
样例输出 #2
13
说明
数据规模与约定
- 是长度为 的字符串,由
#
和.
组成。 .
在字符串 ( ) 中至少出现一次。
样例 解释
如果 Snuke 把灯放在从上往下第二行、从左往上第二列的方格上,它将点亮以下方格:第二行从左起第一到第五个方格,第二列从上起第一到第四个方格,总共八个方格。