CF549D.Haar Features

The first algorithm for detecting a face on the image working in realtime was developed by Paul Viola and Michael Jones in 2001. A part of the algorithm is a procedure that computes Haar features. As part of this task, we consider a simplified model of this concept.

Let's consider a rectangular image that is represented with a table of size n × m. The table elements are integers that specify the brightness of each pixel in the image.

A feature also is a rectangular table of size n × m. Each cell of a feature is painted black or white.

To calculate the value of the given feature at the given image, you must perform the following steps. First the table of the feature is put over the table of the image (without rotations or reflections), thus each pixel is entirely covered with either black or white cell. The value of a feature in the image is the value of W - B, where W is the total brightness of the pixels in the image, covered with white feature cells, and B is the total brightness of the pixels covered with black feature cells.

Some examples of the most popular Haar features are given below.

Your task is to determine the number of operations that are required to calculate the feature by using the so-called prefix rectangles.

A prefix rectangle is any rectangle on the image, the upper left corner of which coincides with the upper left corner of the image.

You have a variable value, whose value is initially zero. In one operation you can count the sum of pixel values at any prefix rectangle, multiply it by any integer and add to variable value.

You are given a feature. It is necessary to calculate the minimum number of operations required to calculate the values of this attribute at an arbitrary image. For a better understanding of the statement, read the explanation of the first sample.

2001 年，Paul Viola 和 Michael Jones 提出了首个可在实时条件下检测图像中人脸的算法。该算法的一部分是一种用于计算 Haar 特征的过程。在本题中，我们考虑这一概念的一个简化模型。

考虑一幅矩形图像，它由一个大小为 $n \times m$ 的表格表示。表格中的元素均为整数，表示图像中每个像素的亮度值。

一个特征同样是一个大小为 $n \times m$ 的矩形表格。特征的每个单元格被涂成黑色或白色。

要计算给定特征在给定图像上的取值，需执行以下步骤：首先将特征表格无旋转、无翻转地覆盖在图像表格之上，使得每个像素完全被一个黑色或白色特征单元格所覆盖。该特征在图像上的取值定义为 $W - B$，其中 $W$ 是所有被白色特征单元格覆盖的像素亮度总和，$B$ 是所有被黑色特征单元格覆盖的像素亮度总和。

下图给出了几种最常用 Haar 特征的示例：

你的任务是确定：使用所谓“前缀矩形”（prefix rectangle）计算该特征所需的最少操作次数。

前缀矩形是指图像上任意一个其左上角与图像左上角重合的矩形区域。

你有一个变量 $\text{value}$，其初始值为 $0$。每次操作中，你可以任选一个前缀矩形，计算其中所有像素值之和，再乘以任意整数，最后将结果加到 $\text{value}$ 上。

现给出一个特征，你需要计算：为在任意图像上计算该特征的取值，所需的最少操作次数。为更好地理解题意，请参阅第一个样例的解释。

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 100) — the number of rows and columns in the feature.

Next n lines contain the description of the feature. Each line consists of m characters, the j-th character of the i-th line equals to "W", if this element of the feature is white and "B" if it is black.

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 100$）——分别表示该特征的行数和列数。

接下来的 $n$ 行描述该特征。每行包含 $m$ 个字符；其中第 $i$ 行的第 $j$ 个字符为 "W"，表示该特征元素为白色；为 "B"，则表示该特征元素为黑色。

Print a single number — the minimum number of operations that you need to make to calculate the value of the feature.

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

The first sample corresponds to feature B, the one shown in the picture. The value of this feature in an image of size 6 × 8 equals to the difference of the total brightness of the pixels in the lower and upper half of the image. To calculate its value, perform the following two operations:

1. add the sum of pixels in the prefix rectangle with the lower right corner in the 6-th row and 8-th column with coefficient 1 to the variable value (the rectangle is indicated by a red frame);
2. add the number of pixels in the prefix rectangle with the lower right corner in the 3-rd row and 8-th column with coefficient  - 2 and variable value.

Thus, all the pixels in the lower three rows of the image will be included with factor 1, and all pixels in the upper three rows of the image will be included with factor 1 - 2 =  - 1, as required.

第一个样例对应特征 B，即图中所示的特征。该特征在一幅 $6 \times 8$ 尺寸图像中的取值，等于图像下半部分与上半部分所有像素总亮度之差。为计算其值，请执行以下两个操作：

1. 将以第 6 行第 8 列为右下角的前缀矩形内所有像素之和乘以系数 $1$，加到变量 value 中（该矩形由红色边框标出）；
   
2. 将以第 3 行第 8 列为右下角的前缀矩形内像素个数乘以系数 $-2$，加到变量 value 中。
   

因此，图像下半三行的所有像素将以系数 $1$ 被计入，而上半三行的所有像素将以系数 $1 - 2 = -1$ 被计入，符合要求。