seuOJ394 - 数方框

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：春季, 夏季, 校赛, 2022

题目描述

让我们一起来数方框！

现在有一张分辨率为$h\times w$的图片，其中画了若干个方框。方框的线条宽度为$1$像素，且方框任一条边长度均不小于$3$像素。所有线条都水平或垂直，也就是不存在类似菱形等情况。

为了方便样例的解释，假设图片左上角为 (1,1) ,右下角为 (h,w) ,我们使用 [($l_1,r_1$),($l_2,r_2$)] 表示一个左上角位于($l_1,r_1$)，右下角位于 ($l_2,r_2$) 的方框。

不同的方框交叉会形成一些新的方框，例如样例中的图形就由 [($1,1$),($9,15$)], [($1,1$),($6,7$)], [($3,3$),($9,15$)]，3个方框组成。然而画出的图形中，除了原本的$3$个方框，还新产生了[($6,1$),($9,3$)], [($3,3$),($6,7$)], [($1,7$),($3,15$)]共$3$个方框。所以样例中一共有$6$个方框。

数据保证，即使是因为交叉产生的小方框，小方框的任意一边长也不小于$3$像素。

现在姬哥在纸上画了不超过 $100$ 个方框，你只知道最终画出的图片，请你数一数一张给定图片里有多少个方框。

输入格式

第一行两个正整数$h,w(3\leq h,w\leq 1000)$，表示图片分辨率。

接下来一共$h$行$w$列的$01$值，代表图片中每个像素，$1$表示线条，$0$表示背景。

数据保证图片可以由不超过100个方框画出。

输出格式

输出一行一个正整数，表示图片中方框的个数。

样例

输入样例

9 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 1 0 0 0 0 0 0 0 1
1 0 1 0 0 0 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 0 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出样例

6