分数: 600 点
问题陈述
有一个 N \times N 网格,一些方块上有方块。
网格描述为 N 字符串 S_1,S_2,\dots,S_N,如下。
- 如果 j第一个字符 S_i is
#,广场上有一个方块 i从顶部数第行和 j左起第 列。 - 如果 j第一个字符 S_i is
.,该处的广场上没有方块 i从顶部数第行和 j左起第 列。
Takahashi 可以执行零次或多次以下的操作。
- 首先,选择一个整数 D 之间 1 和 N (含),以及 D \times D 网格内的子方格。
- 然后,消费 D 耐力点可以摧毁子方格内的所有方块。
找出摧毁所有方块所需的最小耐力值。
约束
- N 是一个整数。
- 1 \le N \le 50
- S_i 包括
#和.. - |S_i|=N
输入
输入由标准输入按以下格式给出:
N S_1 S_2 \vdots S_N
输出
将答案打印为整数。
示例输入 1
5 ##... .##.. #.#.. ..... ....#
示例输出 1
4
通过选择下面的子方格,高桥将消耗 4 耐力点,这是最佳的。
- 的 3 \times 3 左上方方块位于 1- 从顶部开始的第行和 1- 左起第 1 列。
- 的 1 \times 1 左上方方块位于 5从顶部数第行和 5左起第 列。
示例输入 2
3 ... ... ...
示例输出 2
0
网格上可能没有方块。
示例输入 3
21 ..................... ..................... ...#.#............... ....#.............#.. ...#.#...........#.#. ..................#.. ..................... ..................... ..................... ..........#.....#.... ......#..###......... ........#####..#..... .......#######....... .....#..#####........ .......#######....... ......#########...... .......#######..#.... ......#########...... ..#..###########..... .........###......... .........###.........
示例输出 3
19