AT_utpc2020_h Grid Eraser
题目描述
umg 有一个 $H$ 行 $W$ 列的网格。这个网格中每个格子可以是白色或黑色。用 $S_{ij}$ 表示第 $i$ 行第 $j$ 列格子的颜色，其中 `.` 表示白色，`#` 表示黑色。umg 可以通过以下两种方式获得分数：
1. 如果第 $i$ 行的所有格子颜色相同，umg 可以删除这一行，获得 $1$ 分。删除后，如果存在的话，第 $i-1$ 行和第 $i+1$ 行会相连。
2. 如果第 $j$ 列的所有格子颜色相同，umg 可以删除这一列，获得 $1$ 分。删除后，如果存在的话，第 $j-1$ 列和第 $j+1$ 列会相连。
当网格中没有任何格子可供操作时，umg 将无法再进行任何操作。请问 umg 最多能够获得多少分？
输入格式
输入通过标准输入给出，格式如下：
> $H$ $W$
$S_{11} \cdots S_{1W}$
$\vdots$
$S_{H1} \cdots S_{HW}$
输出格式
输出一个整数，表示 umg 可以获得的最大分数。
说明/提示
- $1 \leq H, W \leq 2000$
- $S_{ij}$ 仅可能为 `.` 或 `#`
### 举例说明
对于某个示例，umg 可以以以下步骤获得最多 $2$ 分：
1. 删除第 2 行获得 1 分，剩下的网格是：
```
.##
##.
```
2. 删除第 2 列获得 1 分，最终网格变成：
```
.#
#.
```
此时无法再进行任何删除操作。
**本翻译由 AI 自动生成**