G - Strongest Takahashi
当前没有测试数据。
G - 最强的高桥
得分：$600$分
问题描述
现在有一个 $N \times N$ 的网格，在一些方格上放有方块。
网格可以用 $N$ 个字符串 $S_1,S_2,\dots,S_N$ 来描述，如下所示。
- 如果 $S_i$ 的第 $j$ 个字符是
#，则表示网格的第 $i$ 行从上到下，第 $j$ 列从左到右放有一个方块。 - 如果 $S_i$ 的第 $j$ 个字符是
.，则表示网格的第 $i$ 行从上到下，第 $j$ 列从左到右没有方块。
高桥可以进行以下操作零次或多次：
- 首先，在 $1$ 和 $N$ 之间（包括 $1$ 和 $N$）选择一个整数 $D$，然后在网格内选择一个大小为 $D \times D$ 的子网格。
- 然后，花费 $D$ 的体力值来摧毁子网格中的所有方块。
求摧毁所有方块所需的最小体力值。
约束
- $N$ 是一个整数。
- $1 \le N \le 50$
- $S_i$ 由
#和.组成。 - $|S_i|=N$
输入
输入数据从标准输入中读入，格式如下：
输出
以整数的形式输出答案。
5
##...
.##..
#.#..
.....
....#
4
选择以下子网格，高桥需要消耗 $4$ 的体力值，这是最优策略。
- 左上角为 $(1,1)$，大小为 $3 \times 3$ 的子网格。
- 左上角为 $(5,5)$，大小为 $1 \times 1$ 的子网格。
3
...
...
...
0
网格上可能没有方块。
21
.....................
.....................
...#.#...............
....#.............#..
...#.#...........#.#.
..................#..
.....................
.....................
.....................
..........#.....#....
......#..###.........
........#####..#.....
.......#######.......
.....#..#####........
.......#######.......
......#########......
.......#######..#....
......#########......
..#..###########.....
.........###.........
.........###.........
19