← 返回题目列表

Codeforces · 549/D

D. Haar 特点

中文机器翻译题面 查看原题

第一个实时检测图像上人脸的算法由 Paul Viola 和 Michael Jones 于 2001 年开发。该算法的一部分是计算 Haar 特征的过程。作为这项任务的一部分,我们考虑这个概念的简化模型。

让我们考虑一个用大小为 n × m 的表格表示的矩形图像。表元素是指定图像中每个像素的亮度的整数。

一个特征也是一个大小为 n × m 的矩形桌子。特征的每个单元都被漆成黑色或白色。

要计算给定图像上给定特征的值,您必须执行以下步骤。首先,将特征表放在图像表上(没有旋转或反射),因此每个像素完全被黑色或白色单元覆盖。图像中某个特征的值是 W - B 的值,其中 W 是图像中被白色特征单元覆盖的像素的总亮度,B 是被黑色特征单元覆盖的像素的总亮度。

下面给出了最流行的 Haar 功能的一些示例。

您的任务是确定使用所谓的前缀矩形计算特征所需的操作数。

前缀矩形是图像上的任意矩形,其左上角与图像的左上角重合。

您有一个变量值,其值最初为零。在一次操作中,您可以计算任何前缀矩形处的像素值之和,将其乘以任何整数并添加到变量值。

您获得了一项功能。有必要计算在任意图像上计算该属性的值所需的最少操作次数。为了更好地理解该语句,请阅读第一个示例的解释。

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 100) — 特征中的行数和列数。

接下来的 n 行包含该功能的描述。每行由 m 个字符组成,如果特征的该元素是白色,则第 i 行的第 j 个字符等于“W”,如果是黑色,则等于“B”。

输出

打印单个数字 — 计算特征值所需执行的最少操作数。

示例

输入 #1

6 8
BBBBBBBB
BBBBBBBB
BBBBBBBB
WWWWWWWW
WWWWWWWW
WWWWWWWW

输出 #1

2

输入 #2

3 3
WBW
BWW
WWW

输出 #2

4

输入 #3

3 6
WWBBWW
WWBBWW
WWBBWW

输出 #3

3

输入#4

4 4
BBBB
BBBB
BBBB
BBBW

输出#4

4

注意

第一个样本对应于特征 B,如图所示。在尺寸为 6 × 8 的图像中,该特征的值等于图像下半部分和上半部分像素的总亮度之差。要计算其值,请执行以下两个操作:

1、将第6行第8列右下角的前缀矩形中系数为1的像素之和添加到变量值中(该矩形用红框表示);
2.将第3行第8列右下角前缀矩形中的像素数与系数 - 2和变量值相加。

因此,根据需要,图像下部三行中的所有像素将包含因子 1,图像上部三行中的所有像素将包含因子 1 - 2 = - 1。