102336: [AtCoder]ABC233 G - Strongest Takahashi

Problem Statement

There is a $N \times N$ grid, with blocks on some squares.
The grid is described by $N$ strings $S_1,S_2,\dots,S_N$, as follows.

• If the $j$-th character of $S_i$ is #, there is a block on the square at the $i$-th row from the top and $j$-th column from the left.
• If the $j$-th character of $S_i$ is ., there is not a block on the square at the $i$-th row from the top and $j$-th column from the left.

Takahashi can do the operation below zero or more times.

• First, choose an integer $D$ between $1$ and $N$ (inclusive), and a $D \times D$ subsquare within the grid.
• Then, consume $D$ stamina points to destroy all blocks within the subsquare.

Find the minimum number of stamina points needed to destroy all the blocks.

Constraints

• $N$ is an integer.
• $1 \le N \le 50$
• $S_i$ consists of # and ..
• $|S_i|=N$

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer as an integer.

Sample Input 1

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

Sample Output 1

4

By choosing the subsquares below, Takahashi will consume $4$ stamina points, which is optimal.

• The $3 \times 3$ subsquare whose top-left square is at the $1$-st row from the top and $1$-st column from the left.
• The $1 \times 1$ subsquare whose top-left square is at the $5$-th row from the top and $5$-th column from the left.

Sample Input 2

3
...
...
...

Sample Output 2

0

There may be no block on the grid.

Sample Input 3

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

Sample Output 3

19

问题描述

有一个$N \times N$的网格，某些方块上有一些方块。

• 如果$S_i$的第$j$个字符是#，则在从上数第$i$行，从左数第$j$列的方块上有一个方块。
• 如果$S_i$的第$j$个字符是.，则在从上数第$i$行，从左数第$j$列的方块上没有一个方块。

高桥可以执行零次或多次以下操作。

• 首先，选择一个介于1和N（含）之间的整数D，并在网格中选择一个D×D的子方块。
• 然后，消耗D点体力来销毁子方块中的所有方块。

找出销毁所有方块所需的最小体力值。

约束条件

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

输入

输入将以以下格式从标准输入给出：

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

输出

将答案作为整数打印。

样例输入1

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