AT_abc233_g [ABC233G] Strongest Takahashi

题目描述

有一个 $N \times N$ 的网格，其中一些格子上放有方块。
网格的信息由 $N$ 个字符串 $S_1,S_2,\dots,S_N$ 以如下形式给出：

• 当 $S_i$ 的第 $j$ 个字符为 # 时，表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子上有方块。
• 当 $S_i$ 的第 $j$ 个字符为 . 时，表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子上没有方块。

高桥君可以进行如下操作，次数不限（可以为 $0$ 次）：

• 首先，选择一个整数 $D$，满足 $1 \le D \le N$，以及网格中的一个 $D \times D$ 的正方形区域。
• 然后，消耗 $D$ 点体力，将该正方形区域内的所有方块全部破坏。

请你求出高桥君破坏所有方块所需的最小体力值。

输入格式

输入按以下格式从标准输入给出。

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

输出格式

请输出一个整数，表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

4

输入输出样例 #2

输入 #2

3
...
...
...

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

19

说明/提示

限制条件

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

样例解释 1

可以选择如下的正方形区域，使得消耗的体力为 $4$，且这是最优的：

• 以从上往下第 $1$ 行、从左往右第 $1$ 列为左上角的 $3 \times 3$ 的正方形区域。
• 以从上往下第 $5$ 行、从左往右第 $5$ 列为左上角的 $1 \times 1$ 的正方形区域。

样例解释 2

也有可能网格中没有任何方块。

由 ChatGPT 4.1 翻译