← 返回题目列表

AtCoder · utpc2020_h

H. 网格橡皮擦

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

問題文

umg 先生有纵向 H 行、横 W 行的网格。每个格子是白色或黑色。从上到下 i 第几行,从左起 j 第列格子的颜色是 S_{ij} 什么时候可以工作 . 时为白色, # 时为黑色。umg 先生如下 2 通过以喜欢的顺序和次数进行各种操作来获得积分。

  • i 行中的所有格子都是相同颜色时 i , i 删除该行 1 获取积分。之后, i-1 线和 i+1 行(如果存在)会被连接。
  • j 列中的所有格子都是相同颜色时 j ,j 删除该列 1 获取积分。之后, j-1 列和 j+1 列(如果存在)会被连接。

如果网格中没有格子存在, 1 则无法进行操作。umg君最多可以获得多少积分?

制約

  • 1 \leq H,W \leq 2000
  • S_{ij} 是 您也可以写 . 或 至少 #

入力

输入是按以下格式从标准输入给出的。

H W  
S_{11}\cdotsS_{1W}  
\vdots  
S_{H1}\cdotsS_{HW}  

出力

答案 请打印除以 1 行输出。


入力例1

3 3
.##
...
##.

出力例1

2

按如下方式操作 2 获取积分是最优的。

2 删除该行 1 获取积分后,网格将如下所示。

.##
##.

2 删除该列 1 获取积分后,网格将如下所示。

.#
#.

无法再进行操作。


入力例2

7 56
........................................................
.#...#..#####..#####...####..#####..#####..#####..#####.
.#...#....#....#...#..#..........#..#...#......#..#...#.
.#...#....#....####...#......#####..#...#..#####..#...#.
.#...#....#....#......#......#......#...#..#......#...#.
..###.....#....#.......####..#####..#####..#####..#####.
........................................................

出力例2

24