| Codeforces Round 668 (Div. 1) |
|---|
| Закончено |
Кирпич — прямоугольник с целыми сторонами шириной $$$1$$$ или высотой $$$1$$$ (или и то и другое).
Дана сетка $$$n\times m$$$, и каждая ячейка окрашена в черный или белый цвет. Замощение — это способ поместить кирпичи на сетку так, чтобы каждая черная ячейка была покрыта ровно одним кирпичом, а каждая белая ячейка не была покрыта кирпичом. Другими словами, кирпичи размещаются только в черных ячейках, покрывают все черные ячейки, и никакие два кирпича не перекрываются.
Пример замощения с первого примера с использованием $$$5$$$ кирпичей. Существует также замощение из $$$4$$$ кирпичей. Какое минимальное количество кирпичей необходимо для замощения данной сетки?
Первая строка содержит два целых числа $$$n$$$, $$$m$$$ ($$$1\le n, m\le 200$$$) — количество строк и столбцов соответственно.
Следующие $$$n$$$ строки описывают сетку. $$$i$$$-я строка содержит строку длиной $$$m$$$, где $$$j$$$-я строка обозначает цвет ячейки в строке $$$i$$$, столбец $$$j$$$. Черная ячейка обозначается символом «#», а белая — символом «.».
Гарантируется, что есть хотя бы одна черная ячейка.
Выведите единственное целое число — минимальное количество требуемых кирпичей.
3 4 #.## #### ##..
4
6 6 ###### ##.... ###### ##...# ##...# ######
6
10 8 ####..## #..#.##. #..#.### ####.#.# ....#### .###.### ###.#..# ######## ###..### .##.###.
18
Сетка с первого примера может быть замощена $$$4$$$-мя кирпичами, размещенными вертикально.
Сетка с третьего примера может быть замощена такими $$$18$$$ кирпичами:
