题目描述

$N\ \times\ N$ のグリッドがあり、いくつかのマスにはブロックが置いてあります。
グリッドの情報は $N$ 個の文字列 $S_1,S_2,\dots,S_N$ によって以下の形式で与えられます。

• $S_i$ の $j$ 文字目が # のとき、グリッドの上から $i$ マス目、左から $j$ マス目にブロックがある。
• $S_i$ の $j$ 文字目が . のとき、グリッドの上から $i$ マス目、左から $j$ マス目にブロックがない。

高橋くんは、以下の操作を $0$ 回以上好きなだけ行うことができます。

• まず、 $1$ 以上 $N$ 以下の整数 $D$ と、グリッド内の $D\ \times\ D$ の部分正方形を選ぶ。
• その後、体力 $D$ を消費して部分正方形内のブロックをすべて破壊する。

高橋くんがすべてのブロックを破壊するのに必要な体力の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $S_1$ $S_2$ $\vdots$ $S_N$

输出格式

答えを整数として出力せよ。

题目大意

问题陈述

给定有一个 $N \times N$ 的地图 $S$，若 $S_{i, j}$ 是 #，则位置 $(i,j)$ 上有障碍。

高桥可以进行下面的操作 $0$ 次或更多次：

• 首先，在 $1\sim N$ 之间选择一个整数 $D$，并在地图内选择一个 $D \times D$ 的子矩阵。
• 消耗 $D$ 的代价摧毁子方格内的所有障碍。

求摧毁所有障碍所需的最少代价。

translated by

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

4

3
...
...
...

0

21
.....................
.....................
...#.#...............
....#.............#..
...#.#...........#.#.
..................#..
.....................
.....................
.....................
..........#.....#....
......#..###.........
........#####..#.....
.......#######.......
.....#..#####........
.......#######.......
......#########......
.......#######..#....
......#########......
..#..###########.....
.........###.........
.........###.........

19

提示

制約

• $N$ は整数
• $1\ \le\ N\ \le\ 50$
• $S_i$ は # と . のみからなる
• $|S_i|=N$

Sample Explanation 1

以下の部分正方形を選ぶことで、消費する体力を $4$ にすることができ、これが最適です。 - 上から $1$ マス目、左から $1$ マス目を左上とした、 $3\ \times\ 3$ の部分正方形 - 上から $5$ マス目、左から $5$ マス目を左上とした、 $1\ \times\ 1$ の部分正方形

Sample Explanation 2

グリッドにブロックが $1$ つもない場合もあります。