最强高桥

题目描述

有一个 $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$

输出格式

将答案作为整数输出。

样例

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

4

选择以下子正方形时,消耗的体力为 4,这是最优的。

• 以从上数第 1 行、从左数第 1 列为左上角的 $3 \times 3$ 子正方形。
• 以从上数第 5 行、从左数第 5 列为左上角的 $1 \times 1$ 子正方形。

3
...
...
...

0

网格上也可能一个方块都没有。

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

19

数据范围

• $N$ 是整数
• $1 \le N \le 50$
• $S_i$ 只由 # 和 . 组成
• $|S_i|=N$