| Codeforces Round 576 (Div. 1) |
|---|
| Закончено |
Есть клетчатый квадрат размера $$$n \times n$$$. Некоторые клетки квадрата покрашены в черный цвет, остальные клетки покрашены в белый. За одну операцию разрешается выбрать некоторый прямоугольник и перекрасить все его клетки в белый цвет. За перекраску прямоугольника размера $$$h \times w$$$ взимается штраф в размере $$$\max(h, w)$$$. Требуется за минимальный суммарный штраф покрасить все клетки в белый цвет.
В первой строке через пробел задано одно целое число $$$n$$$ — размер квадрата ($$$1 \leq n \leq 50$$$).
В следующих $$$n$$$ строках записаны строки длины $$$n$$$, состоящие из символов . и #. Если $$$j$$$-й символ $$$i$$$-й строки равен #, то клетка квадрата с координатами $$$(i, j)$$$ является чёрной, иначе — белой.
Выведите одно число — минимальный суммарный штраф покраски всего квадрата в белый цвет.
3 ### #.# ###
3
3 ... ... ...
0
4 #... .... .... #...
2
5 #...# .#.#. ..... .#... #....
5
На картинке вы можете видеть четыре примера и некоторые из оптимальных способов их покрасить.
