有一个大小为 $$$n \times n$$$ 的方形网格。一些细胞呈黑色,所有其他细胞呈白色。在一项操作中,您可以选择某个矩形并将其所有单元格着色为白色。为大小为 $$$h \times w$$$ 的矩形着色的成本为 $$$\max(h, w)$$$。您将以最小的总成本将所有单元格设置为白色。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 50$$$) — 方形网格的大小。
接下来的 $$$n$$$ 行均包含长度为 $$$n$$$ 的字符串,由字符“.”组成。和 '#'。如果坐标为 $$$(i, j)$$$ 的单元格为黑色,则第 $$$i$$$ 行的第 $$$j$$$ 个字符为“#”,否则为白色。
输出
打印一个整数 - 将所有单元格涂成白色的最小总成本。
示例
输入 #1
3 ### #.# ###
输出 #1
3
输入 #2
3 ... ... ...
输出 #2
0
输入 #3
4 #... .... .... #...
输出 #3
2
输入#4
5 #...# .#.#. ..... .#... #....
输出#4
5
注意
示例和一些最佳解决方案如下图所示。