You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 最近刚学了关于矩阵的问题，小 Y 就出了一个题准备考考小 Z。小 Y 提出了一个叫做 "01完美矩阵" 的概念。一个 01 矩形被称为是 01 完美矩形，如果满足下面 $3$ 个条件:

1. 它的四条边上都是 $1$，
2. 内部（除了 $4$ 条边）的 $0$ 和 $1$ 的个数之差不超过 $1$，
3. 大小至少是 $2 * 2$，即该矩阵行数和列数都至少要大于等于 $2$。

注意：01完美矩阵可以全是 1，只要满足上述 3 个要求。

给定一个 01 矩阵，问小 Z 可以在这个矩阵中圈出多少个 01 完美矩形。

输入格式

从 matrix.in 文件输入数据。

第一行两个整数 $n$ 和 $m$，表示矩阵的行数和列数。

接下来 $n$ 行，每行 $m$ 个数，$0$ 或者 $1$，每行输入的数都用一个空格隔开。

输出格式

输出到 matrix.out 文件。

输出 $01$ 完美矩形的个数。

样例

4 4
1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1

3

5 5
1 0 1 1 1
1 0 1 0 1
1 1 0 1 1
1 0 0 1 1
1 1 1 1 1

3

样例输入3

点击链接 matrix.in 下载大样例输入

样例输出3

点击链接 matrix.out 下载大样例输出

说明/提示

样例 1 解释

如下图所示，满足条件的 01 完美矩阵有圈起来的 $3$ 个。

数据范围

对于 $30\%$ 的数据，$n$ 和 $m$ 的数据范围 $[1,20]$;

对于 $60\%$ 的数据，$n$ 和 $m$ 的数据范围 $[1,100]$;

对于 $100\%$ 的数据，$n$ 和 $m$ 的数据范围 $[1,300]$。