3.方格涂色

题目描述

有一个$n \times n$大小的方格图，某些方格初始是黑色，其余为白色，要求用最小的代价把所有方格变成白色，其中代价的计算方式为染一个$n \times m$的矩形区域的代价为$\max(m,n)$。

输入格式

输入的第一行包含一个整数$n$。

接下来$n$行，每行为一个长度为$n$的字符串，由.与#组成，分别表示白色与黑色。第$x$行第$y$列的坐标为$(x,y)$。

输出格式

一行一个整数表示答案。

数据范围与提示

• 对于$40\%$的数据，$n < 5$；
• 对于$100\%$的数据，$1 < n < 50$。

样例

5
#...#
.#.#.
.....
.#...
#....

5