D. Признаки Хаара
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Первый алгоритм для определения лиц на изображении, который работает в реальном времени, был разработан Paul Viola и Michael Jones в 2001 году. Частью алгоритма является процедура, вычисляющая признаки Хаара. В рамках данной задачи мы рассмотрим упрощённую модель данного понятия.

Рассмотрим прямоугольное изображение, представляющее собой таблицу размера n × m. Элементы таблицы являются целыми числами, задающими яркость каждого пикселя в изображении.

Признак также представляет из себя прямоугольную таблицу размера n × m. Каждая ячейка признака покрашена в черный или белый цвет.

Чтобы вычислить значение данного признака на данном изображении, необходимо произвести следующие шаги. Сначала таблица признака совмещается с таблицей изображения (без переворотов или отражений), таким образом, каждый пиксель оказывается целиком покрыт либо черным, либо белым цветом. Значением признака на изображении называется величина W - B, где W — суммарная яркость пикселей изображения, покрытых белыми ячейками признака, а B — суммарная яркость пикселей, покрытых черными ячейками признака.

Ниже изображены примеры наиболее популярных признаков Хаара.

Ваша задача будет заключаться в определении числа операций, которые необходимы для подсчёта признака с помощью так называемых префиксных прямоугольников.

Префиксным прямоугольником называется любой прямоугольник на изображении, левый верхний угол которого совпадает с левым верхним углом изображения.

У вас есть переменная value, значение которой исходно равняется нулю. За одну операцию вы можете посчитать сумму значений пикселей на любом префиксном прямоугольнике, умножить её на любое целое число и прибавить к переменной value.

Вам задан признак. Необходимо посчитать минимальное число операций, которое требуется для вычисления значения этого признака на произвольном изображении. Для лучшего понимания условия, прочтите объяснение первого примера.

Входные данные

В первой строке через пробел заданы два целых числа n и m (1 ≤ n, m ≤ 100) — количество строк и столбцов в признаке.

Следующие n строк содержат описание признака. Каждая строка состоит из m символов, j-й символ i-й строки равен «W», если этот элемент признака имеет белый цвет и «B», если черный.

Выходные данные

Выведите одно число — минимальное количество операций, которое необходимо произвести, чтобы вычислить значение признака.

Примеры
Входные данные
6 8
BBBBBBBB
BBBBBBBB
BBBBBBBB
WWWWWWWW
WWWWWWWW
WWWWWWWW
Выходные данные
2
Входные данные
3 3
WBW
BWW
WWW
Выходные данные
4
Входные данные
3 6
WWBBWW
WWBBWW
WWBBWW
Выходные данные
3
Входные данные
4 4
BBBB
BBBB
BBBB
BBBW
Выходные данные
4
Примечание

Первый пример соответствует признаку B, изображенному на картинке. Значение этого признака на изображении размера 6 × 8 равняется разности суммарной яркости пикселей в нижней и верхней половине изображения. Для вычисления его значения необходимо выполнить следующие две операции:

  1. Прибавить сумму пикселей на префиксном прямоугольнике с нижним правым углом в 6 строке и 8 столбце с коэффициентом 1 к переменной value (красной рамкой обозначен прямоугольник);
  2. Прибавить сумму пикселей на префиксном прямоугольнике с нижним правым углом в 3 строке и 8 столбце с коэффициентом  - 2 и переменной value.

Таким образом, все пиксели в нижних трёх строках изображения войдут с коэффициентом 1, а все пиксели в верхних трёх строках изображения войдут с коэффициентом 1 - 2 =  - 1, что и требуется.