Problem5849--YACS - 消消乐(一)

5849: YACS - 消消乐(一)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

消消乐游戏可以看成一个 $n \times m$ 的方格图,每个方格上放置着可以消除的水果或是不可移动与消除的障碍物。玩家可以通过交换相邻的水果,使同一水果组成超过连续 $3$ 个,便可将其消除。除此之外,还有一种道具叫做水果炸弹,在任意位置放置水果炸弹,便可从水果炸弹位置开始,同时向上下左右四个方向炸出,并消除沿途的水果,直至碰到障碍物为止。
例如下图所示:图中 # 部分表示为障碍物,若在五角星处放置水果炸弹,其消除的水果范围在图中用红色方块表示,则在该位置放置水果炸弹可以消除的水果数量为 $14$ 个。

给定游戏当前进行在一个 $n\times m$ 方格图上,每个格子用 . 表示水果,# 表示障碍物,你拿到一个水果炸弹,请你计算如何放置水果炸弹,能使消除的水果数量最多,最多为多少个?

Input

输入第一行,两个正整数 $n,\ m$。
接下来 $n$ 行:每行 $m$ 个字符,表示游戏方格的状态。

Output

输出一个正整数,表示最多能消除的水果数量。

Constraints

对于 $30\%$ 的数据,$1 \leq n,\ m \leq 10$
对于 $60\%$ 的数据,$1 \leq n,\ m \leq 100$
对于 $100\%$ 的数据,$1 \leq n,\ m \leq 1000$

Sample 1 Input

4 4
##.#
...#
#...
####

Sample 1 Output

5
将水果炸弹放置在 $(2,\ 3)$ 位置,此时最多能够消除 $5$ 个水果。

HINT

题目来源:IAI 463

Source/Category