Олимпиадный тренинг

Задача . E. Кирпичи

Задача

Кирпич — прямоугольник с целыми сторонами шириной $1$ или высотой $1$ (или и то и другое).

Дана сетка $n\times m$, и каждая ячейка окрашена в черный или белый цвет. Замощение — это способ поместить кирпичи на сетку так, чтобы каждая черная ячейка была покрыта ровно одним кирпичом, а каждая белая ячейка не была покрыта кирпичом. Другими словами, кирпичи размещаются только в черных ячейках, покрывают все черные ячейки, и никакие два кирпича не перекрываются.

$\text{[math]}$ Пример замощения с первого примера с использованием $5$ кирпичей. Существует также замощение из $4$ кирпичей.

Какое минимальное количество кирпичей необходимо для замощения данной сетки?

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

Первая строка содержит два целых числа $n$, $m$ ($1\le n, m\le 200$) — количество строк и столбцов соответственно.

Следующие $n$ строки описывают сетку. $i$-я строка содержит строку длиной $m$, где $j$-я строка обозначает цвет ячейки в строке $i$, столбец $j$. Черная ячейка обозначается символом «#», а белая — символом «.».

Гарантируется, что есть хотя бы одна черная ячейка.

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

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

Примечание

Сетка с первого примера может быть замощена $4$-мя кирпичами, размещенными вертикально.

Сетка с третьего примера может быть замощена такими $18$ кирпичами:

$\text{[math]}$

Примеры

№	Входные данные	Выходные данные
1	3 4 #.## #### ##..	4
2	6 6 ###### ##.... ###### ##...# ##...# ######	6
3	10 8 ####..## #..#.##. #..#.### ####.#.# ....#### .###.### ###.#..# ######## ###..### .##.###.	18

time 4000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет