CF1198D.Rectangle Painting 1

There is a square grid of size $n \times n$. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs $\max(h, w)$ to color a rectangle of size $h \times w$. You are to make all cells white for minimum total cost.

有一个 $n \times n$ 的正方形网格。其中部分格子被染成黑色，其余格子均为白色。在一次操作中，你可以选择某个矩形区域，并将该矩形内的所有格子染成白色。将一个 $h \times w$ 大小的矩形染白的代价为 $\max(h, w)$。你的目标是以最小的总代价将所有格子变为白色。

The first line contains a single integer $n$ ($1 \leq n \leq 50$) — the size of the square grid.

Each of the next $n$ lines contains a string of length $n$, consisting of characters '.' and '#'. The $j$-th character of the $i$-th line is '#' if the cell with coordinates $(i, j)$ is black, otherwise it is white.

第一行包含一个整数 $n$（$1 \leq n \leq 50$）——表示正方形网格的大小。

接下来的 $n$ 行中，每行包含一个长度为 $n$ 的字符串，由字符 '.' 和 '#' 组成。第 $i$ 行的第 $j$ 个字符为 '#'，当且仅当坐标为 $(i, j)$ 的格子是黑色的；否则该格子为白色。

Print a single integer — the minimum total cost to paint all cells in white.

输出一个整数——将所有格子涂成白色的最小总代价。

The examples and some of optimal solutions are shown on the pictures below.

示例及部分最优解如下图所示。