问题 S: 摆字方阵
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:424
解决:119
题目描述
这道题和军训时的摆字方阵有些像,但又不完全像。
有一个N*M的方阵,由"#"和"."构成,"."点的同学是可以主动翻面或跟随翻面的,而"#"点的同学无论何时都不能动。
每当一个"."同学主动翻面,它周围的"."点的同学就会跟随翻面,整个效果就像炸弹堂类似,初始点放置了一颗炸弹,然后就会形成一个“十”字形状,长度一定的攻击范围。
不过在本题中,上下左右四个方向除非遇到"#"点,就会一直沿着当前方向延续,即“十”字四条边的长度无限制,就……你懂!
然后问只能由一个"."同学主动翻面的情况下,能最多翻面的同学的个数。
有一个N*M的方阵,由"#"和"."构成,"."点的同学是可以主动翻面或跟随翻面的,而"#"点的同学无论何时都不能动。
每当一个"."同学主动翻面,它周围的"."点的同学就会跟随翻面,整个效果就像炸弹堂类似,初始点放置了一颗炸弹,然后就会形成一个“十”字形状,长度一定的攻击范围。
不过在本题中,上下左右四个方向除非遇到"#"点,就会一直沿着当前方向延续,即“十”字四条边的长度无限制,就……你懂!
然后问只能由一个"."同学主动翻面的情况下,能最多翻面的同学的个数。
输入
1≤N≤2,000
1≤M≤2,000
Si,j='.'或Si,j='#'
1≤M≤2,000
Si,j='.'或Si,j='#'
输出
被翻面的点的数量的最大值
样例输入 复制
4 6
#..#..
.....#
....#.
#.#...
样例输出 复制
8
提示
样例解释:
最优解,主动翻面的同学为@,被动的翻面的同学为*
# * . # . .
* @ * * * #
. * . . # .
# * # . . .
最优解,主动翻面的同学为@,被动的翻面的同学为*
# * . # . .
* @ * * * #
. * . . # .
# * # . . .