LibreOJ

569 「LibreOJ Round #11」Misaka Network 与测试

内存限制：512 MB 时间限制：1000 ms

题目描述

研究者们想要测试 Misaka Network，于是他们把 Misaka Network 中的所有妹妹们召集到了一起。

现在妹妹们排成了 $N$ 行 $M$ 列，有的位置没有人。现在研究者们给每一个个体的超能力进行了评定，一共有三个能力等级：Level 1 低能力者、Level 2 异能力者 和 Level 3 超能力者。研究者们每次测试可以选取一个子矩形内的所有个体，为了保证高效，他们不希望这个矩形内存在空的位置。并且，为了保证稳定，他们希望这个矩形内所有个体的能力等级的平均值恰好为 $2$。同时，每个个体最多只能参加一次测试，因此，多次测试选取的矩形应当不相交。

研究者们想知道他们最多能进行多少次测试。

输入格式

第一行两个整数$N$、$M$。

接下来 $N$ 行每行 $M$ 个字符，每个字符表示了队列中对应位置的个体。

1 表示 Level 1 低能力者，2 表示 Level 2 异能力者，3 表示 Level 3 超能力者，* 表示一个空的位置。

输出格式

一行一个整数，表示最多能够进行多少次测试。

样例 1

样例 2

样例 3

数据范围与提示

对于所有数据 $1 \leq N \times M \leq 10^5$，队列中仅包含 1、2、3、* 四种字符。

子任务编号 分值 $N \times M$ 特殊性质
1 $5$ $\leq 10^5$ 队列中不存在 1
2 $15$ $\leq 1000$ $N=1$
3 $15$ $\leq 2000$ $N=2$
4 $35$ $\leq 2000$ 队列中不存在 *
5 $15$ $\leq 2000$ -
6 $15$ $\leq 10^5$ -

样例

样例输入 1

2 3
31*
*13

样例输出 1

2

样例输入 2

6 6
23311*
**13**
11*233
13*223
***133
331***

样例输出 2

9

样例输入 3

2 50
21111121332233123311312211231333122233133212221212
21332123132223111331233121122331133311112121331311

样例输出 3

51