← 返回题目列表

AtCoder · abc233_g

G. 最强高桥

中文机器翻译题面 查看原题

分数: 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