CF549D Haar Features

2001 年，Paul Viola 和 Michael Jones 首次开发出了可以实时检测图像中人脸的算法。该算法中的一部分用于计算 Haar 特征。在本题中，我们将考虑该概念的简化模型。 给定一个由 $n \times m$ 大小的矩形图像区域。区域中的每个元素是一个整数，表示该像素的亮度。 特征也是一个 $n \times m$ 的矩形表。特征的每个格子要么被涂黑，要么被涂白。 要计算给定特征在给定图像上的值，需要执行以下步骤。首先，将特征表格直接覆盖在图像表格上（不进行旋转或翻转），这样每个像素都被黑色或白色的特征格子完全覆盖。特征在该图像上的值为 $W-B$，其中 $W$ 是所有被白色特征格子覆盖的像素亮度总和，$B$ 是所有被黑色特征格子覆盖的像素亮度总和。 下面给出了最常见的 Haar 特征示例。  你的任务是使用所谓的前缀矩形计算该特征所需的操作次数。 前缀矩形是指图像上矩形的一种，其左上角总是与图像的左上角重合。 你有一个变量 $value$，初始值为 $0$。每一步操作，你都可以计算任意一个前缀矩形内像素值的总和，将其乘以任意整数后加到变量 $value$ 上。 现在给定特征描述，请你计算最少需要多少次操作才能在任意图像上计算出该特征的值。为了更好地理解题意，请参考样例一的解释。

第一行为两个用空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 100$），表示特征的行数和列数。 接下来的 $n$ 行描述特征，每行包括 $m$ 个字符。若该格特征为白色，则为 'W'，若为黑色，则为 'B'。

输出一个整数，表示计算该特征所需的最少操作次数。

第一个样例对应的是图中的特征 $B$。该特征在一个 $6 \times 8$ 的图像上的值等于下半部分所有像素亮度总和减去上半部分所有像素亮度总和。你可以用如下两个操作来计算此特征： 1. 将以第 $6$ 行第 $8$ 列为右下角的前缀矩形的像素和，乘以 $1$ 加到变量 $value$ 上（该矩形如红框所示）； 2. 将以第 $3$ 行第 $8$ 列为右下角的前缀矩形的像素和，乘以 $-2$ 加到变量 $value$ 上。 这样，图像下半部分的所有像素将以系数 $1$ 计入，上半部分的所有像素将以系数 $1-2=-1$ 计入，正好符合题意。 由 ChatGPT 5 翻译