配点 : $600$ 点

問題文

$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$ は整数
• $1 \le N \le 50$
• $S_i$ は # と . のみからなる
• $|S_i|=N$

入力

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

$N$

$S_1$

$S_2$

$\vdots$

$S_N$

出力

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

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

4

以下の部分正方形を選ぶことで、消費する体力を $4$ にすることができ、これが最適です。

• 上から $1$ マス目、左から $1$ マス目を左上とした、 $3 \times 3$ の部分正方形
• 上から $5$ マス目、左から $5$ マス目を左上とした、 $1 \times 1$ の部分正方形

3
...
...
...

0

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

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

19