[R38G]花草园 - 代码源竞赛平台

时空限制

3S/1024M

题目描述

apiadu 有一个 $n$ 行 $m$ 列的矩形花草园。园中的每个格子可能是空地（用数字 $1$ 表示）、花（用数字 $2$ 表示）或草（用数字 $3$ 表示）。

apiadu 认为一个子矩形区域是“美丽的”，当且仅当该子矩形满足以下所有条件：

1. 至少包含 $2$ 行，且至少包含 $2$ 列。
2. 四个角（左上、右上、左下、右下）的位置必须都是空地。
3. 区域内至少包含 $1$ 个格子是花。
4. 区域内至少包含 $1$ 个格子是草。

请计算出花草园中有多少个“美丽的”子矩形区域。

格式

输入格式

第一行包含两个整数 $n, m$，表示花草园的大小。

接下来 $n$ 行，每行 $m$ 个整数，表示花草园的布局。

• $1$ 表示空地；
• $2$ 表示花；
• $3$ 表示草。

输出格式

输出一个整数，表示美丽区域的数量。

样例

样例输入 #1

5 5
1 2 1 2 1
1 3 1 2 1
1 2 1 2 1
1 3 3 2 1
1 3 3 3 1

样例输出 #1

13

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n, m \le$	$n \times m \le$
$1$	$35$	$5000$
$2$	$55$	$500$	$2.5 \times 10^5$
$3$	$10$	$2.5 \times 10^5$

对于 $100\%$ 的数据，$n \times m \leq 2.5 \times 10^5$。